About: Polynomial-time reduction

Property	Value
dbo:description	Form der Reduktion der theoretischen Informatik (de) method for solving one problem using another (en) metodo per risolvere un problema utilizzando un altro problema (it) різновид звідності (uk) 一種解決另一個問題的方法 (zh)
dbo:wikiPageExternalLink	https://www.youtube.com/watch%3Fv=eHZifpgyH_4
dbo:wikiPageInterLanguageLink	dbpedia-he:רדוקציה_פולינומית
dbo:wikiPageWikiLink	dbr:NC_(complexity) dbr:NL_(complexity) dbr:Stephen_Cook dbr:Undirected_graph dbr:Karp's_21_NP-complete_problems dbr:NP_(complexity) dbc:Reduction_(complexity) dbr:Log-space_reduction dbr:Truth_table dbr:PSPACE dbr:Polynomial_hierarchy dbr:EXPTIME dbr:Many-one_reduction dbr:Crossing_number_(graph_theory) dbr:Formal_language dbr:Contraposition dbr:Existential_theory_of_the_reals dbr:L_(complexity) dbr:Algorithm dbr:Computational_complexity_theory dbr:Polynomial dbr:Complexity_class dbr:P-complete dbr:PSPACE-complete dbr:Reduction_(complexity) dbr:P_(complexity) dbr:GI_(complexity) dbr:Graph_isomorphism_problem dbr:Turing_reduction dbr:Truth-table_reduction dbr:Decision_problem dbr:AM_(complexity) dbr:NP-complete dbr:NP-hard dbr:Richard_Karp dbr:Subroutine dbr:Complete_problem
dbp:wikiPageUsesTemplate	dbt:Reflist dbt:Short_description
dct:subject	dbc:Reduction_(complexity)
gold:hypernym	dbr:Method
rdfs:label	Polynomial-time reduction (en) Polynomialzeitreduktion (de) Réduction polynomiale (fr) Transformación polinómica (es) Riduzione in tempo polinomiale (it) 多項式時間変換 (ja) Redução em tempo polinomial (pt) Полиномиальная сводимость (ru) Поліноміальна звідність (uk) 多项式时间归约 (zh)
owl:sameAs	freebase:Polynomial-time reduction wikidata:Polynomial-time reduction dbpedia-it:Polynomial-time reduction dbpedia-de:Polynomial-time reduction dbpedia-fr:Polynomial-time reduction dbpedia-tr:Polynomial-time reduction dbpedia-zh:Polynomial-time reduction dbpedia-ja:Polynomial-time reduction dbpedia-pt:Polynomial-time reduction dbpedia-es:Polynomial-time reduction dbpedia-ru:Polynomial-time reduction dbpedia-sk:Polynomial-time reduction dbpedia-sr:Polynomial-time reduction dbpedia-uk:Polynomial-time reduction dbpedia-global:Polynomial-time reduction dbr:Polynomial-time reduction
prov:wasDerivedFrom	wikipedia-en:Polynomial-time_reduction?oldid=1158901663&ns=0
foaf:isPrimaryTopicOf	wikipedia-en:Polynomial-time_reduction
is dbo:wikiPageRedirects of	dbr:Polynomial_reduction dbr:Karp_reduction dbr:Polynomial-time_Turing_reduction dbr:Polynomial-time_equivalent dbr:Polynomial-time_many-one_reduction dbr:Polynomial_reducibility dbr:Polynomial_time_equivalent dbr:Polynomial_time_reduction
is dbo:wikiPageWikiLink of	dbr:Polynomial_reduction dbr:Stephen_Cook dbr:NP-completeness dbr:One-way_function dbr:Computer_bridge dbr:List_of_terms_relating_to_algorithms_and_data_structures dbr:SWIFFT dbr:Log-space_reduction dbr:Polynomial_hierarchy dbr:Many-one_reduction dbr:NE_(complexity) dbr:Reductionism dbr:Preorder dbr:Church–Turing_thesis dbr:Existential_theory_of_the_reals dbr:Isolation_lemma dbr:Co-NP dbr:FP_(complexity) dbr:Security_of_cryptographic_hash_functions dbr:Computational_complexity_theory dbr:Boolean_satisfiability_problem dbr:Complexity_class dbr:PSPACE-complete dbr:Reduction_(complexity) dbr:Turing_reduction dbr:PPA_(complexity) dbr:PPP_(complexity) dbr:Graph_homomorphism dbr:Periodic_graph_(geometry) dbr:♯P-completeness_of_01-permanent dbr:Decision_problem dbr:Concrete_security dbr:Reduction_(computability_theory) dbr:Ordered_set_operators dbr:Elliptic_curve_only_hash dbr:L-reduction dbr:Polynomial_creativity dbr:Karp_reduction dbr:Polynomial-time_Turing_reduction dbr:Polynomial-time_equivalent dbr:Polynomial-time_many-one_reduction dbr:Polynomial_reducibility dbr:Polynomial_time_equivalent dbr:Polynomial_time_reduction
is foaf:primaryTopic of	wikipedia-en:Polynomial-time_reduction