![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/0/02/3SAT_reduced_too_VC.svg/langzh-mo-640px-3SAT_reduced_too_VC.svg.png&w=640&q=50)
歸約
維基百科,自由的 encyclopedia
在可計算性理論與計算複雜性理論中,所謂的歸約是將某個計算問題(英語:computational problem)轉換為另一個問題的過程。可用歸約法定義某些問題的複雜度類(因轉換過程而異)。
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/0/02/3SAT_reduced_too_VC.svg/320px-3SAT_reduced_too_VC.svg.png)
以直覺觀之,如果存在能有效解決問題B的演算法,也可以作為解決問題A的子程式,則將問題A稱為「可歸約」到問題B,因此求解A並不會比求解B更困難。
一般寫作A ≤m B,通常也在≤符號下標使用的歸約類型(m:對映縮小,p:多項式縮減)。
將一組問題歸約到特定類型所產生的數學結構,通常形成預序關係,其等價類可用於定義求解難度和複雜度。