Abstract
For a quarter of a century now, NP-completeness has been computer science's favorite paradigm, fad, punching bag, buzzword, alibi, and intellectual export. This paper is a fragmentary commentary on its origins, its nature, its impact, and on the attributes that have made it so pervasive and contagious.
Partially supported by the National Science Foundation.
A version of this talk was given at a meeting in the Fall of 1995 celebrating the 60th birthday of Richard M. Karp, to whom this paper is also affectionately dedicated.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy, “Proof verification and hardness of approximation problems.” Proc. 33rd FOCS (1992) pp. 14–23.
S. A. Cook “The complexity of theorem-proving procedures,” Proc. 3rd STOC, (1971), pp. 151–158.
W. Diffie and M. E. Hellman “New directions in cryptography,” IEEE Trans. Inform. Theory, 22, pp. 644–654, 1976.
R. G. Downey and M. R. Fellows “Fixed-parameter tractability and completeness I: Basic results,” SIAM Journal on Computing, 24, 4, pp. 873–921, 1995.
T. Eiter, G. Gottlob “Identifying the minimal transversals of a hypergraph and related problems” SIAM Journal on Computing, 24, 6, pp. 1278–1304, 1995.
M. Fredman and L. Khachiyan “On the complexity of dualization of monotone disjunctive normal forms” Journal of Algorithms, 21, 3, pp. 618–628, 1996.
P. Honeyman, R. E. Ladner, M. Yannakakis, “Testing the universal instance assumption,” Information Processing Letters, 12, pp. 14–19, 1980.
D. S. Johnson, C. H. Papadimitriou, M. Yannakakis “How Easy is Local Search?” J.CSS, 1988 (special issue for the 1985 FOCS Conference).
D. S. Johnson, C. H. Papadimitriou, M. Yannakakis “On Generating All Maximal Independent Sets”, Information Processing Letters 1988.
R. M. Karp “Reducibility among combinatorial problems,” pp. 85–103 in Complexity of Computer Computations, R. E. Miller and J. W. Thatcher (eds), 1972.
D. E. Knuth “A terminological proposal,” SIGACT News, 6, 1, pp. 12–18, 1974.
R. E. Ladner “On the structure of polynomial time reducibility,” J.ACM, 22, pp. 155–171, 1975.
L. Levin “Universal sorting problems,” Pr. Inf. Transm., 9, pi 265–266, 1973.
C. H. Papadimitriou “On the Complexity of the Parity Argument and other Inefficient Proofs of Existence” JCSS, 48, 3, 498–532, 1994.
C. H. Papadimitriou “Database metatheory: asking the big queries,” Proc. 1995 PODS Conf., reprinted in SIGACT News, spring 1996.
C. H. Papadimitriou “The complexity of knowledge representation,” Proc. 1996 Computational Complexity Symposium.
C. H. Papadimitriou, M. Yannakakis “Optimization, approximation, and complexity classes” Proc. 1988 STOC, and J.CSS 1991.
C. H. Papadimitriou, M. Yannakakis “On limited nondeterminism and the complexity of the Vapnic-Chervonenkis dimension,” special issue of J.CSS 1996 (special issue for the 1993 Structures Conf.).
R. L. Rivest “Cryptography,” pp. 717–755 in Handbook of Theoretical Computer Science, J. van Leeuwen (ed), The MIT Press/Elsevier, 1990.
S. Sahni, T. Gonzalez “P-complete approximation problems,” J.ACM, 23, pp. 555–565, 1976.
T. J. Schaeffer “The complexity of satisfiability problems,” Proc. 10th STOC, (1978), pp. 216–226.
M. Yannakakis “Node-and edge-deletion problems,” Proc. 10th STOC, (1978), pp. 253–264.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1997 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Papadimitriou, C.H. (1997). NP-completeness: A retrospective. In: Degano, P., Gorrieri, R., Marchetti-Spaccamela, A. (eds) Automata, Languages and Programming. ICALP 1997. Lecture Notes in Computer Science, vol 1256. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-63165-8_160
Download citation
DOI: https://doi.org/10.1007/3-540-63165-8_160
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-63165-1
Online ISBN: 978-3-540-69194-5
eBook Packages: Springer Book Archive