歸約維基百科,自由的 encyclopedia 在可計算性理論與計算複雜性理論中,所謂的歸約是將某個計算問題(英語:computational problem)轉換為另一個問題的過程。可用歸約法定義某些問題的複雜度類(因轉換過程而異)。 Example of a reduction from the boolean satisfiability problem (A ∨ B) ∧ (¬A ∨ ¬B ∨ ¬C) ∧ (¬A ∨ B ∨ C) to a vertex cover problem. The blue vertices form a minimum vertex cover, and the blue vertices in the gray oval correspond to a satisfying truth assignment for the original formula. 以直覺觀之,如果存在能有效解決問題B的算法,也可以作為解決問題A的子程序,則將問題A稱為「可歸約」到問題B,因此求解A並不會比求解B更困難。 一般寫作A ≤m B,通常也在≤符號下標使用的歸約類型(m:映射縮小,p:多項式縮減)。 將一組問題歸約到特定類型所產生的數學結構,通常形成預序關係,其等價類可用於定義求解難度和複雜度。
在可計算性理論與計算複雜性理論中,所謂的歸約是將某個計算問題(英語:computational problem)轉換為另一個問題的過程。可用歸約法定義某些問題的複雜度類(因轉換過程而異)。 Example of a reduction from the boolean satisfiability problem (A ∨ B) ∧ (¬A ∨ ¬B ∨ ¬C) ∧ (¬A ∨ B ∨ C) to a vertex cover problem. The blue vertices form a minimum vertex cover, and the blue vertices in the gray oval correspond to a satisfying truth assignment for the original formula. 以直覺觀之,如果存在能有效解決問題B的算法,也可以作為解決問題A的子程序,則將問題A稱為「可歸約」到問題B,因此求解A並不會比求解B更困難。 一般寫作A ≤m B,通常也在≤符號下標使用的歸約類型(m:映射縮小,p:多項式縮減)。 將一組問題歸約到特定類型所產生的數學結構,通常形成預序關係,其等價類可用於定義求解難度和複雜度。