The NP-completeness column
- 1 May 2007
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 3 (2)
- https://doi.org/10.1145/1240233.1240247
Abstract
This is the 26th edition of a column that covers new developments in the theory of NP-completeness. The presentation is modeled on that which M. R. Garey and I used in our book “Computers and Intractability: A Guide to the Theory of NP-Completeness,” W. H. Freeman & Co., New York, 1979, hereinafter referred to as “[G&J].” Previous columns, the first 23 of which appeared in J. Algorithms , will be referred to by a combination of their sequence number and year of appearance, e.g., “Column 1 [1981].” Full bibliographic details on the previous columns, as well as downloadable unofficial versions of them, can be found at http://www.research.att.com/~dsj/columns/. This column discusses the question of whether finding an object can be computationally difficult even when we know that the object exists.Keywords
This publication has 49 references indexed in Scilit:
- Analysis of a Local Search Heuristic for Facility Location ProblemsJournal of Algorithms, 2000
- The Relative Complexity of NP Search ProblemsJournal of Computer and System Sciences, 1998
- The complexity of mean payoff games on graphsTheoretical Computer Science, 1996
- Algebraic methods for interactive proof systemsJournal of the ACM, 1992
- IP = PSPACEJournal of the ACM, 1992
- Are there interactive protocols for co-NP languages?Information Processing Letters, 1988
- Positional strategies for mean payoff gamesInternational Journal of Game Theory, 1979
- A class of games possessing pure-strategy Nash equilibriaInternational Journal of Game Theory, 1973
- A generalization of Brouwer’s fixed point theoremDuke Mathematical Journal, 1941
- Neuer beweis für die invarianz der dimensionszahl und des gebietesAbhandlungen aus dem Mathematischen Seminar der Universitat Hamburg, 1928