Matches in DBpedia 2015-10 for { <http://dbpedia.org/resource/PCP_theorem> ?p ?o }
Showing triples 1 to 77 of
77
with 100 triples 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".".
- PCP_theorem wikiPageExternalLink 1996-jacm.pdf.
- PCP_theorem wikiPageID "3001241".
- PCP_theorem wikiPageLength "10193".
- PCP_theorem wikiPageOutDegree "47".
- PCP_theorem wikiPageRevisionID "666470723".
- PCP_theorem wikiPageWikiLink Approximation_algorithm.
- PCP_theorem wikiPageWikiLink Boolean_satisfiability_problem.
- PCP_theorem wikiPageWikiLink Carsten_Lund.
- PCP_theorem wikiPageWikiLink Category:Probabilistic_complexity_theory.
- PCP_theorem wikiPageWikiLink Category:Theorems_in_computational_complexity_theory.
- PCP_theorem wikiPageWikiLink Complexity_class.
- PCP_theorem wikiPageWikiLink Computational_complexity_theory.
- PCP_theorem wikiPageWikiLink Computational_problem.
- PCP_theorem wikiPageWikiLink Computational_problems.
- PCP_theorem wikiPageWikiLink Constraint_satisfaction_problem.
- PCP_theorem wikiPageWikiLink Cooks_Theorem.
- PCP_theorem wikiPageWikiLink Cook–Levin_theorem.
- PCP_theorem wikiPageWikiLink Decision_problem.
- PCP_theorem wikiPageWikiLink Decision_tree_model.
- PCP_theorem wikiPageWikiLink Dorit_Aharonov.
- PCP_theorem wikiPageWikiLink Expander_graph.
- PCP_theorem wikiPageWikiLink Gödel_Prize.
- PCP_theorem wikiPageWikiLink Hardness_of_approximation.
- PCP_theorem wikiPageWikiLink Independent_set_(graph_theory).
- PCP_theorem wikiPageWikiLink Ingo_Wegener.
- PCP_theorem wikiPageWikiLink Interactive_proof_system.
- PCP_theorem wikiPageWikiLink Irit_Dinur.
- PCP_theorem wikiPageWikiLink Journal_of_the_ACM.
- PCP_theorem wikiPageWikiLink Lance_Fortnow.
- PCP_theorem wikiPageWikiLink Lattice_(group).
- PCP_theorem wikiPageWikiLink Lattice_problem.
- PCP_theorem wikiPageWikiLink Lattice_problems.
- PCP_theorem wikiPageWikiLink László_Lovász.
- PCP_theorem wikiPageWikiLink Madhu_Sudan.
- PCP_theorem wikiPageWikiLink Mario_Szegedy.
- PCP_theorem wikiPageWikiLink Mathematical_proof.
- PCP_theorem wikiPageWikiLink Maximum_independent_set.
- PCP_theorem wikiPageWikiLink NEXP.
- PCP_theorem wikiPageWikiLink NEXPTIME.
- PCP_theorem wikiPageWikiLink NP-hard.
- PCP_theorem wikiPageWikiLink NP-hardness.
- PCP_theorem wikiPageWikiLink NP_(complexity).
- PCP_theorem wikiPageWikiLink Oded_Goldreich.
- PCP_theorem wikiPageWikiLink Probabilistically_checkable_proof.
- PCP_theorem wikiPageWikiLink Query_complexity.
- PCP_theorem wikiPageWikiLink Rajeev_Motwani.
- PCP_theorem wikiPageWikiLink Randomized_algorithm.
- PCP_theorem wikiPageWikiLink Sanjeev_Arora.
- PCP_theorem wikiPageWikiLink Shafi_Goldwasser.
- PCP_theorem wikiPageWikiLink Shmuel_Safra.
- PCP_theorem wikiPageWikiLink Uriel_Feige.
- PCP_theorem wikiPageWikiLinkText "PCP theorem".
- PCP_theorem wikiPageWikiLinkText "probabilistically checkable proofs".
- PCP_theorem hasPhotoCollection PCP_theorem.
- PCP_theorem wikiPageUsesTemplate Template:Citation.
- PCP_theorem wikiPageUsesTemplate Template:Confusion.
- PCP_theorem wikiPageUsesTemplate Template:Harv.
- PCP_theorem wikiPageUsesTemplate Template:Harvtxt.
- PCP_theorem wikiPageUsesTemplate Template:Reflist.
- PCP_theorem subject Category:Probabilistic_complexity_theory.
- PCP_theorem subject Category:Theorems_in_computational_complexity_theory.
- PCP_theorem type Theorem.
- PCP_theorem type Thing.
- 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 differentFrom Post_correspondence_problem.
- 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 Теорема_PCP.
- PCP_theorem sameAs PCP-теорема.
- PCP_theorem sameAs Q1140200.
- PCP_theorem sameAs Q1140200.
- PCP_theorem wasDerivedFrom PCP_theorem?oldid=666470723.
- PCP_theorem isPrimaryTopicOf PCP_theorem.