An overview of computational complexity
DOI10.1145/358141.358144zbMATH Open0622.68039DBLPjournals/cacm/Cook83OpenAlexW1974040526WikidataQ55890216 ScholiaQ55890216MaRDI QIDQ3759938FDOQ3759938
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
Recommendations
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)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Tradeoffs for language recognition on alternating machines
- Polynomial upper bounds on the size of changes of a RAM+BOOL program as a tool for proving belonging to FP
- \(\mathrm P \overset {?} {=} \mathrm{NP}\)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Physical portrayal of computational complexity
- Towards NP-P via proof complexity and search
- Parallel computation of manipulator inverse dynamics
- Title not available (Why is that?)
- Computational Complexity
- \({\mathcal P}\), \({\mathcal{NP}}\) and mathematics -- a computational complexity perspective
- Title not available (Why is that?)
- Basic complexity
- Theoretical computer science: computational complexity
- Algorithmics -- is there hope for a unified theory? (Invited talk)
- Complexity theory basics: NP and NL
- Constructing a perfect matching is in random NC
- FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
- Book review of: Oded Goldreich, Computational complexity: a conceptual perspective
- Title not available (Why is that?)
- Title not available (Why is that?)
- Squeezing Feasibility
- Logic, automata, and computational complexity. The works of Stephen A. Cook
- A Short Introduction to Implicit Computational Complexity
- COMPLEXITY AS A MEASURE OF THE DIFFICULTY OF SYSTEM DIAGNOSIS
- P, NP, and NP-completeness. The basics of computational complexity.
- Distributed Self-Stabilizing MIS with Few States and Weak Communication
- NP-completeness: a retrospective
- Classifying the computational complexity of problems
- Computing in combinatorial optimization
- Some estimated likelihoods for computational complexity
- Polynomial time computations in models of ET
- Title not available (Why is that?)
- On the impact of Turing machines
- Computational complexity
- Title not available (Why is that?)
- 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
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)
