k-satisfiability problem (k-SAT problem)
programming
Statement
k-SAT Problem
Given a boolean function $f$ in CNF with $n$ variables and $m$ clauses of size at most $k$. Is there a true/false assignment to the $n$ variables that satisfies $f$. If yes then output it, otherwise say no.
Solutions
- 2-SAT algorithm using SCC
- This runs in $O(n + m)$.
- Only solves problems with clauses of size at most 2.
Related
- SAT problem
- The more general form of this problem