| Property |
Value |
| dbo:abstract
|
- Le problème P ≟ NP est une conjecture en mathématiques, et plus précisément en informatique théorique, considérée par de nombreux chercheurs comme une des plus importantes conjectures du domaine, et même des mathématiques en général. L'Institut de mathématiques Clay a inclus ce problème dans sa liste des sept problèmes du prix du millénaire, et offre à ce titre un million de dollars à quiconque sera en mesure de démontrer P = NP ou P ≠ NP ou de démontrer que ce n'est pas démontrable. Ce problème est également le troisième problème de Smale. Très schématiquement, il s'agit de déterminer si le fait de pouvoir vérifier rapidement une solution à un problème implique de pouvoir la trouver rapidement ; ou encore, si ce que nous pouvons trouver rapidement lorsque nous avons de la chance peut être trouvé aussi vite par un calcul intelligent. Plus précisément, il s'agit de savoir si la classe de complexité P des problèmes de décision admettant un algorithme de résolution s'exécutant en temps polynomial sur une machine de Turing est équivalente à la classe de complexité NP des problèmes de décision dont la vérification du résultat, une fois celui-ci connu, demande un temps polynomial. Un algorithme qui demande un temps d'exécution polynomial est généralement considéré comme « rapide » (par rapport à un temps d'exécution exponentiel par exemple). À condition que le degré du polynôme issu du caractère polynomial de l'algorithme soit raisonnable, les conséquences de P = NP pourraient être considérables dans de nombreux domaines : cryptologie, informatique, mathématiques, ingénierie, économie. S'il était prouvé que P = NP, alors la résolution de tous les autres problèmes posés par l’Institut Clay pourrait devenir évidente. S'il était au contraire avéré que P ≠ NP, cela signifierait qu'une large classe de problèmes seraient presque sûrement définitivement hors d'atteinte du calcul dans un temps raisonnable (ou nécessiteraient le développement d'architectures différentes de celles des machines de Turing). (fr)
- Le problème P ≟ NP est une conjecture en mathématiques, et plus précisément en informatique théorique, considérée par de nombreux chercheurs comme une des plus importantes conjectures du domaine, et même des mathématiques en général. L'Institut de mathématiques Clay a inclus ce problème dans sa liste des sept problèmes du prix du millénaire, et offre à ce titre un million de dollars à quiconque sera en mesure de démontrer P = NP ou P ≠ NP ou de démontrer que ce n'est pas démontrable. Ce problème est également le troisième problème de Smale. Très schématiquement, il s'agit de déterminer si le fait de pouvoir vérifier rapidement une solution à un problème implique de pouvoir la trouver rapidement ; ou encore, si ce que nous pouvons trouver rapidement lorsque nous avons de la chance peut être trouvé aussi vite par un calcul intelligent. Plus précisément, il s'agit de savoir si la classe de complexité P des problèmes de décision admettant un algorithme de résolution s'exécutant en temps polynomial sur une machine de Turing est équivalente à la classe de complexité NP des problèmes de décision dont la vérification du résultat, une fois celui-ci connu, demande un temps polynomial. Un algorithme qui demande un temps d'exécution polynomial est généralement considéré comme « rapide » (par rapport à un temps d'exécution exponentiel par exemple). À condition que le degré du polynôme issu du caractère polynomial de l'algorithme soit raisonnable, les conséquences de P = NP pourraient être considérables dans de nombreux domaines : cryptologie, informatique, mathématiques, ingénierie, économie. S'il était prouvé que P = NP, alors la résolution de tous les autres problèmes posés par l’Institut Clay pourrait devenir évidente. S'il était au contraire avéré que P ≠ NP, cela signifierait qu'une large classe de problèmes seraient presque sûrement définitivement hors d'atteinte du calcul dans un temps raisonnable (ou nécessiteraient le développement d'architectures différentes de celles des machines de Turing). (fr)
|
| dbo:isPartOf
| |
| dbo:namedAfter
| |
| dbo:thumbnail
| |
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 40644 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| prop-fr:année
|
- 1971 (xsd:integer)
- 2003 (xsd:integer)
- 2005 (xsd:integer)
- 2009 (xsd:integer)
- 2016 (xsd:integer)
|
| prop-fr:auteur
|
- G. J. Woeginger (fr)
- G. J. Woeginger (fr)
|
| prop-fr:fr
|
- Newton da Costa (fr)
- arithmétique primitive récursive (fr)
- Newton da Costa (fr)
- arithmétique primitive récursive (fr)
|
| prop-fr:isbn
| |
| prop-fr:issn
| |
| prop-fr:lang
| |
| prop-fr:langue
|
- anglais (fr)
- en (fr)
- français (fr)
- anglais (fr)
- en (fr)
- français (fr)
|
| prop-fr:lienAuteur
|
- :en:Lance Fortnow (fr)
- Scott Aaronson (fr)
- :en:Lance Fortnow (fr)
- Scott Aaronson (fr)
|
| prop-fr:lienPériodique
|
- Communications of the ACM (fr)
- Communications of the ACM (fr)
|
| prop-fr:mois
|
- Août (fr)
- Septembre (fr)
- octobre (fr)
- Août (fr)
- Septembre (fr)
- octobre (fr)
|
| prop-fr:nom
|
- Cook (fr)
- Delahaye (fr)
- Fortnow (fr)
- Aaronson (fr)
- Cook (fr)
- Delahaye (fr)
- Fortnow (fr)
- Aaronson (fr)
|
| prop-fr:numéro
|
- 9 (xsd:integer)
- 334 (xsd:integer)
|
| prop-fr:pages
|
- 78 (xsd:integer)
- 90 (xsd:integer)
- 151 (xsd:integer)
|
| prop-fr:passage
| |
| prop-fr:prénom
|
- Jean-Paul (fr)
- Scott (fr)
- Lance (fr)
- Stephen A. (fr)
- Jean-Paul (fr)
- Scott (fr)
- Lance (fr)
- Stephen A. (fr)
|
| prop-fr:périodique
|
- Communications of the ACM (fr)
- Pour la Science (fr)
- Communications of the ACM (fr)
- Pour la Science (fr)
|
| prop-fr:revue
|
- Bulletin of the EATCS (fr)
- Bulletin of the EATCS (fr)
|
| prop-fr:titre
|
- Is P Versus NP Formally Independent? (fr)
- P ? NP (fr)
- The P-versus-NP page (fr)
- The Status of the P Versus NP Problem (fr)
- Un algorithme à un million de dollars ? (fr)
- Is P Versus NP Formally Independent? (fr)
- P ? NP (fr)
- The P-versus-NP page (fr)
- The Status of the P Versus NP Problem (fr)
- Un algorithme à un million de dollars ? (fr)
|
| prop-fr:titreChapitre
|
- The Complexity of Theorem-Proving Procedures (fr)
- The Complexity of Theorem-Proving Procedures (fr)
|
| prop-fr:titreOuvrage
|
- Open Problems in Mathematics (fr)
- Conference Record of Third Annual ACM Symposium on Theory of Computing (fr)
- Open Problems in Mathematics (fr)
- Conference Record of Third Annual ACM Symposium on Theory of Computing (fr)
|
| prop-fr:trad
|
- Primitive recursive arithmetic (fr)
- Primitive recursive arithmetic (fr)
|
| prop-fr:url
| |
| prop-fr:urlTexte
| |
| prop-fr:volume
|
- 52 (xsd:integer)
- 81 (xsd:integer)
|
| prop-fr:wikiPageUsesTemplate
| |
| prop-fr:éditeur
|
- Springer (fr)
- Springer (fr)
|
| dct:subject
| |
| rdfs:comment
|
- Le problème P ≟ NP est une conjecture en mathématiques, et plus précisément en informatique théorique, considérée par de nombreux chercheurs comme une des plus importantes conjectures du domaine, et même des mathématiques en général. L'Institut de mathématiques Clay a inclus ce problème dans sa liste des sept problèmes du prix du millénaire, et offre à ce titre un million de dollars à quiconque sera en mesure de démontrer P = NP ou P ≠ NP ou de démontrer que ce n'est pas démontrable. Ce problème est également le troisième problème de Smale. (fr)
- Le problème P ≟ NP est une conjecture en mathématiques, et plus précisément en informatique théorique, considérée par de nombreux chercheurs comme une des plus importantes conjectures du domaine, et même des mathématiques en général. L'Institut de mathématiques Clay a inclus ce problème dans sa liste des sept problèmes du prix du millénaire, et offre à ce titre un million de dollars à quiconque sera en mesure de démontrer P = NP ou P ≠ NP ou de démontrer que ce n'est pas démontrable. Ce problème est également le troisième problème de Smale. (fr)
|
| rdfs:label
|
- مسألة كثير حدود وكثير حدود غير قطعي (ar)
- Bài toán P so với NP (vi)
- Classi di complessità P e NP (it)
- P-NP-Problem (de)
- P/NP问题 (zh)
- P=NP? (sv)
- Problème P ≟ NP (fr)
- Равенство классов P и NP (ru)
- Рівність класів P і NP (uk)
- مسألة كثير حدود وكثير حدود غير قطعي (ar)
- Bài toán P so với NP (vi)
- Classi di complessità P e NP (it)
- P-NP-Problem (de)
- P/NP问题 (zh)
- P=NP? (sv)
- Problème P ≟ NP (fr)
- Равенство классов P и NP (ru)
- Рівність класів P і NP (uk)
|
| rdfs:seeAlso
| |
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is oa:hasTarget
of | |
| is foaf:primaryTopic
of | |
