# Max-Satisfiability Problem
Last edited: 2023-11-13
# Statement
Max-Satisfiability Problem (Max-SAT problem)
Provided with a boolean function $f$ in CNF with $n$ variables and $m$ clauses, where each variable only appears in a single literal in each clause. What is an assignment maximising the number of satisfied clauses?
# Solutions
- Max-SAT random approximation algorithm
- Runs in $O(nm)$ and achieves a $1/2$-approximation.