Hardness of Approximation
Refuting random 3SAT-instances on $O(n)$ clauses (weak form) ★★★
Author(s): Feige
Conjecture For every rational and every rational , there is no polynomial-time algorithm for the following problem.
Given is a 3SAT (3CNF) formula on variables, for some , and clauses drawn uniformly at random from the set of formulas on variables. Return with probability at least 0.5 (over the instances) that is typical without returning typical for any instance with at least simultaneously satisfiable clauses.
Keywords: NP; randomness in TCS; satisfiability