---
title: "SU-CS254B MAY192025"
source: https://www.jemoka.com/posts/kbhsu_cs254b_may192025/
date: 2025-05-19
---

Partial SAT Algorithms run very fast always give the right answer may time out (i.e., will give up on certain instances) &ldquo;Key question: can you make my algorithm fail?&rdquo;
our answer&hellip; uniform random 3cnf instances n: number of variables \(\triangle\), &ldquo;clause density&rdquo;: 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&rsquo;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}] &gt; 99.0\%\) Feige&rsquo;s Hypothesis &ldquo;for all constant \(\triangle\), a \(\triangle\) 3 sat refuters do not exist&rdquo;
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\)
