NP

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

Theoretical Comp. Sci. » Complexity

Discrete Logarithm Problem ★★★

Author(s):

If $p$ is prime and $g,h \in {\mathbb Z}_p^*$ , we write $\log_g(h) = n$ if $n \in {\mathbb Z}$ satisfies $g^n = h$ . The problem of finding such an integer $n$ for a given $g,h \in {\mathbb Z}^*_p$ (with $g \neq 1$ ) is the Discrete Log Problem.