Live briefing
Everything about PCP theorem
Theorem in computational complexity theory
In computational complexity theory, the PCP theorem states that every decision problem in the NP complexity class has probabilistically checkable proofs of constant query complexity and logarithmic randomness complexity. Wikipedia →
🧠Start here: a 6-step reading path
- Read the overview: PCP theoremA 5-minute orientation
- Skim a recent paper: Theoretical Base of Pseudo Chemical Potential (PCP) MethodInfluential work since 2022
- Pick up a classic book: Introduction to automata theory, languages, and computationThe most-reprinted book on the subject
- Read the landmark paper: The PCP theorem by gap amplificationCited 284 times
- Go sideways: Probabilistically checkable proofA closely related topic
- Go sideways: Interactive proof systemA closely related topic
đź“– Definitions
No dictionary entry for this exact phrase.
🗂️ The subject at a glance
🏆 Landmark papers (most cited)
The PCP theorem by gap amplification
Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem
A Combinatorial Consistency Lemma with Application to Proving the PCP Theorem
On Dinur’s proof of the PCP theorem
Logical strength of complexity theory and a formalization of the PCP theorem in bounded arithmetic
Transparent Long Proofs: A First PCP Theorem for NPR
The PCP Theorem for NP Over the Reals
Quantum Information and the PCP Theorem
🆕 Influential since 2022
đź“š Books worth reading
Introduction to automata theory, languages, and computationJohn E. Hopcroft, Jeffrey D. Ullman · 1979
Lectures on proof verification and approximation algorithmsErnst W. Mayr, Angelika Steger · 1998
Randomization and approximation techniques in computer scienceRANDOM '97 (1997 Bologna, Italy) · 1997
Ranked by number of editions on Open Library, a rough measure of how lasting a book is.
đź”— Related topics
- Probabilistically checkable proof In computational complexity theory, a probabilistically checkable proof (PCP) is a type of proof that can be checked by a randomized algorithm using a…
- Interactive proof system In computational complexity theory, an interactive proof system is an abstract machine that models computation as the exchange of messages between two…
- Arthur–Merlin protocol In computational complexity theory, an Arthur–Merlin protocol, introduced by Babai (1985), is an interactive proof system in which the verifier's coin…
- NEXPTIME In computational complexity theory, the complexity class NEXPTIME (sometimes called NEXP) is the set of decision problems that can be solved by a non-determinis…
- MAX-3SAT MAX-3SAT is a problem in the computational complexity subfield of computer science. It generalises the Boolean satisfiability problem (SAT) which is a…
- Karp–Lipton theorem In complexity theory, the Karp–Lipton theorem states that if the Boolean satisfiability problem (SAT) can be solved by Boolean circuits with a polynomial…
- NLTS conjecture In quantum information theory, the no low-energy trivial state (NLTS) conjecture is a lower bound on the complexity of certain classes of quantum states…
- P (complexity) In computational complexity theory, P, also known as PTIME or DTIME(nO(1)), is a fundamental complexity class. It contains all decision problems that can…