About: Certificate (complexity)

An Entity of Type: Thing, from Named Graph: http://dbpedia.org, within Data Space: dbpedia-live.demo.openlinksw.com

String that certifies the answer to a computation

Property	Value
dbo:description	string that certifies the answer to a computation (de) string that certifies the answer to a computation (en) рядок, який засвідчує відповідь на обчислення (uk)
dbo:wikiPageExternalLink	http://www.cs.princeton.edu/theory/complexity/dectreechap.pdf
dbo:wikiPageWikiLink	dbr:NL_(complexity) dbr:Decision_tree_model dbr:NP_(complexity) dbr:Independent_set_(graph_theory) dbc:Computational_complexity_theory dbr:Formal_language dbr:Co-NP dbr:Computability dbr:Nondeterministic_Turing_machine dbr:Computational_complexity_theory dbr:Turing_machine dbr:Boolean_function dbr:Decision_tree dbr:Relation_(mathematics) dbr:Witness_(mathematics) dbr:Polynomial-time dbr:Semi-decidability
dbp:wikiPageUsesTemplate	dbt:Reflist dbt:Citation dbt:Short_description
dct:subject	dbc:Computational_complexity_theory
rdfs:label	Certificate (complexity) (en) Certificat (complexité) (fr) Certificado (complexidade) (pt) Сертифікат (складність обчислень) (uk)
owl:sameAs	freebase:Certificate (complexity) wikidata:Certificate (complexity) dbpedia-fr:Certificate (complexity) dbpedia-pt:Certificate (complexity) dbpedia-uk:Certificate (complexity) dbpedia-global:Certificate (complexity) dbr:Certificate (complexity)
prov:wasDerivedFrom	wikipedia-en:Certificate_(complexity)?oldid=1276648314&ns=0
foaf:isPrimaryTopicOf	wikipedia-en:Certificate_(complexity)
is dbo:wikiPageDisambiguates of	dbr:Certificate
is dbo:wikiPageRedirects of	dbr:Witness_(complexity) dbr:Certificate_(math) dbr:Certificate_complexity
is dbo:wikiPageWikiLink of	dbr:NL_(complexity) dbr:Decision_tree_model dbr:P_versus_NP_problem dbr:NP_(complexity) dbr:QMA dbr:♯P dbr:Co-NP dbr:Probabilistically_checkable_proof dbr:Complexity_class dbr:Constructive_set_theory dbr:Polynomial_creativity dbr:Witness_(mathematics) dbr:Certificate dbr:NLTS_Conjecture dbr:Witness_(complexity) dbr:Certificate_(math) dbr:Certificate_complexity
is foaf:primaryTopic of	wikipedia-en:Certificate_(complexity)