k-satisfiability problem (k-SAT problem)

Statement

k-SAT Problem

Given a boolean function in CNF with variables and clauses of size at most . Is there a true/false assignment to the variables that satisfies . If yes then output it, otherwise say no.

Solutions

• 2-SAT algorithm using SCC
  • This runs in .
  • Only solves problems with clauses of size at most 2.

Related

• SAT problem
  • The more general form of this problem

Theory

• 2-SAT runs in polynomial time.
• k-SAT is in NP
• 3-SAT is NP-complete
• k-SAT is NP-complete for k greater than or equal to 3