An overview of computational complexity

DOI10.1145/358141.358144MaRDI QIDQ3759938zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Stephen Cook

Publication date 1983

Published in Communications of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/358141.358144

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to computer science (68-02) Analysis of algorithms and problem complexity (68Q25) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) History of computer science (68-03)

Cited in

(40)

• scientific article; zbMATH DE number 4098721 (Why is no real title available?)
• Logic, automata, and computational complexity. The works of Stephen A. Cook
• Complexity of computer computations. Proceedings of a symposium on the complexity of computer computations, held March 20--22, 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York, and sponsored by the Office of Naval Research, mathematics program, IBM World Trade Corporation, and the IBM Research Mathematical Sciences Department
• A parallel algorithm for the monadic unification problem
• Computational Complexity
• Basic complexity
• A Short Introduction to Implicit Computational Complexity
• scientific article; zbMATH DE number 2096708 (Why is no real title available?)
• Theoretical computer science: computational complexity
• Distributed Self-Stabilizing MIS with Few States and Weak Communication
• Algorithmics -- is there hope for a unified theory? (Invited talk)
• COMPLEXITY AS A MEASURE OF THE DIFFICULTY OF SYSTEM DIAGNOSIS
• Physical portrayal of computational complexity
• Towards NP-P via proof complexity and search
• scientific article; zbMATH DE number 3999295 (Why is no real title available?)
• Parallel computation of manipulator inverse dynamics
• scientific article; zbMATH DE number 3974291 (Why is no real title available?)
• scientific article; zbMATH DE number 4011937 (Why is no real title available?)
• \({\mathcal P}\), \({\mathcal{NP}}\) and mathematics -- a computational complexity perspective
• scientific article; zbMATH DE number 3888913 (Why is no real title available?)
• FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
• Classifying the computational complexity of problems
• Tradeoffs for language recognition on alternating machines
• scientific article; zbMATH DE number 4106275 (Why is no real title available?)
• NP-completeness: a retrospective
• Computational complexity
• Polynomial upper bounds on the size of changes of a RAM+BOOL program as a tool for proving belonging to FP
• Computing in combinatorial optimization
• Some estimated likelihoods for computational complexity
• P, NP, and NP-completeness. The basics of computational complexity.
• scientific article; zbMATH DE number 218387 (Why is no real title available?)
• \(\mathrm P \overset {?} {=} \mathrm{NP}\)
• scientific article; zbMATH DE number 1453451 (Why is no real title available?)
• Polynomial time computations in models of ET
• scientific article; zbMATH DE number 4022600 (Why is no real title available?)
• On the impact of Turing machines
• Complexity theory basics: NP and NL
• Constructing a perfect matching is in random NC
• Squeezing Feasibility
• Book review of: Oded Goldreich, Computational complexity: a conceptual perspective

This page was built for publication: An overview of computational complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3759938)