Da 3-SAT ein Spezialfall von SAT ist, ist 3-SAT natürlich in NP. Es muss also nur noch gezeigt werden, dass SAT in polinomialer Zeit auf 3-SAT transformiert werden kann. Es sei eine Instanz von SAT gegeben. Da wir in 3-SAT nur Alternativen mit höchsten drei Literalen benutzen dürfen, können wir die in der Instanz von SAT gegebenen Alternativen mit höchstens drei Literalen so übernehmen, wie sie gegeben sind. Sei nun

´A = x_(i_1)^(sigma_(i_1)) vv x_(i_2)^(sigma_(i_2)) vv cdots vv x_(i_(n))^(sigma_(i_(n)))´

eine Alternative mit mindestens vier Literalen, d. h. ´n >= 4´. Wir zeigen, wie die Anzahl der Literale gesenkt werden kann. Dazu betrachten wir die Alternativen

´A' = x_(i_1)^(sigma_(i_1)) vv x_(i_2)^(sigma_(i_2)) vv y´

und

´A'' = x_(i_3)^(sigma_(i_3)) vv x_(i_4)^(sigma_(i_4)) vv cdots vv x_(i_(n))^(sigma_(i_(n))) vv y_0´

wobei y eine neue Variable ist. Diese Alternativen haben nur ´3´ bzw. ´n − 1´ Literale. Es sei ´alpha´ eine Belegung, für die ´A´ erfüllt ist.

Fall 1: Es sei ´w_alpha(x_(i_1)^(sigma_(i_1)) vv x_(i_2)^(sigma_(i_2))) = 1´. Dann gilt auch ´w_alpha(A') = 1´. Setzt man nun noch ´alpha(y) = 0´, so wird ´w_alpha(y^0) = 1´ und folglich ist auch ´A''´ erfüllt.

Fall 2: Es sei ´w_alpha(x_(i_1)^(sigma_(i_1)) vv x_(i_2)^(sigma_(i_2))) = 0´. Da ´A´ erfüllt wird, gilt ´w_alpha(x_(i_3)^(sigma_(i_3)) vv x_(i_4)^(sigma_(i_4)) vv cdots vv x_(i_(n))^(sigma_(i_(n)))) = 1´. Damit ist auch ´A''´ erfüllt. Setzen wir nun ´alpha(y) = 1´, so ist auch ´A'´ erfüllt. Damit folgt aus der Erfüllbarkeit von ´A´ die gleichzeitige Erfüllbarkeit von ´A'´ und ´A''´. Es sei nun ´beta´ eine Belegung, die ´A'´ und ´A''´ erfüllt.

Fall 1: ´beta(y) = 0´ Dann liefert die Erfüllbarkeit von ´A'´, dass ´w_alpha(x_(i_1)^(sigma_(i_1)) vv x_(i_2)^(sigma_(i_2))) = 1´ gilt. Somit ist A auch erfüllt.

Fall 2: ´beta(y) = 1´ Dann liefert die Erfüllbarkeit von ´A''´ unter Berücksichtigung von ´w_beta(y^0) = 0´, dass ´w_alpha(x_(i_3)^(sigma_(i_3)) vv x_(i_4)^(sigma_(i_4)) vv cdots vv x_(i_(n))^(sigma_(i_(n)))) = 1´ gilt. Damit ist erneut ´A´ auch erfüllt. Die Erfüllbarkeit von ´A'´ und ´A''´ liefert also auch die Erfüllbarkeit von ´A´.

Nach diesem Verfahren reduzieren wir die Anzahl der Literale in den Alternativen, bis nur noch solche mit höchstens drei Literalen vorkommen. Nach Obigem ist die neue Menge der Alternativen genau dann erfüllbar, wenn die ursprünglich gegebene Menge von Alternativen erfüllbar ist. Ausgehend von einer Alternativen mit ´n >= 4´ Literalen, konstruieren wir ´n − 2´ Alternativen mit jeweils 3 Literalen. Somit ist die Konstruktion polynomial. Es gibt also eine polynomiale Transformation von SAT auf 3-SAT.