This HTML5 document contains 63 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/
n8http://g.co/kg/m/
dbpedia-ruhttp://ru.dbpedia.org/resource/
dbpedia-ukhttp://uk.dbpedia.org/resource/
rdfshttp://www.w3.org/2000/01/rdf-schema#
category-frhttp://fr.dbpedia.org/resource/Catégorie:
dbpedia-plhttp://pl.dbpedia.org/resource/
dbpedia-pthttp://pt.dbpedia.org/resource/
n15http://fr.dbpedia.org/resource/Modèle:
dbpedia-cshttp://cs.dbpedia.org/resource/
n17http://fr.dbpedia.org/resource/Modèle:Traduction/
wikipedia-frhttp://fr.wikipedia.org/wiki/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
owlhttp://www.w3.org/2002/07/owl#
n16http://ma-graph.org/entity/
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#
dbpedia-idhttp://id.dbpedia.org/resource/
wikidatahttp://www.wikidata.org/entity/
dbrhttp://dbpedia.org/resource/

Statements

Subject Item
dbpedia-fr:Temps_de_calcul_pseudo-polynomial
rdfs:label
Псевдополіноміальний алгоритм Temps de calcul pseudo-polynomial Pseudopolynomiell 伪多项式时间 Tiempo pseudo-polinómico
rdfs:comment
En informatique théorique, et notamment en théorie de la complexité, un algorithme est appelé pseudo-polynomial si sa complexité en temps est un polynôme en la valeur numérique de l'entrée (mais pas nécessairement en la taille en mémoire de l'entrée).
owl:sameAs
dbpedia-pt:Tempo_pseudopolinomial n8:08vmbm dbpedia-cs:Pseudopolynomická_časová_složitost dbpedia-pl:Algorytm_pseudowielomianowy dbr:Pseudo-polynomial_time dbpedia-uk:Псевдополіноміальний_алгоритм n16:167907120 dbpedia-zh:伪多项式时间 wikidata:Q155291 dbpedia-de:Pseudopolynomiell dbpedia-ru:Псевдополиномиальный_алгоритм dbpedia-es:Tiempo_pseudo-polinómico dbpedia-id:Waktu_semu-polinomial
dbo:wikiPageID
8805005
dbo:wikiPageRevisionID
178790112
dbo:wikiPageWikiLink
dbpedia-fr:Nombre_premier dbpedia-fr:Problème_P_≟_NP dbpedia-fr:Addition dbpedia-fr:Problème_NP-complet dbpedia-fr:Test_de_primalité dbpedia-fr:Polynôme dbpedia-fr:Théorie_de_la_complexité_(informatique_théorique) dbpedia-fr:Problème_du_sac_à_dos dbpedia-fr:Informatique_théorique dbpedia-fr:W._H._Freeman_and_Company dbpedia-fr:Complexité_en_temps dbpedia-fr:NP-difficile category-fr:Algorithmique category-fr:Théorie_de_la_complexité_des_algorithmes dbpedia-fr:Algorithme
dbo:wikiPageLength
3889
dct:subject
category-fr:Théorie_de_la_complexité_des_algorithmes category-fr:Algorithmique
prop-fr:wikiPageUsesTemplate
n15:Lien n17:Référence n15:Ouvrage n15:Portail n15:Références
prov:wasDerivedFrom
wikipedia-fr:Temps_de_calcul_pseudo-polynomial?oldid=178790112&ns=0
prop-fr:année
1979
prop-fr:auteur
Michael R. Garey David S. Johnson
prop-fr:fr
problème fortement NP-complet problème faiblement NP-complet
prop-fr:id
GJ
prop-fr:isbn
0
prop-fr:lang
en
prop-fr:langue
en
prop-fr:lieu
New York
prop-fr:pagesTotales
338
prop-fr:sousTitre
A Guide to the Theory of NP-Completeness
prop-fr:titre
Computers and Intractability
prop-fr:trad
Strongly NP-complete weakly NP-complete
prop-fr:éditeur
dbpedia-fr:W._H._Freeman_and_Company
foaf:isPrimaryTopicOf
wikipedia-fr:Temps_de_calcul_pseudo-polynomial
dbo:abstract
En informatique théorique, et notamment en théorie de la complexité, un algorithme est appelé pseudo-polynomial si sa complexité en temps est un polynôme en la valeur numérique de l'entrée (mais pas nécessairement en la taille en mémoire de l'entrée).