3 problems

Let $F(n,cn)$ be a random 3-CNF formula with $n$ variables and clause-to-variable density $c$, and let $c_3$ denote the threshold constant from the Satisfiability Threshold Conject…

Let $F(n,cn)$ be a random $k$-CNF formula with $n$ variables and clause-to-variable density $c$, formed from $m=cn$ independently and uniformly selected proper clauses of length…

Let Feige's Hypothesis be the assertion that no efficient algorithm can prove the unsatisfiability of a random $3$-SAT formula with high probability, even when the formula has a sm…