This HTML5 document contains 94 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
dbpedia-dehttp://de.dbpedia.org/resource/
dctermshttp://purl.org/dc/terms/
yago-reshttp://yago-knowledge.org/resource/
dbohttp://dbpedia.org/ontology/
foafhttp://xmlns.com/foaf/0.1/
n7https://global.dbpedia.org/id/
dbpedia-hehttp://he.dbpedia.org/resource/
yagohttp://dbpedia.org/class/yago/
dbpedia-ruhttp://ru.dbpedia.org/resource/
dbthttp://dbpedia.org/resource/Template:
dbpedia-ukhttp://uk.dbpedia.org/resource/
rdfshttp://www.w3.org/2000/01/rdf-schema#
freebasehttp://rdf.freebase.com/ns/
dbpedia-pthttp://pt.dbpedia.org/resource/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
n19http://groups.csail.mit.edu/cis/pubs/shafi/
owlhttp://www.w3.org/2002/07/owl#
dbpedia-frhttp://fr.dbpedia.org/resource/
wikipedia-enhttp://en.wikipedia.org/wiki/
dbphttp://dbpedia.org/property/
provhttp://www.w3.org/ns/prov#
dbchttp://dbpedia.org/resource/Category:
xsdhhttp://www.w3.org/2001/XMLSchema#
wikidatahttp://www.wikidata.org/entity/
dbrhttp://dbpedia.org/resource/

Statements

Subject Item
dbr:PCP_theorem
rdf:type
yago:Theorem106752293 yago:Communication100033020 yago:WikicatTheoremsInComputationalComplexityTheory yago:Proposition106750804 yago:Abstraction100002137 yago:Message106598915 yago:Statement106722453 owl:Thing
rdfs:label
Théorème PCP Teorema PCP PCP-Theorem Теорема PCP PCP-теорема PCP theorem
rdfs:comment
Das PCP-Theorem ist ein Satz aus der Komplexitätstheorie, einem Teilgebiet der Theoretischen Informatik. У теорії обчислювальної складності, PCP теорема стверджує, що будь-яка у NP має константної і . PCP теорема говорить, що для деякої універсальної константи K, для довільного n, всяке математичне доведення довжини n може бути переписано як інше доведення довжини poly(n), що може бути формально перевірене з 99% точністю ймовірнісним алгоритмом, що переглядає тільки K символів з цього доведення. PCP теорема є наріжним каменем теорії обчислювальної , що досліджує суттєву важкість у розробці ефективних для різних . PCP теорема формулюється у такий спосіб NP = [O(log n), O(1)]. 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. 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). В теории вычислительной сложности теорема PCP (англ. probabilistically checkable proofs — вероятностно проверяемое доказательство) утверждает, что любое решение задачи в классе сложности NP имеет вероятностно проверяемое доказательство (доказательство, которое можно проверить с помощью рандомизированного алгоритма) постоянной и логарифмической сложности случайности (использует логарифмическое число случайных бит). Теорема PCP утверждает, что NP = PCP[O(log n), O(1)]. 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)].
owl:differentFrom
dbr:Post_correspondence_problem
dcterms:subject
dbc:Theorems_in_computational_complexity_theory dbc:Randomized_algorithms
dbo:wikiPageID
3001241
dbo:wikiPageRevisionID
1116511291
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory dbr:Interactive_proof_system dbr:Carsten_Lund dbr:NLTS_Conjecture dbr:Maximum_independent_set dbr:NP_(complexity) dbr:Journal_of_the_ACM dbr:Probabilistically_checkable_proof dbr:Hardness_of_approximation dbr:Computational_problems dbr:Promise_problem dbr:Mario_Szegedy dbr:Shafi_Goldwasser dbr:Uriel_Feige dbr:Irit_Dinur dbr:NP-hard dbr:László_Lovász dbr:Sanjeev_Arora dbr:Rajeev_Motwani dbr:Dorit_Aharonov dbr:Mathematical_proof dbr:Shmuel_Safra dbr:Lattice_problems dbr:Gödel_Prize dbr:Quantum_PCP_Conjecture dbc:Theorems_in_computational_complexity_theory dbr:Decision_problem dbr:Constraint_satisfaction_problem dbr:Cook–Levin_theorem dbr:Approximation_algorithm dbr:Query_complexity dbr:NEXP dbr:Complexity_class dbr:Boolean_satisfiability_problem dbr:Expander_graph dbr:Lattice_(group) dbr:Lance_Fortnow dbc:Randomized_algorithms dbr:Madhu_Sudan dbr:Oded_Goldreich dbr:Ingo_Wegener dbr:Randomized_algorithm dbr:QMA
dbo:wikiPageExternalLink
n19:1996-jacm.pdf
owl:sameAs
n7:C4RM dbpedia-he:משפט_PCP dbpedia-de:PCP-Theorem wikidata:Q1140200 dbpedia-ru:Теорема_PCP dbpedia-pt:Teorema_PCP freebase:m.08jszr dbpedia-uk:PCP-теорема yago-res:PCP_theorem dbpedia-fr:Théorème_PCP
dbp:wikiPageUsesTemplate
dbt:Citation dbt:Reflist dbt:Harvtxt dbt:Harv dbt:Distinguish dbt:Cite_check
dbo: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 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". 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)]. У теорії обчислювальної складності, PCP теорема стверджує, що будь-яка у NP має константної і . PCP теорема говорить, що для деякої універсальної константи K, для довільного n, всяке математичне доведення довжини n може бути переписано як інше доведення довжини poly(n), що може бути формально перевірене з 99% точністю ймовірнісним алгоритмом, що переглядає тільки K символів з цього доведення. PCP теорема є наріжним каменем теорії обчислювальної , що досліджує суттєву важкість у розробці ефективних для різних . PCP теорема формулюється у такий спосіб NP = [O(log n), O(1)]. В теории вычислительной сложности теорема PCP (англ. probabilistically checkable proofs — вероятностно проверяемое доказательство) утверждает, что любое решение задачи в классе сложности NP имеет вероятностно проверяемое доказательство (доказательство, которое можно проверить с помощью рандомизированного алгоритма) постоянной и логарифмической сложности случайности (использует логарифмическое число случайных бит). Теорема PCP является угловым камнем теории вычислительной сложности аппроксимации, которая исследует врождённую сложность при разработке эффективных аппроксимационных алгоритмов для различных задач оптимизации. Теорема отмечена как «самый важный результат в теории сложности со времён теоремы Кука» и как «кульминация цепи впечатляющих работ […], богатых новыми идеями». Есть и критика. Так, в книге Босса говорится: «В своё время это произвело фурор. Снежный ком публикаций нарастает до сих пор … Новое, по существу, определение NP-класса проливает дополнительный свет, однако без особых последствий. … Что касается самой PCP-системы, то она существенно опирается на волшебного Оракула, и поэтому не выпускает равенство NP = PCP[O(log n), O(1)] в практическую плоскость». Теорема PCP утверждает, что NP = PCP[O(log n), O(1)]. 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. Das PCP-Theorem ist ein Satz aus der Komplexitätstheorie, einem Teilgebiet der Theoretischen Informatik.
prov:wasDerivedFrom
wikipedia-en:PCP_theorem?oldid=1116511291&ns=0
dbo:wikiPageLength
12653
foaf:isPrimaryTopicOf
wikipedia-en:PCP_theorem