Matches in DBpedia 2016-04 for { <http://dbpedia.org/resource/Polynomial-time_reduction> ?p ?o }
Showing triples 1 to 71 of
71
with 100 triples per page.
- Polynomial-time_reduction abstract "In computational complexity theory, a polynomial-time reduction is a method of solving one problem by means of a hypothetical subroutine for solving a different problem (that is, a reduction), that uses polynomial time excluding the time within the subroutine. There are several different types of polynomial-time reduction, depending on the details of how the subroutine is used. Intuitively, a polynomial-time reduction proves that the first problem is no more difficult than the second one, because whenever an efficient algorithm exists for the second problem, one exists for the first problem as well. Polynomial-time reductions are frequently used in complexity theory for defining both complexity classes and complete problems for those classes.".
- Polynomial-time_reduction wikiPageID "159695".
- Polynomial-time_reduction wikiPageLength "9346".
- Polynomial-time_reduction wikiPageOutDegree "40".
- Polynomial-time_reduction wikiPageRevisionID "649824703".
- Polynomial-time_reduction wikiPageWikiLink Algorithm.
- Polynomial-time_reduction wikiPageWikiLink Arthur–Merlin_protocol.
- Polynomial-time_reduction wikiPageWikiLink Category:Computational_complexity_theory.
- Polynomial-time_reduction wikiPageWikiLink Complete_(complexity).
- Polynomial-time_reduction wikiPageWikiLink Complexity_class.
- Polynomial-time_reduction wikiPageWikiLink Computational_complexity_theory.
- Polynomial-time_reduction wikiPageWikiLink Crossing_number_(graph_theory).
- Polynomial-time_reduction wikiPageWikiLink Decision_problem.
- Polynomial-time_reduction wikiPageWikiLink EXPTIME.
- Polynomial-time_reduction wikiPageWikiLink Existential_theory_of_the_reals.
- Polynomial-time_reduction wikiPageWikiLink Graph_(discrete_mathematics).
- Polynomial-time_reduction wikiPageWikiLink Graph_isomorphism_problem.
- Polynomial-time_reduction wikiPageWikiLink Karps_21_NP-complete_problems.
- Polynomial-time_reduction wikiPageWikiLink L_(complexity).
- Polynomial-time_reduction wikiPageWikiLink Log-space_reduction.
- Polynomial-time_reduction wikiPageWikiLink Many-one_reduction.
- Polynomial-time_reduction wikiPageWikiLink NC_(complexity).
- Polynomial-time_reduction wikiPageWikiLink NL_(complexity).
- Polynomial-time_reduction wikiPageWikiLink NP-completeness.
- Polynomial-time_reduction wikiPageWikiLink NP-hardness.
- Polynomial-time_reduction wikiPageWikiLink NP_(complexity).
- Polynomial-time_reduction wikiPageWikiLink P-complete.
- Polynomial-time_reduction wikiPageWikiLink PSPACE.
- Polynomial-time_reduction wikiPageWikiLink PSPACE-complete.
- Polynomial-time_reduction wikiPageWikiLink P_(complexity).
- Polynomial-time_reduction wikiPageWikiLink Polynomial_hierarchy.
- Polynomial-time_reduction wikiPageWikiLink Polynomial_transformations.
- Polynomial-time_reduction wikiPageWikiLink Reduction_(complexity).
- Polynomial-time_reduction wikiPageWikiLink Richard_M._Karp.
- Polynomial-time_reduction wikiPageWikiLink Stephen_Cook.
- Polynomial-time_reduction wikiPageWikiLink Subroutine.
- Polynomial-time_reduction wikiPageWikiLink Time_complexity.
- Polynomial-time_reduction wikiPageWikiLink Truth-table_reduction.
- Polynomial-time_reduction wikiPageWikiLink Truth_table.
- Polynomial-time_reduction wikiPageWikiLink Turing_reduction.
- Polynomial-time_reduction wikiPageWikiLinkText "Polynomial-time reduction".
- Polynomial-time_reduction wikiPageWikiLinkText "polynomial equivalence".
- Polynomial-time_reduction wikiPageWikiLinkText "polynomial reductions".
- Polynomial-time_reduction wikiPageWikiLinkText "polynomial time reducible".
- Polynomial-time_reduction wikiPageWikiLinkText "polynomial-time Turing reduction".
- Polynomial-time_reduction wikiPageWikiLinkText "polynomial-time many-one reduction".
- Polynomial-time_reduction wikiPageWikiLinkText "polynomial-time reducibility".
- Polynomial-time_reduction wikiPageWikiLinkText "polynomial-time reducible".
- Polynomial-time_reduction wikiPageWikiLinkText "polynomial-time reduction".
- Polynomial-time_reduction wikiPageWikiLinkText "polynomial-time".
- Polynomial-time_reduction wikiPageWikiLinkText "reducible".
- Polynomial-time_reduction wikiPageWikiLinkText "reduction".
- Polynomial-time_reduction wikiPageWikiLinkText "transformed to it in polynomial time".
- Polynomial-time_reduction wikiPageUsesTemplate Template:Reflist.
- Polynomial-time_reduction subject Category:Computational_complexity_theory.
- Polynomial-time_reduction hypernym Method.
- Polynomial-time_reduction type Software.
- Polynomial-time_reduction comment "In computational complexity theory, a polynomial-time reduction is a method of solving one problem by means of a hypothetical subroutine for solving a different problem (that is, a reduction), that uses polynomial time excluding the time within the subroutine. There are several different types of polynomial-time reduction, depending on the details of how the subroutine is used.".
- Polynomial-time_reduction label "Polynomial-time reduction".
- Polynomial-time_reduction sameAs Q2103034.
- Polynomial-time_reduction sameAs Polynomialzeitreduktion.
- Polynomial-time_reduction sameAs Transformación_polinómica.
- Polynomial-time_reduction sameAs Réduction_polynomiale.
- Polynomial-time_reduction sameAs 多項式時間変換.
- Polynomial-time_reduction sameAs Redução_em_tempo_polinomial.
- Polynomial-time_reduction sameAs m.01529y.
- Polynomial-time_reduction sameAs Polynomiálna_transformovateľnosť.
- Polynomial-time_reduction sameAs Çokterimli_zamanda_indirgeme.
- Polynomial-time_reduction sameAs Q2103034.
- Polynomial-time_reduction wasDerivedFrom Polynomial-time_reduction?oldid=649824703.
- Polynomial-time_reduction isPrimaryTopicOf Polynomial-time_reduction.