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).
| Attributes | Values |
|---|
| rdf:type
| |
| rdfs:label
| - PCP-Theorem (de)
- Théorème PCP (fr)
- PCP theorem (en)
- Теорема PCP (ru)
- Teorema PCP (pt)
- PCP-теорема (uk)
|
| 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)
|
| differentFrom
| |
| dcterms:subject
| |
| Wikipage page ID
| |
| Wikipage revision ID
| |
| Link from a Wikipage to another Wikipage
| |
| Link from a Wikipage to an external page
| |
| sameAs
| |
| dbp:wikiPageUsesTemplate
| |
| has 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)
|
| prov:wasDerivedFrom
| |
| page length (characters) of wiki page
| |
| foaf:isPrimaryTopicOf
| |
| is differentFrom
of | |
| is Link from a Wikipage to another Wikipage
of | |
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)