歸約是指問(wèn)題A的任何實(shí)例能用問(wèn)題B的方法來(lái)解決（判斷）盖彭，并且A的解為“是”，當(dāng)且僅當(dāng)B的解也是“是”喻圃。因此蒋纬，證明歸約是雙向的橄碾，目前遇到的大多歸約問(wèn)題（A ≤p B）都可以按以下步驟進(jìn)行：
- 構(gòu)造圖G，存在問(wèn)題A的解集颠锉；
- 在圖G基礎(chǔ)上，構(gòu)造圖G'（常添加邊或點(diǎn)）史汗，使得問(wèn)題A的解集能反應(yīng)在G'中問(wèn)題B的解集（注意兩個(gè)問(wèn)題解集的規(guī)模k一定要有確定的聯(lián)系）琼掠；
- Claim：“圖G中存在問(wèn)題A的解集S，當(dāng)且僅當(dāng)圖G'中存在問(wèn)題B的解集S' ”停撞；
- 雙向證明瓷蛙，注意不要弄反方向。
也有不用構(gòu)造新圖的戈毒，比如點(diǎn)覆蓋到獨(dú)立集的規(guī)約艰猬，這種方法叫直接規(guī)約。但大多有些難度的歸約一般都需要構(gòu)造埋市。除了前面筆記寫的一部分歸約證明冠桃，下面整理了老師說(shuō)的需要重點(diǎn)掌握的歸約。
Subset-Sum ≤p Partition
Partition：集合能劃分成和相等的兩部分道宅。
構(gòu)造子集和問(wèn)題的實(shí)例食听，如集合胸蛛，子集和為W，需構(gòu)造集合S'樱报，使得集合S存在一個(gè)子集之和為W葬项，當(dāng)且僅當(dāng)集合S'存在一個(gè)partition（
）
思路：構(gòu)造集合，其中
,
=>
S存在一個(gè)子集迹蛤，有
那么集合S'中民珍，有
所以集合S'存在一個(gè)劃分和
<=
集合S'能被劃分為兩個(gè)和相等的集合，可知和
不在一個(gè)劃分子集里
那么盗飒，存在一個(gè)集合A嚷量，設(shè)其元素之和為Y，有
解出箩兽，即...
Subset-Sum ≤p Knapsack
Knapsack：給定物品的集合X津肛，每個(gè)物品有重量和價(jià)值
，背包最多承重
汗贫，目標(biāo)價(jià)值
身坐。問(wèn)是否存在物品的一個(gè)子集S，使得
,
落包？
第一步構(gòu)造Knapsack的實(shí)例部蛇，第二步證明集合X存在一個(gè)子集之和為W，當(dāng)且僅當(dāng)構(gòu)造的Knapsack具有可行方案咐蝇。
對(duì)一個(gè)子集和問(wèn)題的實(shí)例涯鲁，構(gòu)造Knapsack實(shí)例
，滿足
,
,
證明略（別的不會(huì)有序，略學(xué)得很像樣）抹腿。
Subset-Sum ≤p Schedule
Schedule：一個(gè)工作序列，每個(gè)工作具有到達(dá)時(shí)間旭寿，處理時(shí)間
警绩，最遲完成時(shí)間
，問(wèn)如何安排這些工作盅称，使得完成所有工作所需時(shí)間最短（在到達(dá)時(shí)間之后開(kāi)始處理肩祥、最遲完成時(shí)間之前結(jié)束處理）？
思路：對(duì)于給定的集合和W缩膝，構(gòu)造一個(gè)工作安排實(shí)例混狠，證明若存在子集之和為W，當(dāng)且僅當(dāng)存在可行的工作安排疾层。
集合将饺，構(gòu)造n個(gè)工作（從1開(kāi)始編號(hào)），有
,
,
，就是對(duì)到達(dá)時(shí)間和最遲完成時(shí)間沒(méi)有要求俯逾；再創(chuàng)建0號(hào)工作贸桶，
,
,
.
這個(gè)證明就比較顯而易見(jiàn)，但這個(gè)構(gòu)造也太奇怪了桌肴，就是通過(guò)設(shè)置工作的到達(dá)時(shí)間和最遲完成時(shí)間來(lái)固定安排它們的位置皇筛。為什么可以構(gòu)造這樣的特例來(lái)證明呢？因?yàn)閄≤pY坠七，Y本身就是一個(gè)比X難的問(wèn)題水醋，那么我們就可以把Y的更多的約束條件舍去，讓它變成和X比較相像或者復(fù)雜度相當(dāng)?shù)腘PC問(wèn)題。
Partition ≤p Load-Balance
集合，構(gòu)造Load-Balance實(shí)例
持钉，且每個(gè)工作的處理時(shí)間
芽腾，
蔑穴，有
.
證明略。
