Matches in DBpedia 2014 for { <http://dbpedia.org/resource/Reduction_(complexity)> ?p ?o. }
Showing items 1 to 28 of
28
with 100 items per page.
- 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 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) wikiPageRevisionID "589970252".
- Reduction_(complexity) hasPhotoCollection Reduction_(complexity).
- Reduction_(complexity) subject Category:Computational_complexity_theory.
- Reduction_(complexity) subject Category:Structural_complexity_theory.
- 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 as difficult as the first.".
- Reduction_(complexity) label "Reducción (complejidad)".
- Reduction_(complexity) label "Reduction (complexity)".
- Reduction_(complexity) label "Reduktion (Theoretische Informatik)".
- Reduction_(complexity) label "Redução (complexidade)".
- Reduction_(complexity) label "Réduction (complexité)".
- Reduction_(complexity) label "Сведение (теория сложности вычислений)".
- Reduction_(complexity) label "歸約".
- Reduction_(complexity) label "還元 (計算複雑性理論)".
- Reduction_(complexity) sameAs Reduktion_(Theoretische_Informatik).
- Reduction_(complexity) sameAs Reducción_(complejidad).
- Reduction_(complexity) sameAs Réduction_(complexité).
- Reduction_(complexity) sameAs 還元_(計算複雑性理論).
- Reduction_(complexity) sameAs 환산_(복잡도).
- Reduction_(complexity) sameAs Redução_(complexidade).
- Reduction_(complexity) sameAs m.03gsxd.
- Reduction_(complexity) sameAs Q1197709.
- Reduction_(complexity) sameAs Q1197709.
- Reduction_(complexity) wasDerivedFrom Reduction_(complexity)?oldid=589970252.
- Reduction_(complexity) depiction 3SAT_reduced_too_VC.svg.
- Reduction_(complexity) isPrimaryTopicOf Reduction_(complexity).
