| Property |
Value |
| dbo:abstract
|
- 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)
- 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)
|
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 2842 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| prop-fr:wikiPageUsesTemplate
| |
| dct:subject
| |
| 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)
- 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)
|
| rdfs:label
|
- Chứng minh có thể kiểm chứng ngẫu nhiên (độ phức tạp) (vi)
- Preuve vérifiable de manière probabiliste (fr)
- Probabilistically checkable proof (en)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:namedAfter
of | |
| is dbo:wikiPageWikiLink
of | |
| is oa:hasTarget
of | |
| is foaf:primaryTopic
of | |
