About: Complete (complexity)

An Entity of Type: Thing, from Named Graph: http://dbpedia.org, within Data Space: dbpedia.org

Notion of the \hardest\ or \most general\ problem in a complexity class

Property	Value
dbo:description	notion of the \hardest\ or \most general\ problem in a complexity class (en)
dbo:wikiPageWikiLink	dbr:Oracle_machine dbr:NP_(complexity) dbc:Computational_complexity_theory dbr:Co-NP dbr:Computational_complexity_theory dbr:Complexity_class dbr:Reduction_(complexity) dbr:PLS_(complexity) dbr:PPA_(complexity) dbr:Computational_problem dbr:NP-complete dbr:NP-hard
dbp:wikiPageUsesTemplate	dbt:Reflist dbt:Refimprove dbt:Short_description
dct:subject	dbc:Computational_complexity_theory
rdfs:label	Complete (complexity) (en) Schwere und Vollständigkeit (theoretische Informatik) (de) Complet (complexité) (fr) Completo (complessità) (it) Completo (complexidade) (pt) 完備 (複雜度) (zh)
owl:sameAs	freebase:Complete (complexity) wikidata:Complete (complexity) dbpedia-it:Complete (complexity) dbpedia-de:Complete (complexity) dbpedia-fr:Complete (complexity) dbpedia-zh:Complete (complexity) dbpedia-pt:Complete (complexity) dbpedia-sr:Complete (complexity) dbpedia-global:Complete (complexity)
prov:wasDerivedFrom	wikipedia-en:Complete_(complexity)?oldid=1083420704&ns=0
foaf:isPrimaryTopicOf	wikipedia-en:Complete_(complexity)
is dbo:wikiPageRedirects of	dbr:Complete_problem dbr:Hard_(complexity)
is dbo:wikiPageWikiLink of	dbr:Oracle_machine dbr:NP-completeness dbr:LOGCFL dbr:Log-space_reduction dbr:Alexei_Kitaev dbr:Digi-Comp_II dbr:NL-complete dbr:Steinitz's_theorem dbr:Crossing_number_(graph_theory) dbr:QMA dbr:Existential_theory_of_the_reals dbr:Handshaking_lemma dbr:Clique_problem dbr:L_(complexity) dbr:Completeness dbr:Computational_complexity_theory dbr:Complexity_class dbr:P-complete dbr:Reduction_(complexity) dbr:UP_(complexity) dbr:Oblivious_transfer dbr:Jean_Charles_Athanase_Peltier dbr:BQP dbr:Intersection_graph dbr:Graph_isomorphism_problem dbr:PPAD_(complexity) dbr:PPA_(complexity) dbr:PPP_(complexity) dbr:PTAS_reduction dbr:First-order_reduction dbr:Group_testing dbr:Arrangement_of_lines dbr:Computational_hardness_assumption dbr:Configuration_graph dbr:Approximation-preserving_reduction dbr:Resource_bounded_measure dbr:Polynomial-time_counting_reduction dbr:Games,_Puzzles,_and_Computation dbr:MAX-3SAT dbr:Metric_temporal_logic dbr:One_Clean_Qubit dbr:SNP_(complexity) dbr:Descriptive_Complexity dbr:Complete_problem dbr:Hard_(complexity)
is owl:differentFrom of	dbr:Completeness_(logic)
is foaf:primaryTopic of	wikipedia-en:Complete_(complexity)