Matches in DBpedia 2014 for { <http://dbpedia.org/resource/PCP_theorem> ?p ?o. }
Showing items 1 to 29 of
29
with 100 items per page.
- PCP_theorem abstract "In computational complexity theory, the PCP theorem (also known as the PCP Characterization Theorem) states that every decision problem in the NP complexity class has probabilistically checkable proofs (proofs that can be checked by a randomized algorithm) of constant query complexity and logarithmic randomness complexity (uses a logarithmic number of random bits).The PCP theorem says that for some universal constant K, for every n, any mathematical proof of length n can be rewritten as a different proof of length poly(n) that is formally verifiable with 99% accuracy by a randomized algorithm that inspects only K letters of that proof.The PCP theorem is the cornerstone of the theory of computational hardness of approximation, which investigates the inherent difficulty in designing efficient approximation algorithms for various optimization problems. It has been described by Ingo Wegener as "the most important result in complexity theory since Cook's Theorem" and by Oded Goldreich as "a culmination of a sequence of impressive works [...] rich in innovative ideas".The PCP theorem states that NP = PCP[O(log n), O(1)].↑ ↑".
- PCP_theorem wikiPageExternalLink 1996-jacm.pdf.
- PCP_theorem wikiPageID "3001241".
- PCP_theorem wikiPageRevisionID "603859867".
- PCP_theorem hasPhotoCollection PCP_theorem.
- PCP_theorem subject Category:Probabilistic_complexity_theory.
- PCP_theorem subject Category:Theorems_in_computational_complexity_theory.
- PCP_theorem type Abstraction100002137.
- PCP_theorem type Communication100033020.
- PCP_theorem type Message106598915.
- PCP_theorem type Proposition106750804.
- PCP_theorem type Statement106722453.
- PCP_theorem type Theorem106752293.
- PCP_theorem type TheoremsInDiscreteMathematics.
- PCP_theorem comment "In computational complexity theory, the PCP theorem (also known as the PCP Characterization Theorem) states that every decision problem in the NP complexity class has probabilistically checkable proofs (proofs that can be checked by a randomized algorithm) of constant query complexity and logarithmic randomness complexity (uses a logarithmic number of random bits).The PCP theorem says that for some universal constant K, for every n, any mathematical proof of length n can be rewritten as a different proof of length poly(n) that is formally verifiable with 99% accuracy by a randomized algorithm that inspects only K letters of that proof.The PCP theorem is the cornerstone of the theory of computational hardness of approximation, which investigates the inherent difficulty in designing efficient approximation algorithms for various optimization problems. ".
- PCP_theorem label "PCP theorem".
- PCP_theorem label "PCP-Theorem".
- PCP_theorem label "Teorema PCP".
- PCP_theorem label "Théorème PCP".
- PCP_theorem label "Теорема PCP".
- PCP_theorem sameAs PCP-Theorem.
- PCP_theorem sameAs Théorème_PCP.
- PCP_theorem sameAs Teorema_PCP.
- PCP_theorem sameAs m.08jszr.
- PCP_theorem sameAs Q1140200.
- PCP_theorem sameAs Q1140200.
- PCP_theorem sameAs PCP_theorem.
- PCP_theorem wasDerivedFrom PCP_theorem?oldid=603859867.
- PCP_theorem isPrimaryTopicOf PCP_theorem.