Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

It is conjectured that NP-complete problems are hard not only in the worst case but also in the typical case. Formally, given a language $S \in \lbrace 0,1 \rbrace^*$ and for each $n$ a probability distribution $X_n$ on $\lbrace 0,1 \rbrace^n$, $(S, X)$ is called "hard in the typical case" when for any algorithm $A$ and polynomial $q(n)$, the probability $P_n$ that $A$ decides membership in $S$ correctly in time at most $q(n)$ for an $X_n$-random element of $\lbrace 0,1 \rbrace^n$ is s.t. $1-P_n$ decreases with $n$ slower than some polynomial. We henceforth restrict attention to $X_n$ that are polynomial-time-sampleable, that is, $X_n$ can be sampled by a random algorithm with time complexity polynomial in $n$. It can be show than there are problems $(S, X)$ such that

(i) $S \in NP$

(ii) For any $(T, Y)$ with $T \in NP$, $(T, Y)$ can be reduced to $(S, X)$ in an appropriate sense, in particular if $(S, X)$ is feasible (polynomial) in the typical case then $(T, Y)$ is feasible in the typical case

O. Goldreich calls such problems sampNP-complete. For most (all?) natural NP-complete problems $S$, we can find $X$ s.t. $(S, X)$ is sampNP-complete. It is conjectured that such problems are hard in the typical case. In particular, it is a necessary condition for existence of one-way functions

The question is how this theory is affected by introducing non-uniformity. For worst-case complexity, it is known that $NP \subset P/poly$ implies $PH=\Sigma_2$ which is considered unlikely. What about average-case complexity? That is, what evidence can be brought for/against the following statement:

Given $(S, X)$ sampNP-complete, there exists a polynomial-size family of Boolean circuits $C_n$ s.t. $C_n$ decides membership in $S$ correctly except for a fraction of the inputs which diminishes faster than polynomially w.r.t. $X$

EDIT: After posting this question I noticed it is more or less the same as that question. However the answer accepted there seems to me somewhat unsatisfactory. That answer says that the non-degeneracy of the polynomial hierarchy is not known to imply typical-case hardness of $NP$. However it might be that we can get a stronger conclusion by making a stronger assumption e.g. something about the average-case complexity of problems on different levels of the polynomial hierarchy

share|cite|improve this question

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.