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}\left(n, \triangle\right) likely to be SAT or UNSAT? By your choice of \Delta, as: \Delta \geq 5.2 = \left(\log_{\frac{7}{8}} \left(\frac{1}{2}\right)\right), then as \lim_{n\to \infty } \text{Pr}_{\phi \sim R_{3}\left(n, \Delta\right)}\left[\phi \text{SAT}\right] =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}\left(n, \Delta\right), we have \text{Pr}[\text{alg}\left(\ph\right) = \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\left(n, \frac{1}{2}\right) G \sim G\left(n, \frac{1}{2}\right) with a clique of size k planted randomly, where b \gg 2 \log n