Computational complexity theory is the branch of the theory of computation that classifies computational problems according to the resources, chiefly time and memory, they require to solve. This description is adapted from Wikipedia contributors under CC BY-SA 4.0; changes were made. https://creativecommons.org/licenses/by-sa/4.0/
Facts
Central QuestionWhether the class of problems whose solutions can be verified quickly, once found, is the same as the class of problems that can be solved quickly in the first place, the P versus NP question, whose answer would settle whether every efficiently checkable problem is also efficiently solvable. 1 Key DebateWhether P equals NP. Stephen Cook and Leonid Levin independently proved in 1971 that practically relevant NP-complete problems exist, problems as hard as any other problem in NP, and the question of whether solving them is really as hard as verifying them remains one of the most important open questions in theoretical computer science, with wide implications should it ever be settled either way. 1 Classification
Pure or AppliedBoth / Interdisciplinary 1 Computational Complexity Theory
Filter Results1 entry
Connections
Associated With
Includes
Source Blum's speedup theorem, Wikipedia
Source Function Problem (Wikipedia)
Source Immerman-Szelepcsenyi theorem, Wikipedia
Additional Source Wikipedia: P versus NP ProblemContext section
Source PCP theorem, Wikipedia
Source Savitch's theorem, Wikipedia
Source Sipser-Lautemann theorem, Wikipedia
Source Space hierarchy theorem, Wikipedia
Source Toda's theorem, Wikipedia
Source Unique Games Conjecture (Wikipedia)
Source Valiant-Vazirani theorem, Wikipedia
Sources
1. Computational Complexity Theory (Wikipedia)
WikipediaOpening paragraph
computational complexity theory focuses on classifying computational problems according to their resource usage, and explores the relationships between these classifications.
Lead section, pure or applied classification
In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and explores the relationships between these classifications.
Important open problems / P versus NP problem
The question of whether P equals NP is one of the most important open questions in theoretical computer science because of the wide implications of a solution.
History
The field began to flourish in 1971 when Stephen Cook and Leonid Levin proved the existence of practically relevant problems that are NP-complete.
View the Source Wikipedia: P versus NP Problem
Wikimedia FoundationIncludes: P versus NP, Context sectionQuote, Includes: P versus NP, Context section
The relation between the complexity classes P and NP is studied in computational complexity theory, the part of the theory of computation dealing with the resources required during computation.
Unique Games Conjecture (Wikipedia)
Wikimedia FoundationIncludes: Unique Games Conjecture, Lead sentenceQuote, Includes: Unique Games Conjecture, Lead sentence
In computational complexity theory, the unique games conjecture (often referred to as UGC) is a conjecture made by Subhash Khot in
Space hierarchy theorem, Wikipedia
Includes: Space Hierarchy Theorem, Lead sentenceQuote, Includes: Space Hierarchy Theorem, Lead sentence
In computational complexity theory, the space hierarchy theorems are separation results that show that both deterministic and nond
Function Problem (Wikipedia)
Includes: Function Problem, Lead sentenceQuote, Includes: Function Problem, Lead sentence
In computational complexity theory, a function problem is a computational problem where a single output is expected for every inpu
Savitch's theorem, Wikipedia
Includes: Savitch's Theorem, Lead sentenceQuote, Includes: Savitch's Theorem, Lead sentence
In computational complexity theory, Savitch's theorem, proved by Walter Savitch in 1970, gives a relationship between deterministi
Immerman-Szelepcsenyi theorem, Wikipedia
Blum's speedup theorem, Wikipedia
Includes: Blum's Speedup Theorem, Lead sentenceQuote, Includes: Blum's Speedup Theorem, Lead sentence
In computational complexity theory, Blum's speedup theorem, first stated by Manuel Blum in 1967, is a fundamental theorem about th
Sipser-Lautemann theorem, Wikipedia
Toda's theorem, Wikipedia
Includes: Toda's Theorem, Lead sentenceQuote, Includes: Toda's Theorem, Lead sentence
Toda's theorem is a result in computational complexity theory that was proven by Seinosuke Toda in his paper "PP is as Hard as the
Valiant-Vazirani theorem, Wikipedia
PCP theorem, Wikipedia
Includes: PCP Theorem, Lead sentenceQuote, Includes: PCP Theorem, Lead sentence
In computational complexity theory, the PCP theorem (also known as the PCP characterization theorem) states that every decision pr
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.