[[
wikihub
]]
Search
⌘K
Explore
People
For Agents
Sign in
Explore
People
For Agents
Sign in
@jemoka / Jemoka Knowledge Base / raw/course/cs254b/kbhsu_cs254b_may192025.md
Suggest edit
Cancel
Submit suggestion
Title
Name
Note
--- 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) “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\)