DBpedia – Linked Data Fragments

Matches in DBpedia 2015-10 for { <http://dbpedia.org/resource/Reduction_(complexity)> ?p ?o }

• Reduction_(complexity) abstract "In computability theory and computational complexity theory, a reduction is an algorithm for transforming one problem into another problem. A reduction from one problem to another may be used to show that the second problem is at least as difficult as the first. The mathematical structure generated on a set of problems by the reductions of a particular type generally forms a preorder, whose equivalence classes may be used to define degrees of unsolvability and complexity classes.Intuitively, problem A is reducible to problem B if an algorithm for solving problem B efficiently (if it existed) could also be used as a subroutine to solve problem A efficiently. When this is true, solving A cannot be harder than solving B. We write A ≤m B, usually with a subscript on the ≤ to indicate the type of reduction being used (m : mapping reduction, p : polynomial reduction).".
• Reduction_(complexity) thumbnail 3SAT_reduced_too_VC.svg?width=300.
• Reduction_(complexity) wikiPageID "848067".
• Reduction_(complexity) wikiPageLength "11490".
• Reduction_(complexity) wikiPageOutDegree "63".
• Reduction_(complexity) wikiPageRevisionID "683700162".
• Reduction_(complexity) wikiPageWikiLink Algorithm.
• Reduction_(complexity) wikiPageWikiLink Approximation-preserving_reduction.
• Reduction_(complexity) wikiPageWikiLink Approximation_algorithm.
• Reduction_(complexity) wikiPageWikiLink Boolean_satisfiability_problem.
• Reduction_(complexity) wikiPageWikiLink Category:Computational_complexity_theory.
• Reduction_(complexity) wikiPageWikiLink Category:Structural_complexity_theory.
• Reduction_(complexity) wikiPageWikiLink Complete_(complexity).
• Reduction_(complexity) wikiPageWikiLink Complexity_class.
• Reduction_(complexity) wikiPageWikiLink Computability_theory.
• Reduction_(complexity) wikiPageWikiLink Computable_function.
• Reduction_(complexity) wikiPageWikiLink Computational_complexity_theory.
• Reduction_(complexity) wikiPageWikiLink Computational_problem.
• Reduction_(complexity) wikiPageWikiLink Decision_problem.
• Reduction_(complexity) wikiPageWikiLink Equivalence_class.
• Reduction_(complexity) wikiPageWikiLink Function_(mathematics).
• Reduction_(complexity) wikiPageWikiLink Function_composition.
• Reduction_(complexity) wikiPageWikiLink Gadget_(computer_science).
• Reduction_(complexity) wikiPageWikiLink Halting_problem.
• Reduction_(complexity) wikiPageWikiLink Hardness_of_approximation.
• Reduction_(complexity) wikiPageWikiLink Irrational_number.
• Reduction_(complexity) wikiPageWikiLink L_(complexity).
• Reduction_(complexity) wikiPageWikiLink Log-space_reduction.
• Reduction_(complexity) wikiPageWikiLink Many-one_reduction.
• Reduction_(complexity) wikiPageWikiLink NC_(complexity).
• Reduction_(complexity) wikiPageWikiLink NL_(complexity).
• Reduction_(complexity) wikiPageWikiLink NP-complete.
• Reduction_(complexity) wikiPageWikiLink NP-completeness.
• Reduction_(complexity) wikiPageWikiLink NP_(complexity).
• Reduction_(complexity) wikiPageWikiLink Natural_number.
• Reduction_(complexity) wikiPageWikiLink PSPACE.
• Reduction_(complexity) wikiPageWikiLink P_(complexity).
• Reduction_(complexity) wikiPageWikiLink Polynomial-time_reduction.
• Reduction_(complexity) wikiPageWikiLink Polynomial_hierarchy.
• Reduction_(complexity) wikiPageWikiLink Power_set.
• Reduction_(complexity) wikiPageWikiLink Preorder.
• Reduction_(complexity) wikiPageWikiLink Reduction_(recursion_theory).
• Reduction_(complexity) wikiPageWikiLink Reflexive_relation.
• Reduction_(complexity) wikiPageWikiLink Subset.
• Reduction_(complexity) wikiPageWikiLink Transitive_relation.
• Reduction_(complexity) wikiPageWikiLink Truth-table_reduction.
• Reduction_(complexity) wikiPageWikiLink Truth_table_reduction.
• Reduction_(complexity) wikiPageWikiLink Turing_degree.
• Reduction_(complexity) wikiPageWikiLink Turing_machine.
• Reduction_(complexity) wikiPageWikiLink Turing_reduction.
• Reduction_(complexity) wikiPageWikiLink Undecidable_problem.
• Reduction_(complexity) wikiPageWikiLink File:3SAT_reduced_too_VC.svg.
• Reduction_(complexity) wikiPageWikiLinkText "Reduction (complexity)".
• Reduction_(complexity) wikiPageWikiLinkText "Reduction of complexity".
• Reduction_(complexity) wikiPageWikiLinkText "Reduction".
• Reduction_(complexity) wikiPageWikiLinkText "Reductions".
• Reduction_(complexity) wikiPageWikiLinkText "formal reduction".
• Reduction_(complexity) wikiPageWikiLinkText "proof by reduction".
• Reduction_(complexity) wikiPageWikiLinkText "reduce".
• Reduction_(complexity) wikiPageWikiLinkText "reduced".
• Reduction_(complexity) wikiPageWikiLinkText "reduces".
• Reduction_(complexity) wikiPageWikiLinkText "reducible".
• Reduction_(complexity) wikiPageWikiLinkText "reducing".
• Reduction_(complexity) wikiPageWikiLinkText "reduction argument".
• Reduction_(complexity) wikiPageWikiLinkText "reduction".
• Reduction_(complexity) wikiPageWikiLinkText "reductions".
• Reduction_(complexity) wikiPageWikiLinkText "reductive".
• Reduction_(complexity) wikiPageWikiLinkText "security reduction".
• Reduction_(complexity) hasPhotoCollection Reduction_(complexity).
• Reduction_(complexity) subject Category:Computational_complexity_theory.
• Reduction_(complexity) subject Category:Structural_complexity_theory.
• Reduction_(complexity) hypernym Algorithm.
• Reduction_(complexity) type Software.
• Reduction_(complexity) comment "In computability theory and computational complexity theory, a reduction is an algorithm for transforming one problem into another problem. A reduction from one problem to another may be used to show that the second problem is at least as difficult as the first.".
• Reduction_(complexity) label "Reduction (complexity)".
• Reduction_(complexity) sameAs Reducció_(complexitat).
• Reduction_(complexity) sameAs Reduktion_(Theoretische_Informatik).
• Reduction_(complexity) sameAs Reducción_(complejidad).
• Reduction_(complexity) sameAs تقلیل_(پیچیدگی).
• Reduction_(complexity) sameAs Réduction_(complexité).
• Reduction_(complexity) sameAs רדוקציה_חישובית.
• Reduction_(complexity) sameAs 還元_(計算複雑性理論).
• Reduction_(complexity) sameAs 환산_(복잡도).
• Reduction_(complexity) sameAs Redução_(complexidade).
• Reduction_(complexity) sameAs m.03gsxd.
• Reduction_(complexity) sameAs Сведение_(теория_сложности_вычислений).
• Reduction_(complexity) sameAs Redukcia_(teoretická_informatika).
• Reduction_(complexity) sameAs Reduktion_(datalogi).
• Reduction_(complexity) sameAs การลดรูป_(ความซับซ้อน).
• Reduction_(complexity) sameAs Q1197709.
• Reduction_(complexity) sameAs Q1197709.
• Reduction_(complexity) sameAs 歸約.
• Reduction_(complexity) wasDerivedFrom Reduction_(complexity)?oldid=683700162.
• Reduction_(complexity) depiction 3SAT_reduced_too_VC.svg.
• Reduction_(complexity) isPrimaryTopicOf Reduction_(complexity).