1.吝啬SAT問題
8.3吝啬SAT問題是這樣的：給定一組子句（每個子句都是其中文字的析取）和整數k，求一個最多有k個變量為true的滿足指派——如果該指派存在。證明吝啬問題是NP-完全問題。
證明：
易得吝啬SAT問題是NP問題。
已知SAT是NP完全問題，是以，隻要能把SAT歸約到吝啬SAT問題，即可證明。
歸約過程：假設SAT問題有n個變量，即等價于k=n的吝啬SAT問題。命題得證。
2. 4 SAT問題
8.8.在精确的4SAT問題中，輸入為一組子句。每個子句都是恰好4個文字的析取，且每個變量最多在每個子句中出現一次，目标是求它的滿足賦——如果指派存在。
證明：
易得4SAT問題是NP問題。
已知3SAT問題是NP完全問題。現将3SAT問題歸約到4SAT上。歸約時，一要保證每個變量在子句中隻出現一次，二要讓每個子句恰好有4個文字。
歸約過程：對于任意一個3SAT執行個體， 若一個文字出現多次，可将該文字删減為一次或零次（即肯定或否定同時出現）。再添加一寫無關的輔助變量。這樣即可将每個子句的文字擴充到4個。
3.碰撞集問題
8.9.在碰撞集問題中，給定一組集合{S1,S2,S3….Sn}和預算b，我們希望求一個所有的Si相交且規模不大于b的集合H，當然，前提是這樣的集合确實存在。
證明：
易證，這是個NP問題
将最小頂點覆寫歸約到碰撞集問題。現假設求圖G的最小頂點覆寫，我們可以建立一個碰撞集執行個體。其中S1,S2,��,Sn即是圖G的各條邊,比如
{v1,v2},{v3,v4}….。這樣，就可以把求G的最小頂點覆寫歸約成，求這|E|個集合的碰撞集H。其中H的大小b就是最小頂點覆寫。已知最小頂點覆寫是一個NP完全問題，是以該問題是一個NP完全問題。
4.利用推廣的方法證明NP-完全性。
8.10.
(a)子圖同構：給定兩個作為輸入的無向圖G和H，判斷G是否與H的某個子圖同構，且如果是，傳回由V(G)到V(H)的相關映射。
證明：
令圖G為一個環，環上的頂點數等于圖H的頂點數。那麼若G是H的同構子 圖,則說明 H 存在 Rudrata 回路。是以， Rudrata 回路事實上是子圖同構問題的一個特例。
(b)最長路徑：給定圖G和整數g，求G中一條長為g的簡單路徑。
證明：
令g = |V| - 1， 則實際上在求一條Rudrata 路徑。
(c)最大SAT：給定一個CNF公式和整數g，求滿足其中至少g個子句的真指派。
證明：
令g為子句的總數，則成了SAT問題。
(d)稠密子圖：給定一個圖和兩個整數a,b，求G中的a個頂點，使得他們之間最少有b條邊。
證明：
令b= a(a−1)/2，則問題變成了最大團問題。
(e)稀疏子圖：給定一個圖和兩個整數a和b，求G中的a個頂點，使得它們之間最多有b條邊。
證明：
令b=0， 則問題變成了最大獨立集問題。
(f)集合覆寫
證明：
集合覆寫就是最小頂點覆寫的一個推廣。将G={V,E}，以及最小頂點覆寫k，推廣成集合覆寫的全集S，子集Ci，以及集合覆寫k。其中令S = V；Ci為與頂點i有連邊的邊集。則集合覆寫k等于最小頂點覆寫k。
(g)可靠網絡：給定兩個n*n矩陣，一個距離矩陣dij，一個連接配接需求矩陣rij以及預算b。我們要求一個圖G={{1,2,3,….N},E}使得：(1)其中所有邊的總代價不超過b；(2)在任意兩個不同的頂點i和j之間，存在rij條頂點互不相交的路徑。
證明：
假設所有dij都為1或2，b=n，所有的rij=2， 則這是一個TSP問題。
5.NODE-DISJOINT PATH
8.23.在結點互不相交的路徑問題中，輸入是一個無向圖。該圖的一些結點具有特殊标記：節點s1,s2,…,sk 被标記為“出發點”，另一些相同數量的節點t1,t2,…,tk 被标記為“目的地”。目标是對所有的i=1,2,…,k，求由si 到ti 的k條互不相交的路徑（即不包含相同節點的路徑）。請證明該問題是NP完全的。
證明：
易證，該問題是一個NP問題。
現從 3SAT 問題開始歸約。
歸約過程如下：
i.對于包含 m 個子句和 n 個變量的 3SAT 公式，使用 k = m + n 個出發點和目的地。 每個變量 v對應于一個節點對(sx,tx) ，每個子句 c 對應于一個節點對(sc,tc) 。
ii.對每個 3SAT 子句(v1∨v2∨v3) ，引入6個中間節點:v1,v2,v3,~v1,~v2,~v3。即對于出現在子句中的每個文字都有一個節點與之對應，同時還有另一個節點對應于該文字的補。
iii.注意到如果Sc到Tc的路徑經過某個中間節點（代表變量x在子句中出現過），則其他路徑不能再經過該結點。對于任意子句c=(v1∨v2∨v3),分别将sc與vi、vi與tc連結起來形成三條路徑,因為任意vi為真都使得c為真。
iv.對于每個變量x，将sx與所有x串聯起來，再連向 tx ,進而形成一條路徑。再将sx與所有 ~x 串聯起來，連向 tx，又形成一條路徑。在這兩條路徑中，必然要選擇其中一條，如果有任意子句選擇了，則其餘子句就不能再選擇 v。
下面舉 一個簡單的例子,假設要驗證 CNF:(x ∨ y ∨ z)(~x ∨ y ∨ ~z )是否可以被滿足,令u = ( x ∨ y ∨ z ) , v = ( ~x ∨ y ∨ ~z ) ：
i. k = 2+3 = 5, 則有“出發點”集 = {sx,sy,sz,su,sv}, “目的地”集 = {tx,ty,tz,tu,tv}。
ii.對于子句u，加入中間結點x,y,z,~x,~y,~z。 對于子句v加入中間節點，~x,y,~z,x,~y,z。
iii.在子句u中，将su分别與x,y,z連起來，再連向tu。在子句v中，将sv分别與~x,y,~z連起來，再連向tv。
iv.将sx跟所有的x串連起來，再連向tx。将sx跟所有的~x串連起來，再連向tx。同理，y,z也是。
可得 NODE-DISJOINT PATH 問題如下圖:
已知3SAT問題是一個NP-完全問題，是以NODE-DISJOINT PATH 問題也是一個NP-完全問題。