| http://dbpedia.org/ontology/abstract
|
En théorie de la complexité, une preuve na … En théorie de la complexité, une preuve naturelle est une démonstration de borne inférieure sur des circuits booléens qui satisfait certaines propriétés. Ces preuves sont dites naturelles, car elles utilisent une technique classique dans la littérature du domaine. Elles ont été mises en lumière par un résultat d'Alexander Razborov et Steven Rudich qui prouvent que (sous une hypothèse classique) ce genre de preuve ne peut pas permettre de prouver que P est différent de NP.ttre de prouver que P est différent de NP.
|
| http://dbpedia.org/ontology/wikiPageID
|
9808184
|
| http://dbpedia.org/ontology/wikiPageLength
|
5425
|
| http://dbpedia.org/ontology/wikiPageRevisionID
|
178672866
|
| http://dbpedia.org/ontology/wikiPageWikiLink
|
http://fr.dbpedia.org/resource/P/poly +
, http://fr.dbpedia.org/resource/Fonction_parit%C3%A9 +
, http://fr.dbpedia.org/resource/Table_de_v%C3%A9rit%C3%A9 +
, http://fr.dbpedia.org/resource/Cat%C3%A9gorie:Th%C3%A9or%C3%A8me_de_la_th%C3%A9orie_de_la_complexit%C3%A9 +
, http://fr.dbpedia.org/resource/Steven_Rudich +
, http://fr.dbpedia.org/resource/Prix_G%C3%B6del +
, http://fr.dbpedia.org/resource/Classe_de_complexit%C3%A9 +
, http://fr.dbpedia.org/resource/Cat%C3%A9gorie:Th%C3%A9orie_de_la_complexit%C3%A9_des_algorithmes +
, http://fr.dbpedia.org/resource/Probl%C3%A8me_algorithmique +
, http://fr.dbpedia.org/resource/D%C3%A9monstration_%28logique_et_math%C3%A9matique%29 +
, http://fr.dbpedia.org/resource/Th%C3%A9orie_de_la_complexit%C3%A9_%28informatique_th%C3%A9orique%29 +
, http://fr.dbpedia.org/resource/NP_%28complexit%C3%A9%29 +
, http://fr.dbpedia.org/resource/Circuit_bool%C3%A9en +
, http://fr.dbpedia.org/resource/Alexandre_Razborov +
, http://fr.dbpedia.org/resource/Fonction_pseudo-al%C3%A9atoire +
, http://fr.dbpedia.org/resource/Probl%C3%A8me_P_%E2%89%9F_NP +
, http://fr.dbpedia.org/resource/P_%28complexit%C3%A9%29 +
, http://fr.dbpedia.org/resource/AC0 +
, http://fr.dbpedia.org/resource/Machine_de_Turing +
, http://fr.dbpedia.org/resource/Fonction_%C3%A0_sens_unique +
|
| http://fr.dbpedia.org/property/fr
|
modèle de calcul
|
| http://fr.dbpedia.org/property/langue
|
en
|
| http://fr.dbpedia.org/property/trad
|
computational model
|
| http://fr.dbpedia.org/property/wikiPageUsesTemplate
|
http://fr.dbpedia.org/resource/Mod%C3%A8le:Portail +
, http://fr.dbpedia.org/resource/Mod%C3%A8le:Lien +
|
| http://purl.org/dc/terms/subject
|
http://fr.dbpedia.org/resource/Cat%C3%A9gorie:Th%C3%A9orie_de_la_complexit%C3%A9_des_algorithmes +
, http://fr.dbpedia.org/resource/Cat%C3%A9gorie:Th%C3%A9or%C3%A8me_de_la_th%C3%A9orie_de_la_complexit%C3%A9 +
|
| http://www.w3.org/ns/prov#wasDerivedFrom
|
http://fr.wikipedia.org/wiki/Preuve_naturelle?oldid=178672866&ns=0 +
|
| http://xmlns.com/foaf/0.1/isPrimaryTopicOf
|
http://fr.wikipedia.org/wiki/Preuve_naturelle +
|
| owl:sameAs |
http://g.co/kg/m/030r95 +
, http://dbpedia.org/resource/Natural_proof +
, http://www.wikidata.org/entity/Q6980761 +
, http://fr.dbpedia.org/resource/Preuve_naturelle +
, http://ja.dbpedia.org/resource/%E8%87%AA%E7%84%B6%E3%81%AA%E8%A8%BC%E6%98%8E +
, http://pt.dbpedia.org/resource/Prova_natural +
, http://ma-graph.org/entity/2780532209 +
|
| rdfs:comment |
En théorie de la complexité, une preuve na … En théorie de la complexité, une preuve naturelle est une démonstration de borne inférieure sur des circuits booléens qui satisfait certaines propriétés. Ces preuves sont dites naturelles, car elles utilisent une technique classique dans la littérature du domaine. Elles ont été mises en lumière par un résultat d'Alexander Razborov et Steven Rudich qui prouvent que (sous une hypothèse classique) ce genre de preuve ne peut pas permettre de prouver que P est différent de NP.ttre de prouver que P est différent de NP.
|
| rdfs:label |
Natural proof
, Preuve naturelle
|
