Max-k-exact-satisfiability problem

programming

Statement

Max-$k$-exact-satisfiability 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 and each clause has exactly $k$ litterals. What is an assignment maximising the number of satisfied clauses?

Solutions

Theory

Related problems