On graph-theoretic lemmata and complexity classes
- 4 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 794-801 vol.2
- https://doi.org/10.1109/fscs.1990.89602
Abstract
Several new complexity classes of search problems that lie between the classes FP and FNP are defined. These classes are contained in the class TFNP of search problems that always have a solution. A problem in each of these new classes is defined in terms of an implicitly given, exponentially large graph, very much like PLS (polynomial local search). The existence of the solution sought is established by means of a simple graph-theoretic lemma with an inefficiently constructive proof. Several class containments and collapses, resulting in the two new classes PDLF contained in PLF are shown; the relation of either class of PLS is open. PLF contains several important problems for which no polynomial-time algorithm is presently known.Keywords
This publication has 14 references indexed in Scilit:
- Ten Lectures on the Probabilistic MethodPublished by Society for Industrial & Applied Mathematics (SIAM) ,1994
- On the complexity of local searchPublished by Association for Computing Machinery (ACM) ,1990
- Exponential lower bounds for finding Brouwer fix pointsJournal of Complexity, 1989
- Structure in locally optimal solutionsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1989
- The adjacency relation on the traveling salesman polytope is NP-CompleteMathematical Programming, 1978
- Hamiltonian Cycles and Uniquely Edge Colourable GraphsPublished by Elsevier ,1978
- Complementary pivot theory of mathematical programmingLinear Algebra and its Applications, 1968
- Bimatrix Equilibrium Points and Mathematical ProgrammingManagement Science, 1965
- The Jacobian matrix and global univalence of mappingsMathematische Annalen, 1965
- Existence of an Equilibrium for a Competitive EconomyEconometrica, 1954