transformation of one computational problem to another, used to show that the second problem is as difficult as the first
Wikidata facts
Show 3 more facts
- facet of
- problem solving
- Stack Exchange tag
- cstheory.stackexchange.com/tags/reductions
- maintained by WikiProject
- WikiProject Mathematics
Sources (1)
via Wikidata · CC0
Article · 中文
在可計算性理論與計算複雜性理論中，所謂的歸約是將某個轉換為另一個問題的過程。可用歸約法定義某些問題的複雜度類（因轉換過程而異）。 以直覺觀之，如果存在能有效解決問題B的算法，也可以作為解決問題A的子程序，則將問題A稱為「可歸約」到問題B，因此求解A並不會比求解B更困難。 一般寫作A ≤m B，通常也在≤符號下標使用的歸約類型（m：映射縮小，p：多項式縮減）。 將一組問題歸約到特定類型所產生的數學結構，通常形成预序关系，其等價類可用於定義求解難度和複雜度。
Abstract from DBpedia / Wikipedia · CC BY-SA