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
| Attributes | Values |
|---|
| rdf:type
| |
| rdfs:label
| - Demostració provable per probabilitat (ca)
- Preuve vérifiable de manière probabiliste (fr)
- PCP (計算複雑性理論) (ja)
- PCP (복잡도) (ko)
- Probabilistically checkable proof (en)
- Provas verificáveis probabilisticamente (pt)
|
| rdfs:comment
| - En théorie de la complexité, une preuve vérifiable de manière probabiliste aussi appelée preuve vérifiable en probabilité ou PCP (pour Probabilistically checkable proof) est une preuve (certificat) qui peut être vérifiée par un algorithme probabiliste, en utilisant un certain nombre de bits aléatoires et en lisant un certain nombre de bits de la preuve. La classe PCP[r(n),q(n)] réfère à l'ensemble des problèmes de décision qui ont des preuves vérifiables en temps polynomial avec au plus r(n) bits aléatoires et en lisant au plus q(n) bits de la preuve. Sauf mention, une preuve correcte est toujours acceptée ; une preuve incorrecte est rejetée avec une probabilité supérieure ou égale à 1/2. (fr)
- PCP는 확률적으로 검사할 수 있는 증명(probabilistically checkable proof)을 할 수 있는 판정 문제들의 복잡도 종류이다. (ko)
- 計算複雑性理論における PCP とは、確率的検査可能証明（probabilistically checkable proof）系を持つ決定問題の複雑性クラスである。 (ja)
- En teoria de la complexitat, un sistema de demostració provable per probabilitat (o PCP per les sigles en anglès probabilistically checkable proof) és un tipus de prova que pot ser comprovada per un algorisme probabilístic 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àndard (o certificat), igual que el que es fa servir en la definició amb verificador de la classe NP, també satisfà aquests requeriments, ja que el procediment de comprovació de forma determinista llegeix la prova sencera, sempre accepta les proves correctes i rebutja les incorrectes. (ca)
- 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)
- Na teoria da complexidade computacional, uma prova verificável probabilisticamente (PCP) é um tipo de prova que pode ser verificada por um algoritmo aleatório usando uma quantidade limitada de aleatoriedade e ler um número limitado de bits da prova. O algoritmo é então obrigado a aceitar as provas corretas e rejeitar as provas incorretas com a probabilidade muito alta. Uma prova padrão (ou Certificada), como a usada na definição base do verificador de complexidade da classe NP, também satisfaz os requisitos, uma vez que o procedimento de verificação deterministicamente lê a prova toda, sempre aceita as provas corretas e rejeita as incorretas. No entanto, o que os torna interessante é a existência de provas verificáveis probabilisticamente que podem ser verificadas por ler apenas alguns bit (pt)
|
| 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
| - En teoria de la complexitat, un sistema de demostració provable per probabilitat (o PCP per les sigles en anglès probabilistically checkable proof) és un tipus de prova que pot ser comprovada per un algorisme probabilístic 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àndard (o certificat), igual que el que es fa servir en la definició amb verificador de la classe NP, també satisfà aquests requeriments, ja que el procediment de comprovació 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)] és la classe de complexitat del conjunt de problemes de decisió que tenen proves provable per probabilitat en temps polinòmic usant com a molt r(n) bits aleatoris llegint com a molt q(n) bits de la demostració. 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és gran d'1/2. (ca)
- 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 théorie de la complexité, une preuve vérifiable de manière probabiliste aussi appelée preuve vérifiable en probabilité ou PCP (pour Probabilistically checkable proof) est une preuve (certificat) qui peut être vérifiée par un algorithme probabiliste, en utilisant un certain nombre de bits aléatoires et en lisant un certain nombre de bits de la preuve. La classe PCP[r(n),q(n)] réfère à l'ensemble des problèmes de décision qui ont des preuves vérifiables en temps polynomial avec au plus r(n) bits aléatoires et en lisant au plus q(n) bits de la preuve. Sauf mention, une preuve correcte est toujours acceptée ; une preuve incorrecte est rejetée avec une probabilité supérieure ou égale à 1/2. (fr)
- PCP는 확률적으로 검사할 수 있는 증명(probabilistically checkable proof)을 할 수 있는 판정 문제들의 복잡도 종류이다. (ko)
- 計算複雑性理論における PCP とは、確率的検査可能証明（probabilistically checkable proof）系を持つ決定問題の複雑性クラスである。 (ja)
- Na teoria da complexidade computacional, uma prova verificável probabilisticamente (PCP) é um tipo de prova que pode ser verificada por um algoritmo aleatório usando uma quantidade limitada de aleatoriedade e ler um número limitado de bits da prova. O algoritmo é então obrigado a aceitar as provas corretas e rejeitar as provas incorretas com a probabilidade muito alta. Uma prova padrão (ou Certificada), como a usada na definição base do verificador de complexidade da classe NP, também satisfaz os requisitos, uma vez que o procedimento de verificação deterministicamente lê a prova toda, sempre aceita as provas corretas e rejeita as incorretas. No entanto, o que os torna interessante é a existência de provas verificáveis probabilisticamente que podem ser verificadas por ler apenas alguns bits da prova usando essencialmente a aleatoriedade. Provas verificáveis probabilisticamente dão origem a muitas classes de complexidade dependendo do número de consultas necessárias e a quantidade de aleatoriedade utilizada. A classe PCP [r (n), q (n)] refere-se ao conjunto de problemas de decisão que têm provas verificáveis probabilisticamente que podem ser verificadas em tempo polinomial usando essencialmente, no máximo, r (n) bits aleatórios e pela leitura de no máximo q (n ) bits da prova . Exceto quando especificado ao contrário, 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 é a classe de decisão de problemas que têm provas probabilisticamente verificáveis com a completude 1, rigidez α <1, complexidade aleatória O (log n) e complexidade da consulta O (1). (pt)
|
| gold:hypernym
| |
| prov:wasDerivedFrom
| |
| page length (characters) of wiki page
| |
| foaf:isPrimaryTopicOf
| |
| 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)