This HTML5 document contains 235 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
dbpedia-dahttp://da.dbpedia.org/resource/
dbpedia-elhttp://el.dbpedia.org/resource/
n64http://www.claymath.org/sites/default/files/
dbpedia-nohttp://no.dbpedia.org/resource/
dbpedia-svhttp://sv.dbpedia.org/resource/
n16http://www.scottaaronson.com/papers/
dbpedia-lmohttp://lmo.dbpedia.org/resource/
n43http://www.win.tue.nl/~gwoegi/papers/
dbrhttp://dbpedia.org/resource/
dbpedia-fihttp://fi.dbpedia.org/resource/
n42http://www.win.tue.nl/~gwoegi/
dbpedia-arhttp://ar.dbpedia.org/resource/
n6http://fr.dbpedia.org/resource/Modèle:
dbpedia-hehttp://he.dbpedia.org/resource/
n55http://ml.dbpedia.org/resource/
n54http://commons.wikimedia.org/wiki/Special:FilePath/
dbpedia-frhttp://fr.dbpedia.org/resource/
n32https://www.britannica.com/topic/
dcthttp://purl.org/dc/terms/
dbpedia-cshttp://cs.dbpedia.org/resource/
rdfshttp://www.w3.org/2000/01/rdf-schema#
n8http://g.co/kg/m/
n50http://lv.dbpedia.org/resource/
dbpedia-azhttp://az.dbpedia.org/resource/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
n44http://babelnet.org/rdf/
dbpedia-eohttp://eo.dbpedia.org/resource/
n35http://fr.dbpedia.org/resource/Fichier:
xsdhhttp://www.w3.org/2001/XMLSchema#
dbpedia-idhttp://id.dbpedia.org/resource/
dbpedia-ukhttp://uk.dbpedia.org/resource/
n33http://ma-graph.org/entity/
n10http://cacm.acm.org/magazines/2009/9/38904-the-status-of-the-p-versus-np-problem/
prop-frhttp://fr.dbpedia.org/property/
dbohttp://dbpedia.org/ontology/
dbpedia-srhttp://sr.dbpedia.org/resource/
dbpedia-vihttp://vi.dbpedia.org/resource/
dbpedia-pthttp://pt.dbpedia.org/resource/
dbpedia-jahttp://ja.dbpedia.org/resource/
dbpedia-ishttp://is.dbpedia.org/resource/
n40http://www.lifl.fr/~jdelahay/pls/2005/
dbpedia-dehttp://de.dbpedia.org/resource/
dbpedia-thhttp://th.dbpedia.org/resource/
dbpedia-rohttp://ro.dbpedia.org/resource/
dbpedia-ruhttp://ru.dbpedia.org/resource/
wikidatahttp://www.wikidata.org/entity/
n47https://www.quora.com/topic/
dbpedia-ithttp://it.dbpedia.org/resource/
dbpedia-cahttp://ca.dbpedia.org/resource/
n65http://ast.dbpedia.org/resource/
provhttp://www.w3.org/ns/prov#
foafhttp://xmlns.com/foaf/0.1/
dbpedia-nnhttp://nn.dbpedia.org/resource/
dbpedia-simplehttp://simple.dbpedia.org/resource/
wikipedia-frhttp://fr.wikipedia.org/wiki/
n56http://4mhz.de/
dbpedia-kohttp://ko.dbpedia.org/resource/
n26http://lt.dbpedia.org/resource/
dbpedia-behttp://be.dbpedia.org/resource/
dbpedia-glhttp://gl.dbpedia.org/resource/
dbpedia-trhttp://tr.dbpedia.org/resource/
dbpedia-fahttp://fa.dbpedia.org/resource/
n38http://www.cs.bris.ac.uk/Teaching/Resources/COMS30126/
n19http://zh.dbpedia.org/resource/P/
dbpedia-eshttp://es.dbpedia.org/resource/
category-frhttp://fr.dbpedia.org/resource/Catégorie:
owlhttp://www.w3.org/2002/07/owl#

Statements

Subject Item
dbpedia-fr:Problème_P_≟_NP
rdfs:label
Problème P ≟ NP P-NP-Problem Рівність класів P і NP Равенство классов P и NP P/NP问题 P=NP? Bài toán P so với NP Classi di complessità P e NP مسألة كثير حدود وكثير حدود غير قطعي
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.
rdfs:seeAlso
n32:P-problem n32:P-versus-NP-problem n47:P-vs-NP
owl:sameAs
dbpedia-de:P-NP-Problem n8:01txp dbpedia-nn:P=NP-problemet dbpedia-vi:Bài_toán_P_so_với_NP dbpedia-sv:P=NP%3F dbpedia-lmo:P_vs_NP dbpedia-be:Роўнасць_класаў_P_і_NP dbpedia-it:Classi_di_complessità_P_e_NP dbpedia-fi:P=NP n19:NP问题 dbpedia-pt:P_versus_NP dbpedia-uk:Рівність_класів_P_і_NP n26:P_ir_NP_lygumas dbpedia-es:Clases_de_complejidad_P_y_NP dbpedia-gl:P_versus_NP dbpedia-ru:Равенство_классов_P_и_NP dbpedia-fa:مسئله_P_در_مقابل_NP n33:186861659 dbpedia-eo:Demando_P_=_NP dbpedia-ca:P_versus_NP dbpedia-sr:П_=_НП_проблем dbpedia-no:P=NP-problemet dbpedia-ar:مسألة_كثير_حدود_وكثير_حدود_غير_قطعي n44:s03445750n dbpedia-th:กลุ่มความซับซ้อน_พี_และ_เอ็นพี dbpedia-ja:P≠NP予想 dbpedia-el:Πρόβλημα_P=NP dbpedia-tr:P_ile_NP_arasındaki_ilişki n50:P=NP_problēma dbpedia-ro:Clasele_de_complexitate_P_și_NP dbpedia-az:P=NP wikidata:Q746242 n55:പി_വേഴ്സസ്_എൻ_പി_പ്രശ്നം dbpedia-simple:P_versus_NP dbpedia-da:P_versus_NP dbpedia-is:P=NP-vandamálið dbpedia-ko:P-NP_문제 dbr:P_versus_NP_problem dbpedia-cs:Problém_P_versus_NP dbpedia-he:בעיית_P=NP n65:Clases_de_complexidá_P_y_NP dbpedia-id:Masalah_P_versus_NP
dbo:wikiPageID
4876394
dbo:wikiPageRevisionID
189504698
dbo:wikiPageWikiLink
dbpedia-fr:Preuve_naturelle category-fr:Problèmes_du_prix_du_millénaire dbpedia-fr:Alonzo_Church dbpedia-fr:Système_formel dbpedia-fr:Preuve_à_divulgation_nulle_de_connaissance dbpedia-fr:Machine_de_Turing dbpedia-fr:Adi_Shamir dbpedia-fr:1936 dbpedia-fr:Logement_étudiant_en_France dbpedia-fr:21_problèmes_NP-complets_de_Karp dbpedia-fr:1979 dbpedia-fr:Problème_NP-complet dbpedia-fr:Algorithme_de_Grover dbpedia-fr:Ingénierie dbpedia-fr:Hypothèse_de_Riemann dbpedia-fr:Économie_(discipline) dbpedia-fr:Générateur_de_nombres_pseudo-aléatoires dbpedia-fr:Fonction_exponentielle dbpedia-fr:Informatique dbpedia-fr:1931 dbpedia-fr:Décidabilité dbpedia-fr:Problème_SAT dbpedia-fr:Dollar_américain dbpedia-fr:Robin_Cousin dbpedia-fr:1993 dbpedia-fr:Hypothèse_du_continu dbpedia-fr:Jean-Paul_Delahaye dbpedia-fr:Stephen_Cook dbpedia-fr:Cryptologie dbpedia-fr:Disjonction_logique dbpedia-fr:P_(complexité) dbpedia-fr:Décomposition_en_produit_de_facteurs_premiers dbpedia-fr:Gerhard_Woeginger dbpedia-fr:Informatique_théorique n35:BQP_complexity_class_diagram.svg dbpedia-fr:Théorème_de_Cook dbpedia-fr:Problème_de_décision dbpedia-fr:Théorie_de_la_complexité_(informatique_théorique) dbpedia-fr:Algorithme_de_Shor dbpedia-fr:Problème_de_l'isomorphisme_de_graphes dbpedia-fr:Problème_de_l'arrêt dbpedia-fr:Authentification dbpedia-fr:Crible_algébrique dbpedia-fr:Problème_de_la_décision dbpedia-fr:Théorème_de_Robertson-Seymour dbpedia-fr:Alan_Turing dbpedia-fr:Théorie_de_la_démonstration n35:P_np_fr.svg dbpedia-fr:Calculateur_quantique dbpedia-fr:1928 dbpedia-fr:Algorithme_probabiliste dbpedia-fr:BQP dbpedia-fr:Francisco_Dória dbpedia-fr:Relation_binaire dbpedia-fr:Théorèmes_d'incomplétude_de_Gödel dbpedia-fr:Saison_2_d'Elementary dbpedia-fr:PSPACE dbpedia-fr:IP_(complexité) category-fr:Théorie_de_la_complexité_des_algorithmes dbpedia-fr:Kurt_Gödel dbpedia-fr:Théorème_de_Goodstein dbpedia-fr:Conjecture dbpedia-fr:Langage_formel dbpedia-fr:NP-intermédiaire dbpedia-fr:Attaque_par_force_brute category-fr:Conjecture_non_résolue dbpedia-fr:Institut_de_mathématiques_Clay dbpedia-fr:Axiome dbpedia-fr:David_Hilbert dbpedia-fr:Mathématiques dbpedia-fr:NP_(complexité) dbpedia-fr:Théorie_algorithmique_de_l'information dbpedia-fr:Problème_du_voyageur_de_commerce dbpedia-fr:Problèmes_du_prix_du_millénaire dbpedia-fr:Problèmes_de_Smale dbpedia-fr:Théorie_des_ensembles_de_Zermelo-Fraenkel dbpedia-fr:Conjecture_de_Goldbach dbpedia-fr:Michael_Sipser dbpedia-fr:Scott_Aaronson dbpedia-fr:Formule_BBP dbpedia-fr:Liste_de_problèmes_NP-complets dbpedia-fr:Oracle_(machine_de_Turing) dbpedia-fr:1963
dbo:wikiPageExternalLink
n10:fulltext n38:sipser92history.pdf n40:132.pdf n42:P-versus-NP.htm n43:exact.pdf n56:download.php%3Ffile=Cook1971_A4.pdf n16:pnp.pdf n16:indep.pdf n64:pvsnp.pdf
dbo:wikiPageLength
40644
dct:subject
category-fr:Problèmes_du_prix_du_millénaire category-fr:Conjecture_non_résolue category-fr:Théorie_de_la_complexité_des_algorithmes
prop-fr:wikiPageUsesTemplate
n6:Incise n6:Math n6:Computational_Complexity_(Papadimitriou) n6:Reducibility_Karp_1972 n6:Lien n6:Lien_web n6:Loupe n6:Palette_Problèmes_du_prix_du_millénaire n6:En n6:, n6:Article n6:= n6:Refnec n6:Références n6:Portail n6:Chapitre n6:Précision_nécessaire n6:Unité
prov:wasDerivedFrom
wikipedia-fr:Problème_P_≟_NP?oldid=189504698&ns=0
foaf:depiction
n54:P_np_fr.svg n54:BQP_complexity_class_diagram.svg
prop-fr:année
2005 2009 2016 1971 2003
prop-fr:auteur
G. J. Woeginger
prop-fr:fr
arithmétique primitive récursive Newton da Costa
prop-fr:isbn
978
prop-fr:issn
1
prop-fr:lang
en
prop-fr:langue
français anglais en
prop-fr:lienAuteur
:en:Lance Fortnow Scott Aaronson
prop-fr:lienPériodique
Communications of the ACM
prop-fr:mois
Septembre Août octobre
prop-fr:nom
Cook Delahaye Fortnow Aaronson
prop-fr:numéro
334 9
prop-fr:pages
151 78 90
prop-fr:passage
1
prop-fr:prénom
Jean-Paul Lance Scott Stephen A.
prop-fr:périodique
Pour la Science Communications of the ACM
prop-fr:titre
P ? NP Is P Versus NP Formally Independent? The P-versus-NP page The Status of the P Versus NP Problem Un algorithme à un million de dollars ?
prop-fr:titreChapitre
The Complexity of Theorem-Proving Procedures
prop-fr:titreOuvrage
Open Problems in Mathematics Conference Record of Third Annual ACM Symposium on Theory of Computing
prop-fr:trad
Primitive recursive arithmetic
prop-fr:url
n16:indep.pdf n16:pnp.pdf n42:P-versus-NP.htm
prop-fr:urlTexte
n10:fulltext n56:download.php%3Ffile=Cook1971_A4.pdf n40:132.pdf
prop-fr:volume
81 52
prop-fr:éditeur
Springer
prop-fr:revue
Bulletin of the EATCS
dbo:thumbnail
n54:P_np_fr.svg?width=300
foaf:isPrimaryTopicOf
wikipedia-fr:Problème_P_≟_NP
dbo:namedAfter
dbpedia-fr:P_(complexité) dbpedia-fr:NP_(complexité)
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).
dbo:isPartOf
dbpedia-fr:Problèmes_du_prix_du_millénaire