. . "1116511291"^^ . . . . . . "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 [\u2026] rich in innovative ideas\"."@en . "3001241"^^ . . . . . . . . "Th\u00E9or\u00E8me PCP"@fr . . . . . . . . . "Na teoria da complexidade computacional , o Teorema PCP afirma que todo problema de decis\u00E3o na classe de complexidade NP tem (prova que pode ser checada por um ) de constante e complexidade logar\u00EDtmica de aleatoriedade (usa um n\u00FAmero logar\u00EDtmico de bits aleat\u00F3rios). P Teorema PCP diz que para alguma constante universal K, para cada n, qualquer prova matem\u00E1tica de tamanho n pode ser reescrita como uma prova diferente de tamanho poli(n) que \u00E9 formalmente verific\u00E1vel com 99% de precis\u00E3o por um que inspeciona apenas K letras daquela prova. O Teorema PCP \u00E9 a ideia fundamental da teoria da computacional , que investiga a dificuldade inerente ao projeto eficiente de para v\u00E1rios . O Teorema PCP diz que: NP = [O(log n), O(1)]."@pt . . . . . "Das PCP-Theorem ist ein Satz aus der Komplexit\u00E4tstheorie, einem Teilgebiet der Theoretischen Informatik."@de . . "\u0423 \u0442\u0435\u043E\u0440\u0456\u0457 \u043E\u0431\u0447\u0438\u0441\u043B\u044E\u0432\u0430\u043B\u044C\u043D\u043E\u0457 \u0441\u043A\u043B\u0430\u0434\u043D\u043E\u0441\u0442\u0456, PCP \u0442\u0435\u043E\u0440\u0435\u043C\u0430 \u0441\u0442\u0432\u0435\u0440\u0434\u0436\u0443\u0454, \u0449\u043E \u0431\u0443\u0434\u044C-\u044F\u043A\u0430 \u0443 NP \u043C\u0430\u0454 \u043A\u043E\u043D\u0441\u0442\u0430\u043D\u0442\u043D\u043E\u0457 \u0456 . PCP \u0442\u0435\u043E\u0440\u0435\u043C\u0430 \u0433\u043E\u0432\u043E\u0440\u0438\u0442\u044C, \u0449\u043E \u0434\u043B\u044F \u0434\u0435\u044F\u043A\u043E\u0457 \u0443\u043D\u0456\u0432\u0435\u0440\u0441\u0430\u043B\u044C\u043D\u043E\u0457 \u043A\u043E\u043D\u0441\u0442\u0430\u043D\u0442\u0438 K, \u0434\u043B\u044F \u0434\u043E\u0432\u0456\u043B\u044C\u043D\u043E\u0433\u043E n, \u0432\u0441\u044F\u043A\u0435 \u043C\u0430\u0442\u0435\u043C\u0430\u0442\u0438\u0447\u043D\u0435 \u0434\u043E\u0432\u0435\u0434\u0435\u043D\u043D\u044F \u0434\u043E\u0432\u0436\u0438\u043D\u0438 n \u043C\u043E\u0436\u0435 \u0431\u0443\u0442\u0438 \u043F\u0435\u0440\u0435\u043F\u0438\u0441\u0430\u043D\u043E \u044F\u043A \u0456\u043D\u0448\u0435 \u0434\u043E\u0432\u0435\u0434\u0435\u043D\u043D\u044F \u0434\u043E\u0432\u0436\u0438\u043D\u0438 poly(n), \u0449\u043E \u043C\u043E\u0436\u0435 \u0431\u0443\u0442\u0438 \u0444\u043E\u0440\u043C\u0430\u043B\u044C\u043D\u043E \u043F\u0435\u0440\u0435\u0432\u0456\u0440\u0435\u043D\u0435 \u0437 99% \u0442\u043E\u0447\u043D\u0456\u0441\u0442\u044E \u0439\u043C\u043E\u0432\u0456\u0440\u043D\u0456\u0441\u043D\u0438\u043C \u0430\u043B\u0433\u043E\u0440\u0438\u0442\u043C\u043E\u043C, \u0449\u043E \u043F\u0435\u0440\u0435\u0433\u043B\u044F\u0434\u0430\u0454 \u0442\u0456\u043B\u044C\u043A\u0438 K \u0441\u0438\u043C\u0432\u043E\u043B\u0456\u0432 \u0437 \u0446\u044C\u043E\u0433\u043E \u0434\u043E\u0432\u0435\u0434\u0435\u043D\u043D\u044F. PCP \u0442\u0435\u043E\u0440\u0435\u043C\u0430 \u0454 \u043D\u0430\u0440\u0456\u0436\u043D\u0438\u043C \u043A\u0430\u043C\u0435\u043D\u0435\u043C \u0442\u0435\u043E\u0440\u0456\u0457 \u043E\u0431\u0447\u0438\u0441\u043B\u044E\u0432\u0430\u043B\u044C\u043D\u043E\u0457 , \u0449\u043E \u0434\u043E\u0441\u043B\u0456\u0434\u0436\u0443\u0454 \u0441\u0443\u0442\u0442\u0454\u0432\u0443 \u0432\u0430\u0436\u043A\u0456\u0441\u0442\u044C \u0443 \u0440\u043E\u0437\u0440\u043E\u0431\u0446\u0456 \u0435\u0444\u0435\u043A\u0442\u0438\u0432\u043D\u0438\u0445 \u0434\u043B\u044F \u0440\u0456\u0437\u043D\u0438\u0445 . PCP \u0442\u0435\u043E\u0440\u0435\u043C\u0430 \u0444\u043E\u0440\u043C\u0443\u043B\u044E\u0454\u0442\u044C\u0441\u044F \u0443 \u0442\u0430\u043A\u0438\u0439 \u0441\u043F\u043E\u0441\u0456\u0431 NP = [O(log n), O(1)]."@uk . . . . "\u0423 \u0442\u0435\u043E\u0440\u0456\u0457 \u043E\u0431\u0447\u0438\u0441\u043B\u044E\u0432\u0430\u043B\u044C\u043D\u043E\u0457 \u0441\u043A\u043B\u0430\u0434\u043D\u043E\u0441\u0442\u0456, PCP \u0442\u0435\u043E\u0440\u0435\u043C\u0430 \u0441\u0442\u0432\u0435\u0440\u0434\u0436\u0443\u0454, \u0449\u043E \u0431\u0443\u0434\u044C-\u044F\u043A\u0430 \u0443 NP \u043C\u0430\u0454 \u043A\u043E\u043D\u0441\u0442\u0430\u043D\u0442\u043D\u043E\u0457 \u0456 . PCP \u0442\u0435\u043E\u0440\u0435\u043C\u0430 \u0433\u043E\u0432\u043E\u0440\u0438\u0442\u044C, \u0449\u043E \u0434\u043B\u044F \u0434\u0435\u044F\u043A\u043E\u0457 \u0443\u043D\u0456\u0432\u0435\u0440\u0441\u0430\u043B\u044C\u043D\u043E\u0457 \u043A\u043E\u043D\u0441\u0442\u0430\u043D\u0442\u0438 K, \u0434\u043B\u044F \u0434\u043E\u0432\u0456\u043B\u044C\u043D\u043E\u0433\u043E n, \u0432\u0441\u044F\u043A\u0435 \u043C\u0430\u0442\u0435\u043C\u0430\u0442\u0438\u0447\u043D\u0435 \u0434\u043E\u0432\u0435\u0434\u0435\u043D\u043D\u044F \u0434\u043E\u0432\u0436\u0438\u043D\u0438 n \u043C\u043E\u0436\u0435 \u0431\u0443\u0442\u0438 \u043F\u0435\u0440\u0435\u043F\u0438\u0441\u0430\u043D\u043E \u044F\u043A \u0456\u043D\u0448\u0435 \u0434\u043E\u0432\u0435\u0434\u0435\u043D\u043D\u044F \u0434\u043E\u0432\u0436\u0438\u043D\u0438 poly(n), \u0449\u043E \u043C\u043E\u0436\u0435 \u0431\u0443\u0442\u0438 \u0444\u043E\u0440\u043C\u0430\u043B\u044C\u043D\u043E \u043F\u0435\u0440\u0435\u0432\u0456\u0440\u0435\u043D\u0435 \u0437 99% \u0442\u043E\u0447\u043D\u0456\u0441\u0442\u044E \u0439\u043C\u043E\u0432\u0456\u0440\u043D\u0456\u0441\u043D\u0438\u043C \u0430\u043B\u0433\u043E\u0440\u0438\u0442\u043C\u043E\u043C, \u0449\u043E \u043F\u0435\u0440\u0435\u0433\u043B\u044F\u0434\u0430\u0454 \u0442\u0456\u043B\u044C\u043A\u0438 K \u0441\u0438\u043C\u0432\u043E\u043B\u0456\u0432 \u0437 \u0446\u044C\u043E\u0433\u043E \u0434\u043E\u0432\u0435\u0434\u0435\u043D\u043D\u044F. PCP \u0442\u0435\u043E\u0440\u0435\u043C\u0430 \u0454 \u043D\u0430\u0440\u0456\u0436\u043D\u0438\u043C \u043A\u0430\u043C\u0435\u043D\u0435\u043C \u0442\u0435\u043E\u0440\u0456\u0457 \u043E\u0431\u0447\u0438\u0441\u043B\u044E\u0432\u0430\u043B\u044C\u043D\u043E\u0457 , \u0449\u043E \u0434\u043E\u0441\u043B\u0456\u0434\u0436\u0443\u0454 \u0441\u0443\u0442\u0442\u0454\u0432\u0443 \u0432\u0430\u0436\u043A\u0456\u0441\u0442\u044C \u0443 \u0440\u043E\u0437\u0440\u043E\u0431\u0446\u0456 \u0435\u0444\u0435\u043A\u0442\u0438\u0432\u043D\u0438\u0445 \u0434\u043B\u044F \u0440\u0456\u0437\u043D\u0438\u0445 . PCP \u0442\u0435\u043E\u0440\u0435\u043C\u0430 \u0444\u043E\u0440\u043C\u0443\u043B\u044E\u0454\u0442\u044C\u0441\u044F \u0443 \u0442\u0430\u043A\u0438\u0439 \u0441\u043F\u043E\u0441\u0456\u0431 NP = [O(log n), O(1)]."@uk . "En th\u00E9orie de la complexit\u00E9, un domaine de l'informatique th\u00E9orique, le th\u00E9or\u00E8me PCP (acronyme de l'anglais probabilistically checkable proof, qui peut se traduire en fran\u00E7ais par \u00AB preuve v\u00E9rifiable en probabilit\u00E9 \u00BB) est une caract\u00E9risation de la classe NP dans le contexte d'un syst\u00E8me de preuve interactive. Plus pr\u00E9cis\u00E9ment, NP est la classe des probl\u00E8mes de d\u00E9cision qui ont des preuves pouvant \u00EAtre v\u00E9rifi\u00E9es de fa\u00E7on probabiliste en ayant acc\u00E8s \u00E0 un nombre constant de bits de la preuve et en utilisant un nombre logarithmique de bits al\u00E9atoires."@fr . "Teorema PCP"@pt . . . . . . . . "12653"^^ . . . "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 . "\u0412 \u0442\u0435\u043E\u0440\u0438\u0438 \u0432\u044B\u0447\u0438\u0441\u043B\u0438\u0442\u0435\u043B\u044C\u043D\u043E\u0439 \u0441\u043B\u043E\u0436\u043D\u043E\u0441\u0442\u0438 \u0442\u0435\u043E\u0440\u0435\u043C\u0430 PCP (\u0430\u043D\u0433\u043B. probabilistically checkable proofs \u2014 \u0432\u0435\u0440\u043E\u044F\u0442\u043D\u043E\u0441\u0442\u043D\u043E \u043F\u0440\u043E\u0432\u0435\u0440\u044F\u0435\u043C\u043E\u0435 \u0434\u043E\u043A\u0430\u0437\u0430\u0442\u0435\u043B\u044C\u0441\u0442\u0432\u043E) \u0443\u0442\u0432\u0435\u0440\u0436\u0434\u0430\u0435\u0442, \u0447\u0442\u043E \u043B\u044E\u0431\u043E\u0435 \u0440\u0435\u0448\u0435\u043D\u0438\u0435 \u0437\u0430\u0434\u0430\u0447\u0438 \u0432 \u043A\u043B\u0430\u0441\u0441\u0435 \u0441\u043B\u043E\u0436\u043D\u043E\u0441\u0442\u0438 NP \u0438\u043C\u0435\u0435\u0442 \u0432\u0435\u0440\u043E\u044F\u0442\u043D\u043E\u0441\u0442\u043D\u043E \u043F\u0440\u043E\u0432\u0435\u0440\u044F\u0435\u043C\u043E\u0435 \u0434\u043E\u043A\u0430\u0437\u0430\u0442\u0435\u043B\u044C\u0441\u0442\u0432\u043E (\u0434\u043E\u043A\u0430\u0437\u0430\u0442\u0435\u043B\u044C\u0441\u0442\u0432\u043E, \u043A\u043E\u0442\u043E\u0440\u043E\u0435 \u043C\u043E\u0436\u043D\u043E \u043F\u0440\u043E\u0432\u0435\u0440\u0438\u0442\u044C \u0441 \u043F\u043E\u043C\u043E\u0449\u044C\u044E \u0440\u0430\u043D\u0434\u043E\u043C\u0438\u0437\u0438\u0440\u043E\u0432\u0430\u043D\u043D\u043E\u0433\u043E \u0430\u043B\u0433\u043E\u0440\u0438\u0442\u043C\u0430) \u043F\u043E\u0441\u0442\u043E\u044F\u043D\u043D\u043E\u0439 \u0438 \u043B\u043E\u0433\u0430\u0440\u0438\u0444\u043C\u0438\u0447\u0435\u0441\u043A\u043E\u0439 \u0441\u043B\u043E\u0436\u043D\u043E\u0441\u0442\u0438 \u0441\u043B\u0443\u0447\u0430\u0439\u043D\u043E\u0441\u0442\u0438 (\u0438\u0441\u043F\u043E\u043B\u044C\u0437\u0443\u0435\u0442 \u043B\u043E\u0433\u0430\u0440\u0438\u0444\u043C\u0438\u0447\u0435\u0441\u043A\u043E\u0435 \u0447\u0438\u0441\u043B\u043E \u0441\u043B\u0443\u0447\u0430\u0439\u043D\u044B\u0445 \u0431\u0438\u0442). \u0422\u0435\u043E\u0440\u0435\u043C\u0430 PCP \u0443\u0442\u0432\u0435\u0440\u0436\u0434\u0430\u0435\u0442, \u0447\u0442\u043E NP = PCP[O(log n), O(1)]."@ru . . . . . . "PCP-Theorem"@de . . . "Na teoria da complexidade computacional , o Teorema PCP afirma que todo problema de decis\u00E3o na classe de complexidade NP tem (prova que pode ser checada por um ) de constante e complexidade logar\u00EDtmica de aleatoriedade (usa um n\u00FAmero logar\u00EDtmico de bits aleat\u00F3rios). P Teorema PCP diz que para alguma constante universal K, para cada n, qualquer prova matem\u00E1tica de tamanho n pode ser reescrita como uma prova diferente de tamanho poli(n) que \u00E9 formalmente verific\u00E1vel com 99% de precis\u00E3o por um que inspeciona apenas K letras daquela prova. O Teorema PCP diz que: NP = [O(log n), O(1)]."@pt . . "\u0412 \u0442\u0435\u043E\u0440\u0438\u0438 \u0432\u044B\u0447\u0438\u0441\u043B\u0438\u0442\u0435\u043B\u044C\u043D\u043E\u0439 \u0441\u043B\u043E\u0436\u043D\u043E\u0441\u0442\u0438 \u0442\u0435\u043E\u0440\u0435\u043C\u0430 PCP (\u0430\u043D\u0433\u043B. probabilistically checkable proofs \u2014 \u0432\u0435\u0440\u043E\u044F\u0442\u043D\u043E\u0441\u0442\u043D\u043E \u043F\u0440\u043E\u0432\u0435\u0440\u044F\u0435\u043C\u043E\u0435 \u0434\u043E\u043A\u0430\u0437\u0430\u0442\u0435\u043B\u044C\u0441\u0442\u0432\u043E) \u0443\u0442\u0432\u0435\u0440\u0436\u0434\u0430\u0435\u0442, \u0447\u0442\u043E \u043B\u044E\u0431\u043E\u0435 \u0440\u0435\u0448\u0435\u043D\u0438\u0435 \u0437\u0430\u0434\u0430\u0447\u0438 \u0432 \u043A\u043B\u0430\u0441\u0441\u0435 \u0441\u043B\u043E\u0436\u043D\u043E\u0441\u0442\u0438 NP \u0438\u043C\u0435\u0435\u0442 \u0432\u0435\u0440\u043E\u044F\u0442\u043D\u043E\u0441\u0442\u043D\u043E \u043F\u0440\u043E\u0432\u0435\u0440\u044F\u0435\u043C\u043E\u0435 \u0434\u043E\u043A\u0430\u0437\u0430\u0442\u0435\u043B\u044C\u0441\u0442\u0432\u043E (\u0434\u043E\u043A\u0430\u0437\u0430\u0442\u0435\u043B\u044C\u0441\u0442\u0432\u043E, \u043A\u043E\u0442\u043E\u0440\u043E\u0435 \u043C\u043E\u0436\u043D\u043E \u043F\u0440\u043E\u0432\u0435\u0440\u0438\u0442\u044C \u0441 \u043F\u043E\u043C\u043E\u0449\u044C\u044E \u0440\u0430\u043D\u0434\u043E\u043C\u0438\u0437\u0438\u0440\u043E\u0432\u0430\u043D\u043D\u043E\u0433\u043E \u0430\u043B\u0433\u043E\u0440\u0438\u0442\u043C\u0430) \u043F\u043E\u0441\u0442\u043E\u044F\u043D\u043D\u043E\u0439 \u0438 \u043B\u043E\u0433\u0430\u0440\u0438\u0444\u043C\u0438\u0447\u0435\u0441\u043A\u043E\u0439 \u0441\u043B\u043E\u0436\u043D\u043E\u0441\u0442\u0438 \u0441\u043B\u0443\u0447\u0430\u0439\u043D\u043E\u0441\u0442\u0438 (\u0438\u0441\u043F\u043E\u043B\u044C\u0437\u0443\u0435\u0442 \u043B\u043E\u0433\u0430\u0440\u0438\u0444\u043C\u0438\u0447\u0435\u0441\u043A\u043E\u0435 \u0447\u0438\u0441\u043B\u043E \u0441\u043B\u0443\u0447\u0430\u0439\u043D\u044B\u0445 \u0431\u0438\u0442). \u0422\u0435\u043E\u0440\u0435\u043C\u0430 PCP \u044F\u0432\u043B\u044F\u0435\u0442\u0441\u044F \u0443\u0433\u043B\u043E\u0432\u044B\u043C \u043A\u0430\u043C\u043D\u0435\u043C \u0442\u0435\u043E\u0440\u0438\u0438 \u0432\u044B\u0447\u0438\u0441\u043B\u0438\u0442\u0435\u043B\u044C\u043D\u043E\u0439 \u0441\u043B\u043E\u0436\u043D\u043E\u0441\u0442\u0438 \u0430\u043F\u043F\u0440\u043E\u043A\u0441\u0438\u043C\u0430\u0446\u0438\u0438, \u043A\u043E\u0442\u043E\u0440\u0430\u044F \u0438\u0441\u0441\u043B\u0435\u0434\u0443\u0435\u0442 \u0432\u0440\u043E\u0436\u0434\u0451\u043D\u043D\u0443\u044E \u0441\u043B\u043E\u0436\u043D\u043E\u0441\u0442\u044C \u043F\u0440\u0438 \u0440\u0430\u0437\u0440\u0430\u0431\u043E\u0442\u043A\u0435 \u044D\u0444\u0444\u0435\u043A\u0442\u0438\u0432\u043D\u044B\u0445 \u0430\u043F\u043F\u0440\u043E\u043A\u0441\u0438\u043C\u0430\u0446\u0438\u043E\u043D\u043D\u044B\u0445 \u0430\u043B\u0433\u043E\u0440\u0438\u0442\u043C\u043E\u0432 \u0434\u043B\u044F \u0440\u0430\u0437\u043B\u0438\u0447\u043D\u044B\u0445 \u0437\u0430\u0434\u0430\u0447 \u043E\u043F\u0442\u0438\u043C\u0438\u0437\u0430\u0446\u0438\u0438. \u0422\u0435\u043E\u0440\u0435\u043C\u0430 \u043E\u0442\u043C\u0435\u0447\u0435\u043D\u0430 \u043A\u0430\u043A \u00AB\u0441\u0430\u043C\u044B\u0439 \u0432\u0430\u0436\u043D\u044B\u0439 \u0440\u0435\u0437\u0443\u043B\u044C\u0442\u0430\u0442 \u0432 \u0442\u0435\u043E\u0440\u0438\u0438 \u0441\u043B\u043E\u0436\u043D\u043E\u0441\u0442\u0438 \u0441\u043E \u0432\u0440\u0435\u043C\u0451\u043D \u0442\u0435\u043E\u0440\u0435\u043C\u044B \u041A\u0443\u043A\u0430\u00BB \u0438 \u043A\u0430\u043A \u00AB\u043A\u0443\u043B\u044C\u043C\u0438\u043D\u0430\u0446\u0438\u044F \u0446\u0435\u043F\u0438 \u0432\u043F\u0435\u0447\u0430\u0442\u043B\u044F\u044E\u0449\u0438\u0445 \u0440\u0430\u0431\u043E\u0442 [\u2026], \u0431\u043E\u0433\u0430\u0442\u044B\u0445 \u043D\u043E\u0432\u044B\u043C\u0438 \u0438\u0434\u0435\u044F\u043C\u0438\u00BB. \u0415\u0441\u0442\u044C \u0438 \u043A\u0440\u0438\u0442\u0438\u043A\u0430. \u0422\u0430\u043A, \u0432 \u043A\u043D\u0438\u0433\u0435 \u0411\u043E\u0441\u0441\u0430 \u0433\u043E\u0432\u043E\u0440\u0438\u0442\u0441\u044F: \u00AB\u0412 \u0441\u0432\u043E\u0451 \u0432\u0440\u0435\u043C\u044F \u044D\u0442\u043E \u043F\u0440\u043E\u0438\u0437\u0432\u0435\u043B\u043E \u0444\u0443\u0440\u043E\u0440. \u0421\u043D\u0435\u0436\u043D\u044B\u0439 \u043A\u043E\u043C \u043F\u0443\u0431\u043B\u0438\u043A\u0430\u0446\u0438\u0439 \u043D\u0430\u0440\u0430\u0441\u0442\u0430\u0435\u0442 \u0434\u043E \u0441\u0438\u0445 \u043F\u043E\u0440 \u2026 \u041D\u043E\u0432\u043E\u0435, \u043F\u043E \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443, \u043E\u043F\u0440\u0435\u0434\u0435\u043B\u0435\u043D\u0438\u0435 NP-\u043A\u043B\u0430\u0441\u0441\u0430 \u043F\u0440\u043E\u043B\u0438\u0432\u0430\u0435\u0442 \u0434\u043E\u043F\u043E\u043B\u043D\u0438\u0442\u0435\u043B\u044C\u043D\u044B\u0439 \u0441\u0432\u0435\u0442, \u043E\u0434\u043D\u0430\u043A\u043E \u0431\u0435\u0437 \u043E\u0441\u043E\u0431\u044B\u0445 \u043F\u043E\u0441\u043B\u0435\u0434\u0441\u0442\u0432\u0438\u0439. \u2026 \u0427\u0442\u043E \u043A\u0430\u0441\u0430\u0435\u0442\u0441\u044F \u0441\u0430\u043C\u043E\u0439 PCP-\u0441\u0438\u0441\u0442\u0435\u043C\u044B, \u0442\u043E \u043E\u043D\u0430 \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0435\u043D\u043D\u043E \u043E\u043F\u0438\u0440\u0430\u0435\u0442\u0441\u044F \u043D\u0430 \u0432\u043E\u043B\u0448\u0435\u0431\u043D\u043E\u0433\u043E \u041E\u0440\u0430\u043A\u0443\u043B\u0430, \u0438 \u043F\u043E\u044D\u0442\u043E\u043C\u0443 \u043D\u0435 \u0432\u044B\u043F\u0443\u0441\u043A\u0430\u0435\u0442 \u0440\u0430\u0432\u0435\u043D\u0441\u0442\u0432\u043E NP = PCP[O(log n), O(1)] \u0432 \u043F\u0440\u0430\u043A\u0442\u0438\u0447\u0435\u0441\u043A\u0443\u044E \u043F\u043B\u043E\u0441\u043A\u043E\u0441\u0442\u044C\u00BB. \u0422\u0435\u043E\u0440\u0435\u043C\u0430 PCP \u0443\u0442\u0432\u0435\u0440\u0436\u0434\u0430\u0435\u0442, \u0447\u0442\u043E NP = PCP[O(log n), O(1)]."@ru . . . . "\u0422\u0435\u043E\u0440\u0435\u043C\u0430 PCP"@ru . . . . "PCP-\u0442\u0435\u043E\u0440\u0435\u043C\u0430"@uk . . "En th\u00E9orie de la complexit\u00E9, un domaine de l'informatique th\u00E9orique, le th\u00E9or\u00E8me PCP (acronyme de l'anglais probabilistically checkable proof, qui peut se traduire en fran\u00E7ais par \u00AB preuve v\u00E9rifiable en probabilit\u00E9 \u00BB) est une caract\u00E9risation de la classe NP dans le contexte d'un syst\u00E8me de preuve interactive. Plus pr\u00E9cis\u00E9ment, NP est la classe des probl\u00E8mes de d\u00E9cision qui ont des preuves pouvant \u00EAtre v\u00E9rifi\u00E9es de fa\u00E7on probabiliste en ayant acc\u00E8s \u00E0 un nombre constant de bits de la preuve et en utilisant un nombre logarithmique de bits al\u00E9atoires. Le th\u00E9or\u00E8me PCP est tr\u00E8s important en informatique th\u00E9orique : il apporte notamment de nombreux r\u00E9sultats sur la difficult\u00E9 d'approximer les probl\u00E8mes algorithmiques."@fr . . . . . . . . . . . . . . . . "Das PCP-Theorem ist ein Satz aus der Komplexit\u00E4tstheorie, einem Teilgebiet der Theoretischen Informatik."@de . . "PCP theorem"@en . . . .