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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.