| Property |
Value |
| dbo:abstract
|
- 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)
- 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)
|
| dbo:award
| |
| dbo:namedAfter
| |
| dbo:thumbnail
| |
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 15017 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| prop-fr:année
|
- 1996 (xsd:integer)
- 1998 (xsd:integer)
- 2007 (xsd:integer)
- 2010 (xsd:integer)
- 2012 (xsd:integer)
|
| prop-fr:archivedate
| |
| prop-fr:archiveurl
| |
| prop-fr:auteur
|
- Dana Moshkovitz (fr)
- Dana Moshkovitz (fr)
|
| prop-fr:doi
| |
| prop-fr:fin
| |
| prop-fr:journal
|
- Journal of the ACM (fr)
- Journal of the ACM (fr)
|
| prop-fr:lienAuteur
|
- Irit Dinur (fr)
- Irit Dinur (fr)
|
| prop-fr:lireEnLigne
| |
| prop-fr:nom
|
- Lund (fr)
- Motwani (fr)
- Sudan (fr)
- Ghys (fr)
- Arora (fr)
- PCP (fr)
- Feige (fr)
- Szegedy (fr)
- Lovász (fr)
- Goldwasser (fr)
- Dinur (fr)
- Safra (fr)
- Lund (fr)
- Motwani (fr)
- Sudan (fr)
- Ghys (fr)
- Arora (fr)
- PCP (fr)
- Feige (fr)
- Szegedy (fr)
- Lovász (fr)
- Goldwasser (fr)
- Dinur (fr)
- Safra (fr)
|
| prop-fr:numéro
|
- 1 (xsd:integer)
- 2 (xsd:integer)
- 3 (xsd:integer)
|
| prop-fr:numéroChapitre
| |
| prop-fr:pages
|
- 12 (xsd:integer)
- 70 (xsd:integer)
- 268 (xsd:integer)
- 501 (xsd:integer)
|
| prop-fr:passage
| |
| prop-fr:prénom
|
- Mario (fr)
- Étienne (fr)
- Carsten (fr)
- Sanjeev (fr)
- Uriel (fr)
- Rajeev (fr)
- Shmuel (fr)
- Laszlo (fr)
- Madhu (fr)
- Shafi (fr)
- Irit (fr)
- Mario (fr)
- Étienne (fr)
- Carsten (fr)
- Sanjeev (fr)
- Uriel (fr)
- Rajeev (fr)
- Shmuel (fr)
- Laszlo (fr)
- Madhu (fr)
- Shafi (fr)
- Irit (fr)
|
| prop-fr:périodique
|
- Images des Mathématiques (fr)
- Journal of the ACM (fr)
- ACM Crossroads (fr)
- Images des Mathématiques (fr)
- Journal of the ACM (fr)
- ACM Crossroads (fr)
|
| prop-fr:titre
|
- Proof verification and the hardness of approximation problems (fr)
- The PCP theorem by gap amplification (fr)
- Interactive proofs and the hardness of approximating cliques (fr)
- Vérifier une preuve : la conférence de Irit Dinur (fr)
- The tale of the PCP theorem (fr)
- Probabilistic checking of proofs: a new characterization of NP (fr)
- Proof verification and the hardness of approximation problems (fr)
- The PCP theorem by gap amplification (fr)
- Interactive proofs and the hardness of approximating cliques (fr)
- Vérifier une preuve : la conférence de Irit Dinur (fr)
- The tale of the PCP theorem (fr)
- Probabilistic checking of proofs: a new characterization of NP (fr)
|
| prop-fr:titreChapitre
|
- PCP Theorem and Hardness of Approximation: An introduction (fr)
- PCP Theorem and Hardness of Approximation: An introduction (fr)
|
| prop-fr:url
| |
| prop-fr:volume
|
- 18 (xsd:integer)
- 43 (xsd:integer)
- 45 (xsd:integer)
- 54 (xsd:integer)
|
| prop-fr:wikiPageUsesTemplate
| |
| dct:subject
| |
| rdfs:comment
|
- 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)
- 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)
|
| rdfs:label
|
- PCP-Theorem (de)
- PCP-теорема (uk)
- Théorème PCP (fr)
- PCP-Theorem (de)
- PCP-теорема (uk)
- Théorème PCP (fr)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageDisambiguates
of | |
| is dbo:wikiPageWikiLink
of | |
| is oa:hasTarget
of | |
| is foaf:primaryTopic
of | |
