There is no polynomial time algorithm \(A\) such that for all 3CNF \(\varphi\), \(A\qty(\varphi)\) accepts if and only if \(\varphi\) is satisfiable.
How do we relax this?
- we can say “for most” 3CNF formulas, which means that we have to name a distribution
- we can say to satisfy “most” \(\varphi\), meaning we can satisfy most clauses of \(\varphi\)
- allow more than poly-time (SoTA is at \(1.34\dots^{n}\)).
PCP Theorem
\(P \neq NP\) implies no polynomial time algorithm that finds \(x\) that satisfies \(99.9\%\) of clauses. In particular, no polytime algorithm that finds \(x\) that satisfies \(\geq \frac{7}{8} + \varepsilon\) fraction of the clauses.
Min-Bisection
Given a graph \(G\), split the vertices into two such that, with \(S \subseteq V\), \(| S | = \frac{n}{2}\), such that the number of edges \(s \leftrightarrow \bar{s}\) is minimized.