Home » Subject » Theoretical Comp. Sci. » Complexity

Hardness of Approximation


Theoretical Comp. Sci. » Complexity » Hardness of Approximation

Refuting random 3SAT-instances on $O(n)$ clauses (weak form) ★★★

Author(s): Feige

Conjecture   For every rational $ \epsilon > 0 $ and every rational $ \Delta $, there is no polynomial-time algorithm for the following problem.

Given is a 3SAT (3CNF) formula $ I $ on $ n $ variables, for some $ n $, and $ m = \floor{\Delta n} $ clauses drawn uniformly at random from the set of formulas on $ n $ variables. Return with probability at least 0.5 (over the instances) that $ I $ is typical without returning typical for any instance with at least $ (1 - \epsilon)m $ simultaneously satisfiable clauses.

Keywords: NP; randomness in TCS; satisfiability

Posted by cwenner
updated February 27th, 2009
add new comment

Note: Resolved problems from this section may be found in Solved problems.


Syndicate content