David S. Johnson
Skip Abstract Section
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.
- Agrawal, M., Kayal, N., and Saxena, N. 2004. PRIMES is in P. Ann. Math. 160, 781--793.Google Scholar
Cross Ref
- Álvarez, C., Gabarró, J., and Serna, M. 2005. Pure Nash equilibria in games with a large number of actions. In Proceedings of the 30th International Symposium on Mathematical Foundations of Computer Science. Lecture Notes in Computer Science, vol. 3618. Springer-Verlag, Berlin, 95--106. Google ScholarDigital Library
- Arya, V., Garg, N., Khandekar, R., Meyerson, A., Munagala, K., and Pandit, V. 2004. Local search heuristics for k-median and facility location problems. SIAM J. Comput. 33, 544--562. (Preliminary version in Proceedings of the 33rd Annual ACM Symposium on Theory of Computing. ACM, New York, 2001, 21--29.) Google ScholarDigital Library
- Beame, P., Cook, S., Edmonds, J., Impagliazzo, R., and Pitassi, T. 1998. The relative complexity of NP search problems. J. Comput. Syst. Sci. 57, 3--19. Google ScholarDigital Library
- Blum, M., and Impagliazzo, R. 1987. Generic oracles and oracle classes. In Proceedings of the 28th Annual Symposium on Foundations of Computer Science. IEEE Computer Society, Los Alamitos, Calif., 118--126.Google Scholar
- Brouwer, L. E. J. 1910. Über eneindeutige, stetige Transformationen von Flächen in sich. Math. Ann. 69, 176--180.Google ScholarCross Ref
- Buresh-Oppenheim, J., and Morioka, T. 2004. Relativized NP search problems and propositional proof systems. In Proceedings of the 19th Annual IEEE Conference on Computational Complexity. IEEE Computer Society, Los Alamitos, Calif., 54--67. Google ScholarCross Ref
- Chen, X., and Deng, X. 2005. 3-Nash is PPAD-complete. Tech. Rep. TR05-134, Electronic Colloquium on Computational Complexity.Google Scholar
- Chen, X., and Deng, X. 2006a. On the complexity of 2D discrete fixed point problems. In Proceedings of the 33rd International Colloquium on Automata, Languages and Programming. Lecture Notes in Computer Science, vol. 4051. Springer-Verlag, Berlin, 489--500. Google ScholarDigital Library
- Chen, X., and Deng, X. 2006b. Settling the complexity of two-player Nash equilibrium. In Proceedings of the 47th Annual Symposium on Foundations of Computer Science. IEEE Computer Society, Los Alamitos, Calif., 261--270. Google ScholarDigital Library
- Chen, X., Deng, X., and Teng, S.-H. 2006. Computing Nash equilibria: Approximation and smoothed complexity. In Proceedings of the 47th Annual Symposium on Foundations of Computer Science. IEEE Computer Society, Los Alamitos, Calif., 603--612. Google ScholarDigital Library
- Cohen, P. J. 1964. The independence of the continuum hypothesis. Proc. Nat. Acad. Sci 51, 105--110.Google ScholarCross Ref
- Condon, A. 1992. The complexity of stochastic games. Inform. Comp. 96, 203--224. Google ScholarDigital Library
- Condon, A. 1993. On algorithms for simple stochastic games. In Advances in Computational Complexity Theory, J.-Y. Cai, Ed. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 13. American Mathematical Society, Providence, RI. 51--73.Google Scholar
- Daskalakis, C., Goldberg, P. W., and Papadimitriou, C. H. 2006. The complexity of computing a Nash equilibrium. In Proceedings of the 38th Annual ACM Symposium on Theory of Computing. ACM, New York, 71--78. Google ScholarDigital Library
- Daskalakis, C., Goldberg, P. W., and Papadimitriou, C. H. 2007. The complexity of computing a Nash equilibrium. Submitted journal version of Daskalakis et al. {2006}, Goldberg and Papadimitriou {2006}, and Dasakalakis and Papadimitriou {2005}.Google Scholar
- Daskalakis, C., and Papadimitriou, C. H. 2005. Three-player games are hard. Tech. Rep. TR05-139, Electronic Colloquium on Computational Complexity.Google Scholar
- Ehrenfeucht, A., and Mycielski, J. 1979. Positional strategies for mean payoff games. Int. J. Game Theory 8, 109--113.Google ScholarDigital Library
- Emerson, E. A., and Jutla, C. S. 1991. Tree automata, mu-calculus and determinacy. In Proceedings of the 32nd Annual Symposium on Foundations of Computer Science. IEEE Computer Society, Los Alamitos, Calif., 368--377. Google ScholarDigital Library
- Englert, M., Röglin, H., and Vöcking, B. 2007. Worst case and probabilistic analysis of the 2-opt algorithm for the TSP. In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, Philadelphia, PA, 1295--1304. Google ScholarDigital Library
- Fabrikant, A., Papadimitriou, C. H., and Talwar, K. 2004. The complexity of pure Nash equilibria. In Proceedings of the 34th Annual ACM Symposium on Theory of Computing. ACM, New York, 604--612. Google ScholarDigital Library
- Fenner, S., Fortnow, L., Kurtz, S., and Li, L. 2003. An oracle builder's toolkit. Inform. Comp. 182, 95--136. Google ScholarDigital Library
- Fortnow, L., and Sipser, M. 1988. Are there interactive protocols for co-NP languages? Inform. Proc. Lett. 28, 249--251. Google ScholarDigital Library
- Foster, J. A. 1993. The generic oracle hypothesis is false. Inform. Proc. Lett. 45, 59--62. Google ScholarDigital Library
- Friedl, K., Ivanyos, G., Santha, M., and Verhoeven, Y. F. 2006. Locally 2-dimensional Sperner problems complete for polynomial parity argument classes. In Proceedings of the 6th Italian Conference on Algorithms and Complexity. Lecture Notes in Computer Science, vol. 3998. Springer-Verlag, Berlin, 380--391. Google ScholarDigital Library
- Goldberg, P. W., and Papadimitriou, C. H. 2006. Reducibility among equilibrium problems. In Proceedings of the 38th Annual ACM Symposium on Theory of Computing. ACM, New York, 61--70. Google ScholarDigital Library
- Gottlob, G., Greco, G., and Scarcello, F. 2003. Pure Nash equilibria: Hard and easy games. In Proceedings of the 9th Conference on Theoretical Aspects of Rationality and Knowledge. ACM, New York, 215--230. Google ScholarDigital Library
- Grigni, M. 2001. A Sperner lemma complete for PPA. Inform. Proc. Lett. 77, 255--259. Google ScholarDigital Library
- Gurvich, V. A., Karzanov, A. V., and Khachiyan, L. G. 1988. Cyclic games and an algorithm to find minimax cycle means in directed graphs. U.S.S.R. Comput. Math. Math. Phys. 28, 85--91. Google ScholarDigital Library
- Homan, C. M., and Thakur, M. 2003. One-way permutations and self-witnessing languages. J. Comput. Syst. Sci. 67, 608--622. Google ScholarDigital Library
- Hopfield, J. J. 1982. Neural networks and physical systems with emergent collective computational abilities. Proc. Nat. Acad. Sci. 79, 2554--2558.Google ScholarCross Ref
- Johnson, D. S., and McGeoch, L. A. 1997. The traveling salesman problem: A case study in local optimization. In Local Search in Combinatorial Optimization, E. Aarts and J. K. Lenstra, Eds. John Wiley & Sons, Chichester, UK, 215--310. Preliminary version available at http://www.research. att.com/∼∼dsj/papers.Google Scholar
- Johnson, D. S., Papadimitriou, C. H., and Yannakakis, M. 1988. How easy is local search? J. Comput. Syst. Sci. 37, 79--100. Google ScholarDigital Library
- Juba, B. 2005. On the hardness of simple stochastic games. M.S. Thesis, Carnegie-Mellon University. Currently available from http://people.csail.mit.edu/bjuba/.Google Scholar
- Jurdziński, M. 1998. Deciding the winner in parity games is in UP ∩ co-UP. Inform. Proc. Lett. 68, 119--124. Google ScholarDigital Library
- Jurdziński, M., Paterson, M., and Zwick, U. 2006. A deterministic subexponential algorithm for solving parity games. In Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, Philadelphia, PA, 117--123. Google ScholarDigital Library
- Kakutani, S. 1941. A generalization of Brouwer's fixed point theorem. Duke Math. J. 8, 457--459.Google ScholarCross Ref
- Karzanov, A. V., and Lebedev, V. N. 1993. Cyclical games with prohibitions. Math. Prog. 60, 277--293. Google ScholarDigital Library
- Kernighan, B., and Lin, S. 1970. An efficient heuristic for partitioning graphs. Bell Syst. Tech. J. 49, 291--307.Google ScholarCross Ref
- Khachiyan, L. G. 1979. A polynomial algorithm in linear programming. Dokl. Akad. Nauk. SSSR 20, 191--194.Google Scholar
- Klee, V., and Minty, G. J. 1972. How good is the simplex algorithm? In Inequalities III, O. Shisha, Ed. Academic Press, New York, 159--175.Google Scholar
- Korupolu, M. R., Plaxton, C. G., and Rajaraman, R. 2000. Analysis of a local search heuristic for facility location problems. J. Alg. 37, 146--188. Google ScholarDigital Library
- Krentel, M. W. 1989. Structure in locally optimal solutions. In Proceedings of the 30th Annual Symposium on Foundations of Computer Science. IEEE Computer Society, Los Alamitos, Calif., 216--221.Google ScholarDigital Library
- Lemke, C. E. 1965. Bimatrix equivalence points and mathematical programming. Mgmt. Sci. 11, 681--689.Google ScholarCross Ref
- Lenstra, A. K., and Lenstra, H. W., Eds. 1993. Development of the Number Field Sieve. Lecture Notes in Mathematics, vol. 1554. Springer-Verlag, Berlin.Google Scholar
- Lin, S., and Kernighan, B. 1973. An effective heuristic algorithm for the traveling salesman problem. Oper. Res. 21, 972--989.Google ScholarDigital Library
- Lipton, R. J., and Markakis, E. 2004. Nash equilibria via polynomial equations. In Latin 2000: Theoretical Informatics. Lecture Notes in Computer Science, vol. 2976. Springer-Verlag, Berlin, 413--422.Google Scholar
- Lipton, R. J., Markakis, E., and Mehta, A. 2003. Playing large games using simple strategies. In Proceedings of the 4th ACM Conference on Electronic Commerce. ACM, New York, 36--41. Google ScholarDigital Library
- Lueker, G. 1976. Manuscript, Princeton University.Google Scholar
- Lund, C., Fortnow, L., Karloff, H., and Nisan, N. 1992. Algebraic methods for proof systems. J. ACM 39, 859--868. Google ScholarDigital Library
- Megiddo, N., and Papadimitriou, C. H. 1991. On total functions, existence theorems and computational complexity. Theor. Comput. Sci. 81, 317--324. Google ScholarDigital Library
- Morioka, T. 2001. The classification of search problems and their definability in bounded arithmetic. M.S. thesis, University of Toronto. Also available as Tech. Rep. TR01-82, Electronic Colloquium on Computational Complexity.Google Scholar
- Nash, J. F. 1951. Non-cooperative games. Ann. Math. 54, 286--295.Google ScholarCross Ref
- Papadimitriou, C. H. 1990. On graph-theoretic lemmata and complexity classes. In Proceedings of the 31st Annual IEEE Symposium on Foundations of Computing. IEEE Computer Society, Los Alamitos, Calif., 794--801. (Preliminary version of Papadimitriou {1994}.Google ScholarDigital Library
- Papadimitriou, C. H. 1992. The complexity of the Lin-Kernighan heuristic for the traveling salesman problem. SIAM J. Comput. 21, 450--465. Google ScholarDigital Library
- Papadimitriou, C. H. 1994. The complexity of the parity argument and other inefficient proofs of existence. J. Comput. Syst. Sci. 48, 498--532. (Journal version of Papadimitriou {1990}. Google ScholarDigital Library
- Papadimitriou, C. H., Schäffer, A. A., and Yannakakis, M. 1990. On the complexity of local search. In Proceedings of the 22nd Annual ACM Symposium on Theory of Computing. ACM, New York, 438--445. Google ScholarDigital Library
- Papadimitriou, C. H., and Steiglitz, K. 1978. Some examples of difficult traveling salesman problems. Oper. Res. 26, 434--443.Google ScholarDigital Library
- Pomerance, C. 1996. A tale of two sieves. Amer. Math. Soc. Not. 43, 1473--1485.Google Scholar
- Pratt, V. 1975. Every prime has a succinct certificate. SIAM J. Comput. 4, 214--220.Google ScholarDigital Library
- Puri, A. 1995. Theory of hybrid systems and discrete event systems. Ph.D. thesis, University of California, Berkeley. Google ScholarDigital Library
- Rosenthal, R. W. 1973. A class of games possessing pure-strategy Nash equilibria. Int. J. Game Theory 2, 65--67.Google ScholarDigital Library
- Schäffer, A. A., and Yannakakis, M. 1991. Simple local search problems that are hard to solve. SIAM J. Comput. 20, 56--87. Google ScholarDigital Library
- Shamir, A. 1992. IP = PSPACE. J. ACM 39, 869--877. Google ScholarDigital Library
- Sipser, M. 1982. On relativization and the existence of complete sets. In Proceedings of the 9th International Colloquium on Automata, Languages and Programming. Lecture Notes in Computer Science, vol. 140. Springer-Verlag, Berlin, 523--531. Google ScholarDigital Library
- Sperner, E. 1928. Neuer beweis für die Invarianz der Dimensionzahl und des Gebietes. Abh. math. Sem. Univ. Hamburg 6, 265--272.Google ScholarCross Ref
- Vöcking, B. 2006. Congestion games: Optimization in competition. In Proceedings of the 2nd Algorithms and Complexity in Durham Workshop, H. Broersma, S. Dantchev, M. Johnson, and S. Szeider, Eds. Kings College Publications, London, 9--20.Google Scholar
- Yannakakis, M. 1990. The analysis of local search problems and their heuristics. In Proceedings of the 7th Annual Symposium on Theoretical Aspects of Computing. Lecture Notes in Computer Science, vol. 415. Springer-Verlag, Berlin, Germany, 298--311. Google ScholarDigital Library
- Yannakakis, M. 1997. Computational complexity. In Local Search in Combinatorial Optimization, E. Aarts and J. K. Lenstra, Eds. John Wiley & Sons, Chichester, UK, 19--55.Google Scholar
- Zwick, U., and Paterson, M. 1996. The complexity of mean payoff games on graphs. Theor. Comput. Sci. 158, 343--359. Google ScholarDigital Library
Index Terms
- The NP-completeness column: Finding needles in haystacks
Recommendations
The myth of the folk theorem
STOC '08: Proceedings of the fortieth annual ACM symposium on Theory of computingA well-known result in game theory known as "the Folk Theorem" suggests that finding Nash equilibria in repeated games should be easier than in one-shot games. In contrast, we show that the problem of finding any (approximate) Nash equilibrium for a ...
Can Almost Everybody be Almost Happy?
ITCS '16: Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer ScienceWe conjecture that PPAD has a PCP-like complete problem, seeking a near equilibrium in which all but very few players have very little incentive to deviate. We show that, if one assumes that this problem requires exponential time, several open problems ...
Further collapses in TFNP
CCC '22: Proceedings of the 37th Computational Complexity ConferenceWe show EOPL = PLS ∩ PPAD. Here the class EOPL consists of all total search problems that reduce to the End-of-Potential-Line problem, which was introduced in the works by Hubáček and Yogev (SICOMP 2020) and Fearnley et al. (JCSS 2020). In particular, ...
Comments