This group gathers pioneers of theory of computation whose primary contribution was computational complexity theory, classifying problems by the time, space or other resources an algorithm needs to solve them, including the P versus NP question, NP-completeness, polynomial-time reductions, complexity classes and hierarchy theorems, circuit and communication complexity, proof complexity, algorithmic information theory and Kolmogorov complexity, and the study of hardness of approximation. It follows the Computational complexity and cryptography second-level heading of the ACM Computing Classification System under Theory of Computation. Their shared work is proving what is and is not efficiently computable in principle, as distinct from designing one specific efficient algorithm, which belongs to Algorithm Design and Analysis, or a cryptographic construction, which belongs to Cryptography and Cryptanalysis.
Facts
Comparison
Era of Emergence All Computational Complexity Theory
Filter Results62 entries
Sources
1. Wikipedia: Computational complexity theory
WikipediaComputational complexity theory, History section, Hartmanis-Stearns sentenceQuote, Computational complexity theory, History section, Hartmanis-Stearns sentence
The beginning of systematic studies in computational complexity is attributed to the seminal 1965 paper "On the Computational Complexity of Algorithms" by Juris Hartmanis and Richard E. Stearns, which laid out the definitions of time complexity and space complexity, and proved the hierarchy theorems.
Wikipedia: Róbert Szelepcsényi
Has Member: Róbert Szelepcsényi, Lead sectionQuote, Has Member: Róbert Szelepcsényi, Lead section
closure of non-deterministic space under complement
Uriel Feige (Wikipedia)
Has Member: Uriel Feige, English Wikipedia, infoboxQuote, Has Member: Uriel Feige, English Wikipedia, infobox
Uriel Feige currently holds the post of Professor at the Department of Computer Science and Applied Mathematics
Luca Trevisan (Wikipedia)
Has Member: Luca Trevisan, LeadQuote, Has Member: Luca Trevisan, Lead
His research area was theoretical computer science, focusing on randomness, cryptography, probabilistically checkable proofs, approximation, property testing, spectral graph theory, and sublinear algorithms.
Nick Pippenger (source article)
Has Member: Nick Pippenger, Lead, Nick's ClassQuote, Has Member: Nick Pippenger, Lead, Nick's Class
was named by Stephen Cook after Nick Pippenger for his research on circuits with polylogarithmic depth and polynomial size
Ashok K. Chandra (Wikipedia)
Has Member: Ashok K. Chandra, Lead, complexity groupQuote, Has Member: Ashok K. Chandra, Lead, complexity group
he introduced alternating Turing machines in computational complexity (with Dexter Kozen and Larry Stockmeyer)
Wikipedia: Neil Immerman
Has Member: Neil Immerman, Lead sectionQuote, Has Member: Neil Immerman, Lead section
key developers of descriptive complexity
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.