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

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

Namespace Prefixes

PrefixIRI
n4http://g.co/kg/g/
dcthttp://purl.org/dc/terms/
dbohttp://dbpedia.org/ontology/
foafhttp://xmlns.com/foaf/0.1/
rdfshttp://www.w3.org/2000/01/rdf-schema#
category-frhttp://fr.dbpedia.org/resource/Catégorie:
n9http://fr.dbpedia.org/resource/Modèle:
wikipedia-frhttp://fr.wikipedia.org/wiki/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
owlhttp://www.w3.org/2002/07/owl#
dbpedia-frhttp://fr.dbpedia.org/resource/
prop-frhttp://fr.dbpedia.org/property/
provhttp://www.w3.org/ns/prov#
xsdhhttp://www.w3.org/2001/XMLSchema#
dbrhttp://dbpedia.org/resource/
wikidatahttp://www.wikidata.org/entity/

Statements

Subject Item
dbpedia-fr:Théorème_de_Mahaney
rdfs:label
Mahaney's theorem Théorème de Mahaney
rdfs:comment
En informatique théorique, et plus précisément en théorie de la complexité, le théorème de Mahaney dit que s'il existe un langage creux NP-complet, alors P = NP. Un langage creux est un langage où le nombre de mots de longueur n du langage est polynomial en n.
owl:sameAs
n4:11bv1t272t wikidata:Q20707135 dbr:Mahaney's_theorem
dbo:wikiPageID
11289344
dbo:wikiPageRevisionID
181651266
dbo:wikiPageWikiLink
category-fr:Algorithmique dbpedia-fr:Problème_P_≟_NP dbpedia-fr:Langage_creux dbpedia-fr:Théorie_de_la_complexité_(informatique_théorique) dbpedia-fr:Problème_NP-complet category-fr:Informatique_théorique dbpedia-fr:Langage_formel dbpedia-fr:Polynôme dbpedia-fr:Informatique_théorique category-fr:Logique_mathématique
dbo:wikiPageLength
954
dct:subject
category-fr:Logique_mathématique category-fr:Informatique_théorique category-fr:Algorithmique
prop-fr:wikiPageUsesTemplate
n9:Références n9:Portail
prov:wasDerivedFrom
wikipedia-fr:Théorème_de_Mahaney?oldid=181651266&ns=0
foaf:isPrimaryTopicOf
wikipedia-fr:Théorème_de_Mahaney
dbo:abstract
En informatique théorique, et plus précisément en théorie de la complexité, le théorème de Mahaney dit que s'il existe un langage creux NP-complet, alors P = NP. Un langage creux est un langage où le nombre de mots de longueur n du langage est polynomial en n.