An overview of computational complexity

DOI10.1145/358141.358144zbMath0622.68039DBLPjournals/cacm/Cook83OpenAlexW1974040526WikidataQ55890216 ScholiaQ55890216MaRDI QIDQ3759938

Stephen A. 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

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

Related Items (10)

A parallel algorithm for the monadic unification problem ⋮ Parallel computation of manipulator inverse dynamics ⋮ Constructing a perfect matching is in random NC ⋮ Squeezing Feasibility ⋮ Tradeoffs for language recognition on alternating machines ⋮ Towards NP-P via proof complexity and search ⋮ Distributed Self-Stabilizing MIS with Few States and Weak Communication ⋮ Classifying the computational complexity of problems ⋮ COMPLEXITY AS A MEASURE OF THE DIFFICULTY OF SYSTEM DIAGNOSIS ⋮ Computing in combinatorial optimization

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