This HTML5 document contains 71 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-dehttp://de.dbpedia.org/resource/
dcthttp://purl.org/dc/terms/
dbohttp://dbpedia.org/ontology/
foafhttp://xmlns.com/foaf/0.1/
dbpedia-eshttp://es.dbpedia.org/resource/
n18http://g.co/kg/m/
dbpedia-ruhttp://ru.dbpedia.org/resource/
dbpedia-ukhttp://uk.dbpedia.org/resource/
rdfshttp://www.w3.org/2000/01/rdf-schema#
dbpedia-srhttp://sr.dbpedia.org/resource/
category-frhttp://fr.dbpedia.org/resource/Catégorie:
dbpedia-pthttp://pt.dbpedia.org/resource/
n13http://fr.dbpedia.org/resource/Modèle:
dbpedia-fahttp://fa.dbpedia.org/resource/
wikipedia-frhttp://fr.wikipedia.org/wiki/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
owlhttp://www.w3.org/2002/07/owl#
n17http://ma-graph.org/entity/
dbpedia-ithttp://it.dbpedia.org/resource/
dbpedia-zhhttp://zh.dbpedia.org/resource/
dbpedia-frhttp://fr.dbpedia.org/resource/
prop-frhttp://fr.dbpedia.org/property/
provhttp://www.w3.org/ns/prov#
xsdhhttp://www.w3.org/2001/XMLSchema#
wikidatahttp://www.wikidata.org/entity/
dbrhttp://dbpedia.org/resource/
dbpedia-nlhttp://nl.dbpedia.org/resource/
dbpedia-rohttp://ro.dbpedia.org/resource/

Statements

Subject Item
dbpedia-fr:21_problèmes_NP-complets_de_Karp
rdfs:label
Lista de 21 problemas NP-completos de Karp 21 problemi NP-completi di Karp 21 problèmes NP-complets de Karp 卡普的二十一個NP-完全問題
rdfs:comment
Les 21 problèmes NP-complets de Karp ont marqué une étape importante de l'histoire de la théorie de la complexité des algorithmes. Ce sont 21 problèmes réputés difficiles de combinatoire et de théorie des graphes qui sont réductibles entre eux. C'est ce qu'a démontré Richard Karp en 1972 dans son article Reducibility Among Combinatorial Problems, de même que leur NP-complétude.
owl:sameAs
dbpedia-fa:۲۱_مسئله_ان‌پی-کامل_کارپ dbpedia-zh:卡普的二十一個NP-完全問題 dbpedia-pt:21_problemas_NP-completos_de_Karp dbpedia-es:Lista_de_21_problemas_NP-completos_de_Karp dbpedia-nl:Karps_21_NP-volledige_problemen dbpedia-it:21_problemi_NP-completi_di_Karp dbpedia-de:Karps_21_NP-vollständige_Probleme n17:155373194 n18:06d_qs dbpedia-sr:Karpov_21_NP-kompletan_problem dbpedia-ru:21_NP-полная_задача_Карпа wikidata:Q1734364 dbpedia-ro:Cele_21_de_probleme_NP-complete_ale_lui_Karp dbr:Karp's_21_NP-complete_problems dbpedia-uk:21_NP-повна_задача_Карпа
dbo:wikiPageID
909305
dbo:wikiPageRevisionID
186128013
dbo:wikiPageWikiLink
dbpedia-fr:Stephen_Cook dbpedia-fr:Séquençage_de_tâches dbpedia-fr:Théorie_de_la_complexité_(informatique_théorique) dbpedia-fr:Appariement_à_3_dimensions dbpedia-fr:Coloration_de_graphe dbpedia-fr:Coupe_maximum dbpedia-fr:Feedback_arc_set dbpedia-fr:Problème_de_l'arbre_de_Steiner dbpedia-fr:Problème_SAT dbpedia-fr:Coupe-cycles_de_sommets dbpedia-fr:Théorème_de_Cook category-fr:Théorie_de_la_complexité_des_algorithmes dbpedia-fr:Set_packing dbpedia-fr:Problème_de_la_couverture_exacte dbpedia-fr:Problème_de_partition dbpedia-fr:Problème_de_la_clique dbpedia-fr:Problème_du_sac_à_dos category-fr:Problème_NP-complet dbpedia-fr:Graphe_hamiltonien dbpedia-fr:Forme_normale_conjonctive dbpedia-fr:Théorie_des_graphes dbpedia-fr:1971_en_informatique dbpedia-fr:Stable_(théorie_des_graphes) dbpedia-fr:Richard_Karp dbpedia-fr:Combinatoire dbpedia-fr:Réduction_polynomiale dbpedia-fr:Problème_3-SAT dbpedia-fr:Ensemble_intersectant dbpedia-fr:Problème_NP-complet dbpedia-fr:Optimisation_linéaire_en_nombres_entiers dbpedia-fr:Problème_de_couverture_par_ensembles dbpedia-fr:Liste_de_problèmes_NP-complets dbpedia-fr:Problème_de_couverture_par_sommets dbpedia-fr:1972 dbpedia-fr:Partition_en_cliques
dbo:wikiPageLength
3081
dct:subject
category-fr:Problème_NP-complet category-fr:Théorie_de_la_complexité_des_algorithmes
prop-fr:wikiPageUsesTemplate
n13:Reducibility_Karp_1972 n13:Références n13:Portail n13:Sources n13:Palette
prov:wasDerivedFrom
wikipedia-fr:21_problèmes_NP-complets_de_Karp?oldid=186128013&ns=0
foaf:isPrimaryTopicOf
wikipedia-fr:21_problèmes_NP-complets_de_Karp
dbo:namedAfter
dbpedia-fr:Richard_Karp dbpedia-fr:Problème_NP-complet
dbo:abstract
Les 21 problèmes NP-complets de Karp ont marqué une étape importante de l'histoire de la théorie de la complexité des algorithmes. Ce sont 21 problèmes réputés difficiles de combinatoire et de théorie des graphes qui sont réductibles entre eux. C'est ce qu'a démontré Richard Karp en 1972 dans son article Reducibility Among Combinatorial Problems, de même que leur NP-complétude.
dbo:creator
dbpedia-fr:Richard_Karp