# NP

## 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

## Discrete Logarithm Problem ★★★

Author(s):

If is prime and , we write if satisfies . The problem of finding such an integer for a given (with ) is the *Discrete Log Problem*.

**Conjecture**There does not exist a polynomial time algorithm to solve the Discrete Log Problem.

Keywords: discrete log; NP

## P vs. NP ★★★★

**Problem**Is P = NP?

Keywords: Complexity Class; Computational Complexity; Millenium Problems; NP; P; polynomial algorithm