An overview of computational complexity

DOI10.1145/358141.358144zbMATH Open0622.68039DBLPjournals/cacm/Cook83OpenAlexW1974040526WikidataQ55890216 ScholiaQ55890216MaRDI QIDQ3759938FDOQ3759938

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

• scientific article; zbMATH DE number 218387
• scientific article
• scientific article; zbMATH DE number 610968
• scientific article; zbMATH DE number 784042
• scientific article

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 (28)

• Title not available (Why is that?)
• Title not available (Why is that?)
• Tradeoffs for language recognition on alternating machines
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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
• 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
• A Short Introduction to Implicit Computational Complexity
• COMPLEXITY AS A MEASURE OF THE DIFFICULTY OF SYSTEM DIAGNOSIS
• Distributed Self-Stabilizing MIS with Few States and Weak Communication
• Classifying the computational complexity of problems
• Computing in combinatorial optimization
• Polynomial time computations in models of ET
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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)