Partial SAT Algorithms
- run very fast
- always give the right answer
- may time out (i.e., will give up on certain instances)
“Key question: can you make my algorithm fail?”
our answer…
- uniform random 3cnf instances
- n: number of variables
- \(\triangle\), “clause density”: the number of clauses; where \(\Delta = \frac{n}{m}\).
- output \(\phi\), \(\Delta\) n random clauses, independently chosen
SAT or UNSAT
Sampling \(\phi \sim R_{3}\qty(n, \triangle)\) likely to be SAT or UNSAT? By your choice of \(\Delta\), as: \(\Delta \geq 5.2 = \qty(\log_{\frac{7}{8}} \qty(\frac{1}{2}))\), then as \(\lim_{n\to \infty } \text{Pr}_{\phi \sim R_{3}\qty(n, \Delta)}\qty [\phi \text{SAT}] =0\).
3-SAT Refuter
A 3-SAT refuter is a polynomial time algorithm where:
- given any 3CNF instance, it outputs SAT, UNSAT, or no-comment
- never wrong: it won’t say unsat for SAT, and converse
- given random \(\phi \sim R_{3}\qty(n, \Delta)\), we have \(\text{Pr}[\text{alg}\qty(\ph) = \text{unset}] > 99.0\%\)
Feige’s Hypothesis
“for all constant \(\triangle\), a \(\triangle\) 3 sat refuters do not exist”
This implies P != NP
Planted Clique Problem
In polytime, distinguish between:
- \(G \sim G\qty(n, \frac{1}{2})\)
- \(G \sim G\qty(n, \frac{1}{2})\) with a clique of size \(k\) planted randomly, where \(b \gg 2 \log n\)