We are going to assume the following.

Statement

k-SAT

We are going to show that the k-SAT problem is NP-Complete for $k \geq 3$.

k-SAT

To do this we will show 3-SAT is NP-complete which as 3-SAT is a subproblem to k-SAT for $k \geq 3$ this will prove all we need to.

We need to do the following to show this:

• Show that 3-SAT is NP
• Show there is a reduction from the SAT problem to 3-SAT.

k-SAT is in NP

k-SAT is in NP

3-SAT is NP-Complete

3-SAT is NP-complete

Though this has shown us even more than just 3-SAT.

k-SAT is NP-complete for k greater than or equal to 3

Practice problems

From Algorithms by S. Dasgupta, C. Papadimitriou, and U. Vazirani.