# k-satisfiability problem (k-SAT problem)

Last edited: 2023-11-11

# 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.

SAT problem
- The more general form of this problem

# Theory