CODEWITHSUNDEEP
npnp-completesat
old man
old man

Reputation: 151

SAT is NP complete, so why don't we have k-SAT is NP complete for arbitrary value of k

k-SAT is a special case of SAT. Since SAT is NP-complete, I don't understand why we don't have k-SAT is NP-complete for whatever values of k. In the class, my professor used polynomial reduction from SAT to prove that 3-SAT is NP-complete. I don't understand why we need to prove for that, shouldn't a special case must follow the rule for general case?

Upvotes: 3

Views: 2401

Answers (1)

alias
alias

Reputation: 30525

Well, your claim is clearly not true for 1- or 2-SAT.

1-SAT problem (i.e., where you have at most one literal!) is obviously linear in the number of clauses and variables, as the polarity in each clause would tell you how to pick the variables.

2-SAT is trickier, but you can solve it in polynomial time: https://www.geeksforgeeks.org/2-satisfiability-2-sat-problem/

For any k > 3, k-SAT is obviously NP-complete; as any algorithm for those can be used to solve 3-SAT, as your professor seems to have discussed.

So, the fundamental confusion here is that while k-SAT is an instance of the general SAT problem, it does not mean all k-SAT problems are equally difficult. In a sense, 3-SAT is the "simplest" instance of SAT that is NP-complete, and thus forms a good basis to reduce other problems to. Hope that helps!

Upvotes: 4

Related Questions