Matches in DBpedia 2014 for { <http://dbpedia.org/resource/Probabilistically_checkable_proof> ?p ?o. }
Showing items 1 to 28 of
28
with 100 items per page.
- Probabilistically_checkable_proof abstract "In computational complexity theory, a probabilistically checkable proof (PCP) is a type of proof that can be checked by a randomized algorithm using a bounded amount of randomness and reading a bounded number of bits of the proof. The algorithm is then required to accept correct proofs and reject incorrect proofs with very high probability. A standard proof (or certificate), as used in the verifier-based definition of the complexity class NP, also satisfies these requirements, since the checking procedure deterministically reads the whole proof, always accepts correct proofs and rejects incorrect proofs. However, what makes them interesting is the existence of probabilistically checkable proofs that can be checked by reading only a few bits of the proof using randomness in an essential way.Probabilistically checkable proofs give rise to many complexity classes depending on the number of queries required and the amount of randomness used. The class PCP[r(n),q(n)] refers to the set of decision problems that have probabilistically checkable proofs that can be verified in polynomial time using at most r(n) random bits and by reading at most q(n) bits of the proof. Unless specified otherwise, correct proofs should always be accepted, and incorrect proofs should be rejected with probability greater than 1/2. The PCP theorem, a major result in computational complexity theory, states that PCP[O(log n),O(1)] = NP.The complexity class PCP is the class of decision problems that have probabilistically checkable proofs with completeness 1, soundness α < 1, randomness complexity O(log n) and query complexity O(1).[citation needed]".
- Probabilistically_checkable_proof wikiPageExternalLink pcp-course.html.
- Probabilistically_checkable_proof wikiPageExternalLink 05au.
- Probabilistically_checkable_proof wikiPageExternalLink pcp-history.pdf.
- Probabilistically_checkable_proof wikiPageID "504509".
- Probabilistically_checkable_proof wikiPageRevisionID "549821455".
- Probabilistically_checkable_proof hasPhotoCollection Probabilistically_checkable_proof.
- Probabilistically_checkable_proof subject Category:Mathematical_proofs.
- Probabilistically_checkable_proof subject Category:Probabilistic_complexity_theory.
- Probabilistically_checkable_proof type Abstraction100002137.
- Probabilistically_checkable_proof type Argument106648724.
- Probabilistically_checkable_proof type Communication100033020.
- Probabilistically_checkable_proof type Evidence106643408.
- Probabilistically_checkable_proof type Indication106797169.
- Probabilistically_checkable_proof type MathematicalProof106647864.
- Probabilistically_checkable_proof type MathematicalProofs.
- Probabilistically_checkable_proof type Proof106647614.
- Probabilistically_checkable_proof comment "In computational complexity theory, a probabilistically checkable proof (PCP) is a type of proof that can be checked by a randomized algorithm using a bounded amount of randomness and reading a bounded number of bits of the proof. The algorithm is then required to accept correct proofs and reject incorrect proofs with very high probability.".
- Probabilistically_checkable_proof label "PCP (計算複雑性理論)".
- Probabilistically_checkable_proof label "Probabilistically checkable proof".
- Probabilistically_checkable_proof sameAs PCP_(計算複雑性理論).
- Probabilistically_checkable_proof sameAs PCP_(복잡도).
- Probabilistically_checkable_proof sameAs m.02jcqc.
- Probabilistically_checkable_proof sameAs Q841495.
- Probabilistically_checkable_proof sameAs Q841495.
- Probabilistically_checkable_proof sameAs Probabilistically_checkable_proof.
- Probabilistically_checkable_proof wasDerivedFrom Probabilistically_checkable_proof?oldid=549821455.
- Probabilistically_checkable_proof isPrimaryTopicOf Probabilistically_checkable_proof.