PCP theorem (original) (raw)
Das PCP-Theorem ist ein Satz aus der Komplexitätstheorie, einem Teilgebiet der Theoretischen Informatik.
| Property | Value |
|---|---|
| dbo:abstract | Das PCP-Theorem ist ein Satz aus der Komplexitätstheorie, einem Teilgebiet der Theoretischen Informatik. (de) 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 for a statement 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". (en) En théorie de la complexité, un domaine de l'informatique théorique, le théorème PCP (acronyme de l'anglais probabilistically checkable proof, qui peut se traduire en français par « preuve vérifiable en probabilité ») est une caractérisation de la classe NP dans le contexte d'un système de preuve interactive. Plus précisément, NP est la classe des problèmes de décision qui ont des preuves pouvant être vérifiées de façon probabiliste en ayant accès à un nombre constant de bits de la preuve et en utilisant un nombre logarithmique de bits aléatoires. Le théorème PCP est très important en informatique théorique : il apporte notamment de nombreux résultats sur la difficulté d'approximer les problèmes algorithmiques. (fr) Na teoria da complexidade computacional , o Teorema PCP afirma que todo problema de decisão na classe de complexidade NP tem (prova que pode ser checada por um ) de constante e complexidade logarítmica de aleatoriedade (usa um número logarítmico de bits aleatórios). P Teorema PCP diz que para alguma constante universal K, para cada n, qualquer prova matemática de tamanho n pode ser reescrita como uma prova diferente de tamanho poli(n) que é formalmente verificável com 99% de precisão por um que inspeciona apenas K letras daquela prova. O Teorema PCP é a ideia fundamental da teoria da computacional , que investiga a dificuldade inerente ao projeto eficiente de para vários . O Teorema PCP diz que: NP = [O(log n), O(1)]. (pt) В теории вычислительной сложности теорема PCP (англ. probabilistically checkable proofs — вероятностно проверяемое доказательство) утверждает, что любое решение задачи в классе сложности NP имеет вероятностно проверяемое доказательство (доказательство, которое можно проверить с помощью рандомизированного алгоритма) постоянной и логарифмической сложности случайности (использует логарифмическое число случайных бит). Теорема PCP является угловым камнем теории вычислительной сложности аппроксимации, которая исследует врождённую сложность при разработке эффективных аппроксимационных алгоритмов для различных задач оптимизации. Теорема отмечена как «самый важный результат в теории сложности со времён теоремы Кука» и как «кульминация цепи впечатляющих работ […], богатых новыми идеями». Есть и критика. Так, в книге Босса говорится: «В своё время это произвело фурор. Снежный ком публикаций нарастает до сих пор … Новое, по существу, определение NP-класса проливает дополнительный свет, однако без особых последствий. … Что касается самой PCP-системы, то она существенно опирается на волшебного Оракула, и поэтому не выпускает равенство NP = PCP[O(log n), O(1)] в практическую плоскость». Теорема PCP утверждает, что NP = PCP[O(log n), O(1)]. (ru) У теорії обчислювальної складності, PCP теорема стверджує, що будь-яка у NP має константної і . PCP теорема говорить, що для деякої універсальної константи K, для довільного n, всяке математичне доведення довжини n може бути переписано як інше доведення довжини poly(n), що може бути формально перевірене з 99% точністю ймовірнісним алгоритмом, що переглядає тільки K символів з цього доведення. PCP теорема є наріжним каменем теорії обчислювальної , що досліджує суттєву важкість у розробці ефективних для різних . PCP теорема формулюється у такий спосіб NP = [O(log n), O(1)]. (uk) |
| dbo:wikiPageExternalLink | http://groups.csail.mit.edu/cis/pubs/shafi/1996-jacm.pdf |
| dbo:wikiPageID | 3001241 (xsd:integer) |
| dbo:wikiPageLength | 12653 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1116511291 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Carsten_Lund dbr:Sanjeev_Arora dbr:NP_(complexity) dbc:Randomized_algorithms dbr:Approximation_algorithm dbr:Decision_problem dbr:Ingo_Wegener dbr:Interactive_proof_system dbr:QMA dbr:NLTS_Conjecture dbr:NP-hard dbr:Constraint_satisfaction_problem dbr:Cook–Levin_theorem dbr:László_Lovász dbr:Madhu_Sudan dbc:Theorems_in_computational_complexity_theory dbr:Complexity_class dbr:Computational_complexity_theory dbr:Hardness_of_approximation dbr:Probabilistically_checkable_proof dbr:Gödel_Prize dbr:Irit_Dinur dbr:Lattice_(group) dbr:Promise_problem dbr:Expander_graph dbr:Journal_of_the_ACM dbr:Uriel_Feige dbr:Mathematical_proof dbr:Lance_Fortnow dbr:Lattice_problems dbr:Dorit_Aharonov dbr:Mario_Szegedy dbr:Boolean_satisfiability_problem dbr:Oded_Goldreich dbr:Rajeev_Motwani dbr:Randomized_algorithm dbr:Shafi_Goldwasser dbr:Shmuel_Safra dbr:Computational_problems dbr:Maximum_independent_set dbr:Query_complexity dbr:NEXP dbr:Quantum_PCP_Conjecture |
| dbp:wikiPageUsesTemplate | dbt:Citation dbt:Distinguish dbt:Harv dbt:Harvtxt dbt:Reflist dbt:Cite_check |
| dct:subject | dbc:Randomized_algorithms dbc:Theorems_in_computational_complexity_theory |
| rdf:type | owl:Thing yago:WikicatTheoremsInComputationalComplexityTheory yago:Abstraction100002137 yago:Communication100033020 yago:Message106598915 yago:Proposition106750804 yago:Statement106722453 yago:Theorem106752293 |
| rdfs:comment | Das PCP-Theorem ist ein Satz aus der Komplexitätstheorie, einem Teilgebiet der Theoretischen Informatik. (de) У теорії обчислювальної складності, PCP теорема стверджує, що будь-яка у NP має константної і . PCP теорема говорить, що для деякої універсальної константи K, для довільного n, всяке математичне доведення довжини n може бути переписано як інше доведення довжини poly(n), що може бути формально перевірене з 99% точністю ймовірнісним алгоритмом, що переглядає тільки K символів з цього доведення. PCP теорема є наріжним каменем теорії обчислювальної , що досліджує суттєву важкість у розробці ефективних для різних . PCP теорема формулюється у такий спосіб NP = [O(log n), O(1)]. (uk) 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). (en) En théorie de la complexité, un domaine de l'informatique théorique, le théorème PCP (acronyme de l'anglais probabilistically checkable proof, qui peut se traduire en français par « preuve vérifiable en probabilité ») est une caractérisation de la classe NP dans le contexte d'un système de preuve interactive. Plus précisément, NP est la classe des problèmes de décision qui ont des preuves pouvant être vérifiées de façon probabiliste en ayant accès à un nombre constant de bits de la preuve et en utilisant un nombre logarithmique de bits aléatoires. (fr) Na teoria da complexidade computacional , o Teorema PCP afirma que todo problema de decisão na classe de complexidade NP tem (prova que pode ser checada por um ) de constante e complexidade logarítmica de aleatoriedade (usa um número logarítmico de bits aleatórios). P Teorema PCP diz que para alguma constante universal K, para cada n, qualquer prova matemática de tamanho n pode ser reescrita como uma prova diferente de tamanho poli(n) que é formalmente verificável com 99% de precisão por um que inspeciona apenas K letras daquela prova. O Teorema PCP diz que: NP = [O(log n), O(1)]. (pt) В теории вычислительной сложности теорема PCP (англ. probabilistically checkable proofs — вероятностно проверяемое доказательство) утверждает, что любое решение задачи в классе сложности NP имеет вероятностно проверяемое доказательство (доказательство, которое можно проверить с помощью рандомизированного алгоритма) постоянной и логарифмической сложности случайности (использует логарифмическое число случайных бит). Теорема PCP утверждает, что NP = PCP[O(log n), O(1)]. (ru) |
| rdfs:label | PCP-Theorem (de) Théorème PCP (fr) PCP theorem (en) Теорема PCP (ru) Teorema PCP (pt) PCP-теорема (uk) |
| owl:differentFrom | dbr:Post_correspondence_problem |
| owl:sameAs | freebase:PCP theorem yago-res:PCP theorem wikidata:PCP theorem dbpedia-de:PCP theorem dbpedia-fr:PCP theorem dbpedia-he:PCP theorem dbpedia-pt:PCP theorem dbpedia-ru:PCP theorem dbpedia-uk:PCP theorem https://global.dbpedia.org/id/C4RM |
| prov:wasDerivedFrom | wikipedia-en:PCP_theorem?oldid=1116511291&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:PCP_theorem |
| is dbo:knownFor of | dbr:Sanjeev_Arora |
| is dbo:wikiPageDisambiguates of | dbr:PCP |
| is dbo:wikiPageRedirects of | dbr:PCP_Theorem dbr:PCP_Characterization_Theorem dbr:PCP_characterization_theorem dbr:QPCP_theorem dbr:Quantum_PCP_theorem dbr:Probabilistically_checkable_proof_theorem |
| is dbo:wikiPageWikiLink of | dbr:Sanjeev_Arora dbr:List_of_University_of_California,_Berkeley_alumni dbr:List_of_computer_scientists dbr:MAX-3SAT dbr:Approximation_algorithm dbr:List_of_important_publications_in_theoretical_computer_science dbr:Vertex_cover dbr:Interactive_proof_system dbr:(SAT,_ε-UNSAT) dbr:Small-bias_sample_space dbr:Computers_and_Intractability dbr:Hardness_of_approximation dbr:PCP dbr:Probabilistically_checkable_proof dbr:Gödel_Prize dbr:Irit_Dinur dbr:Karloff–Zwick_algorithm dbr:Expander_graph dbr:Uriel_Feige dbr:Johan_Håstad dbr:Boolean_satisfiability_algorithm_heuristics dbr:Rajeev_Motwani dbr:SNP_(complexity) dbr:Shmuel_Safra dbr:List_of_theorems dbr:Ruzsa–Szemerédi_problem dbr:PCP_Theorem dbr:PCP_Characterization_Theorem dbr:PCP_characterization_theorem dbr:QPCP_theorem dbr:Quantum_PCP_theorem dbr:Probabilistically_checkable_proof_theorem |
| is dbp:knownFor of | dbr:Sanjeev_Arora |
| is owl:differentFrom of | dbr:Post_correspondence_problem |
| is foaf:primaryTopic of | wikipedia-en:PCP_theorem |