. . . "En th\u00E9orie de la complexit\u00E9, une preuve v\u00E9rifiable de mani\u00E8re probabiliste aussi appel\u00E9e preuve v\u00E9rifiable en probabilit\u00E9 ou PCP (pour Probabilistically checkable proof) est une preuve (certificat) qui peut \u00EAtre v\u00E9rifi\u00E9e par un algorithme probabiliste, en utilisant un certain nombre de bits al\u00E9atoires et en lisant un certain nombre de bits de la preuve. La classe PCP[r(n),q(n)] r\u00E9f\u00E8re \u00E0 l'ensemble des probl\u00E8mes de d\u00E9cision qui ont des preuves v\u00E9rifiables en temps polynomial avec au plus r(n) bits al\u00E9atoires et en lisant au plus q(n) bits de la preuve. Sauf mention, une preuve correcte est toujours accept\u00E9e ; une preuve incorrecte est rejet\u00E9e avec une probabilit\u00E9 sup\u00E9rieure ou \u00E9gale \u00E0 1/2."@fr . . . . . . . . . . . . . . . "Probabilistically checkable proof"@en . . . . . "En th\u00E9orie de la complexit\u00E9, une preuve v\u00E9rifiable de mani\u00E8re probabiliste aussi appel\u00E9e preuve v\u00E9rifiable en probabilit\u00E9 ou PCP (pour Probabilistically checkable proof) est une preuve (certificat) qui peut \u00EAtre v\u00E9rifi\u00E9e par un algorithme probabiliste, en utilisant un certain nombre de bits al\u00E9atoires et en lisant un certain nombre de bits de la preuve. La classe PCP[r(n),q(n)] r\u00E9f\u00E8re \u00E0 l'ensemble des probl\u00E8mes de d\u00E9cision qui ont des preuves v\u00E9rifiables en temps polynomial avec au plus r(n) bits al\u00E9atoires et en lisant au plus q(n) bits de la preuve. Sauf mention, une preuve correcte est toujours accept\u00E9e ; une preuve incorrecte est rejet\u00E9e avec une probabilit\u00E9 sup\u00E9rieure ou \u00E9gale \u00E0 1/2."@fr . "In computational complexity theory, a probabilistically checkable proof (PCP) is a type of proof that can be checked by a randomized algorithm using a bounded amount of randomness and reading a bounded number of bits of the proof. The algorithm is then required to accept correct proofs and reject incorrect proofs with very high probability. A standard proof (or certificate), as used in the verifier-based definition of the complexity class NP, also satisfies these requirements, since the checking procedure deterministically reads the whole proof, always accepts correct proofs and rejects incorrect proofs. However, what makes them interesting is the existence of probabilistically checkable proofs that can be checked by reading only a few bits of the proof using randomness in an essential way. Probabilistically checkable proofs give rise to many complexity classes depending on the number of queries required and the amount of randomness used. The class PCP[r(n),q(n)] refers to the set of decision problems that have probabilistically checkable proofs that can be verified in polynomial time using at most r(n) random bits and by reading at most q(n) bits of the proof. Unless specified otherwise, correct proofs should always be accepted, and incorrect proofs should be rejected with probability greater than 1/2. The PCP theorem, a major result in computational complexity theory, states that PCP[O(log n),O(1)] = NP."@en . "En teoria de la complexitat, un sistema de demostraci\u00F3 provable per probabilitat (o PCP per les sigles en angl\u00E8s probabilistically checkable proof) \u00E9s un tipus de prova que pot ser comprovada per un algorisme probabil\u00EDstic usant una quantitat fitada de aleatorietat i llegint una quantitat fitada de bits de la prova. Es requereix que l'algorisme accepti les proves correctes i rebutgi les incorrectes amb una probabilitat molt alta. Una prova est\u00E0ndard (o certificat), igual que el que es fa servir en la definici\u00F3 amb verificador de la classe NP, tamb\u00E9 satisf\u00E0 aquests requeriments, ja que el procediment de comprovaci\u00F3 de forma determinista llegeix la prova sencera, sempre accepta les proves correctes i rebutja les incorrectes. Aquest tipus de proves per probabilitat dona peu a diverses classes de complexitat depenent del nombre de preguntes que fan falta i la quantitat d'aleatorietat es fa servir. La classe PCP[r(n), q(n)] \u00E9s la classe de complexitat del conjunt de problemes de decisi\u00F3 que tenen proves provable per probabilitat en temps polin\u00F2mic usant com a molt r(n) bits aleatoris llegint com a molt q(n) bits de la demostraci\u00F3. Si no es diu el contrari, les demostracions correctes s'han d'acceptar sempre, i les incorrectes han de rebutjar-se amb una probabilitat m\u00E9s gran d'1/2."@ca . . "Provas verific\u00E1veis probabilisticamente"@pt . . . . . . "Demostraci\u00F3 provable per probabilitat"@ca . . "Preuve v\u00E9rifiable de mani\u00E8re probabiliste"@fr . . . "10096"^^ . "PCP\uB294 \uD655\uB960\uC801\uC73C\uB85C \uAC80\uC0AC\uD560 \uC218 \uC788\uB294 \uC99D\uBA85(probabilistically checkable proof)\uC744 \uD560 \uC218 \uC788\uB294 \uD310\uC815 \uBB38\uC81C\uB4E4\uC758 \uBCF5\uC7A1\uB3C4 \uC885\uB958\uC774\uB2E4."@ko . . . "In computational complexity theory, a probabilistically checkable proof (PCP) is a type of proof that can be checked by a randomized algorithm using a bounded amount of randomness and reading a bounded number of bits of the proof. The algorithm is then required to accept correct proofs and reject incorrect proofs with very high probability. A standard proof (or certificate), as used in the verifier-based definition of the complexity class NP, also satisfies these requirements, since the checking procedure deterministically reads the whole proof, always accepts correct proofs and rejects incorrect proofs. However, what makes them interesting is the existence of probabilistically checkable proofs that can be checked by reading only a few bits of the proof using randomness in an essential way"@en . . . . . . "\u8A08\u7B97\u8907\u96D1\u6027\u7406\u8AD6\u306B\u304A\u3051\u308B PCP \u3068\u306F\u3001\u78BA\u7387\u7684\u691C\u67FB\u53EF\u80FD\u8A3C\u660E\uFF08probabilistically checkable proof\uFF09\u7CFB\u3092\u6301\u3064\u6C7A\u5B9A\u554F\u984C\u306E\u8907\u96D1\u6027\u30AF\u30E9\u30B9\u3067\u3042\u308B\u3002"@ja . . "Na teoria da complexidade computacional, uma prova verific\u00E1vel probabilisticamente (PCP) \u00E9 um tipo de prova que pode ser verificada por um algoritmo aleat\u00F3rio usando uma quantidade limitada de aleatoriedade e ler um n\u00FAmero limitado de bits da prova. O algoritmo \u00E9 ent\u00E3o obrigado a aceitar as provas corretas e rejeitar as provas incorretas com a probabilidade muito alta. Uma prova padr\u00E3o (ou Certificada), como a usada na defini\u00E7\u00E3o base do verificador de complexidade da classe NP, tamb\u00E9m satisfaz os requisitos, uma vez que o procedimento de verifica\u00E7\u00E3o deterministicamente l\u00EA a prova toda, sempre aceita as provas corretas e rejeita as incorretas. No entanto, o que os torna interessante \u00E9 a exist\u00EAncia de provas verific\u00E1veis probabilisticamente que podem ser verificadas por ler apenas alguns bit"@pt . . . . "En teoria de la complexitat, un sistema de demostraci\u00F3 provable per probabilitat (o PCP per les sigles en angl\u00E8s probabilistically checkable proof) \u00E9s un tipus de prova que pot ser comprovada per un algorisme probabil\u00EDstic usant una quantitat fitada de aleatorietat i llegint una quantitat fitada de bits de la prova. Es requereix que l'algorisme accepti les proves correctes i rebutgi les incorrectes amb una probabilitat molt alta. Una prova est\u00E0ndard (o certificat), igual que el que es fa servir en la definici\u00F3 amb verificador de la classe NP, tamb\u00E9 satisf\u00E0 aquests requeriments, ja que el procediment de comprovaci\u00F3 de forma determinista llegeix la prova sencera, sempre accepta les proves correctes i rebutja les incorrectes."@ca . "Na teoria da complexidade computacional, uma prova verific\u00E1vel probabilisticamente (PCP) \u00E9 um tipo de prova que pode ser verificada por um algoritmo aleat\u00F3rio usando uma quantidade limitada de aleatoriedade e ler um n\u00FAmero limitado de bits da prova. O algoritmo \u00E9 ent\u00E3o obrigado a aceitar as provas corretas e rejeitar as provas incorretas com a probabilidade muito alta. Uma prova padr\u00E3o (ou Certificada), como a usada na defini\u00E7\u00E3o base do verificador de complexidade da classe NP, tamb\u00E9m satisfaz os requisitos, uma vez que o procedimento de verifica\u00E7\u00E3o deterministicamente l\u00EA a prova toda, sempre aceita as provas corretas e rejeita as incorretas. No entanto, o que os torna interessante \u00E9 a exist\u00EAncia de provas verific\u00E1veis probabilisticamente que podem ser verificadas por ler apenas alguns bits da prova usando essencialmente a aleatoriedade. Provas verific\u00E1veis probabilisticamente d\u00E3o origem a muitas classes de complexidade dependendo do n\u00FAmero de consultas necess\u00E1rias e a quantidade de aleatoriedade utilizada. A classe PCP [r (n), q (n)] refere-se ao conjunto de problemas de decis\u00E3o que t\u00EAm provas verific\u00E1veis probabilisticamente que podem ser verificadas em tempo polinomial usando essencialmente, no m\u00E1ximo, r (n) bits aleat\u00F3rios e pela leitura de no m\u00E1ximo q (n ) bits da prova . Exceto quando especificado ao contr\u00E1rio, as provas corretas devem ser sempre aceitas, e as provas incorretas devem ser rejeitadas com probabilidade maior que 1/2. O teorema PCP, melhor resultado na teoria da complexidade computacional, afirma que PCP [O (log n), O (1)] = NP. A complexidade da classe PCP \u00E9 a classe de decis\u00E3o de problemas que t\u00EAm provas probabilisticamente verific\u00E1veis com a completude 1, rigidez \u03B1 <1, complexidade aleat\u00F3ria O (log n) e complexidade da consulta O (1)."@pt . . . . "PCP (\u8A08\u7B97\u8907\u96D1\u6027\u7406\u8AD6)"@ja . . . . . . . . . "504509"^^ . . . "PCP (\uBCF5\uC7A1\uB3C4)"@ko . . . . . "\u8A08\u7B97\u8907\u96D1\u6027\u7406\u8AD6\u306B\u304A\u3051\u308B PCP \u3068\u306F\u3001\u78BA\u7387\u7684\u691C\u67FB\u53EF\u80FD\u8A3C\u660E\uFF08probabilistically checkable proof\uFF09\u7CFB\u3092\u6301\u3064\u6C7A\u5B9A\u554F\u984C\u306E\u8907\u96D1\u6027\u30AF\u30E9\u30B9\u3067\u3042\u308B\u3002"@ja . . . "1077794443"^^ . . "PCP\uB294 \uD655\uB960\uC801\uC73C\uB85C \uAC80\uC0AC\uD560 \uC218 \uC788\uB294 \uC99D\uBA85(probabilistically checkable proof)\uC744 \uD560 \uC218 \uC788\uB294 \uD310\uC815 \uBB38\uC81C\uB4E4\uC758 \uBCF5\uC7A1\uB3C4 \uC885\uB958\uC774\uB2E4."@ko .