Assuming $\mathsf{P}\ne\mathsf{NP}$, it is impossible to efficiently decide membership in an NP-complete language. I would like to assign probability to such membership, in some sense.


The following definitions use the approach to average-case complexity given in e.g. O. Goldreich "Computational Complexity" chapter 10.

Consider $(L, X_n)$ an average-case decision problem where $L$ is a language and $X_n$ is a family of random variables which can be sampled by an algorithm with polynomial running time.

Consider $A$ an algorithm computing for each input string $x$ an infinite binary fraction in $[0, 1]$ (informally regarded as a probability). We call such algorithms "estimators". $A$ is called efficient when the time of computing $k$ digits of $A(x)$ is bounded by $p(|x|, 2^k)$ with $p$ polynomial.

Define the error function to be

$$\epsilon_n(A; L):=-E_{X_n}[\chi_L(x)\ln A(x) + (1-\chi_L(x))\ln(1-A(x))]$$

where $\chi_L(x)$ is the characteristic function of $L$. It is easy to see that assuming $\mathsf{sampP}\ne\mathsf{sampNP}$, for $(L, X_n)$ which is $\mathsf{sampNP}$-complete there is a polynomial $q$ s.t.

$$\forall n \exists m > n:\epsilon_m(A; L) > \frac{1}{|q(m)|}$$

Define $A$ to be optimal for $(L, X_n)$ when it is efficient and for any efficient $B$ and polynomial $r$:

$$\forall n >> 0:\epsilon_n(A; L) - \epsilon_n(B; L) < \frac{1}{|r(n)|}$$


Assuming $\mathsf{sampP}\ne\mathsf{sampNP}$ (and other conjectures if necessary), does $A$ exist which is optimal for an $\mathsf{sampNP}$-complete problem?



Let's call a Karp-reduction $f$ of $(L, X_n)$ to $(M, Y_n)$ semi-invertible when there exists $g: \lbrace 0, 1 \rbrace^* \rightarrow \lbrace 0, 1 \rbrace^* \cup \lbrace \bot \rbrace$ computable in polynomial time s.t.

$$\forall x: g(f(x))=x$$

$$\forall y: g(y) \ne \bot \rightarrow f(g(y))=y$$

Given $A$ optimal for $(M, Y_n)$ and $f$ a semi-invertible reduction of $(L, X_n)$ to $(M, Y_n)$, $A \circ f$ is optimal for $(L, X_n)$. In particular, if $(M, Y_n)$ is $\mathsf{sampNP}$-complete s.t. the reductions can be chosen semi-invertible (such $(M, Y_n)$ exists since examining the construction of a complete problem in Ben-David et al we see the reductions are semi-invertible), we get optimal algorithms for all problems in $\mathsf{sampNP}$. In particular, $A$ yields an average-case polynomial time solution for any problem formulated as a problem in $\mathsf{sampNP}$ which is "secretly" in $\mathsf{sampP}$. This is similar to the properties of Levin search, but Levin search only solves instances with a positive answer.


Consider $A$, $B$ estimators for $(L, X_n)$. Define the "metric"

$$\delta_n(A, B; L) := E_{X_n}[\chi_L |\ln{A} - \ln{B}| + (1-\chi_L) |\ln{(1-A)} - \ln{(1-B)}|]$$

If $\delta_n(A, B; L)$ vanishes for large $n$ with superpolynomial speed, then $\epsilon_n(A; L) - \epsilon_n(B; L)$ also vanished for large $n$ with superpolynomial speed.

Suppose $A$ and $B$ are both optimal. Then it can be seen that $\delta_n(A, B; L)$ vanishes for large $n$ with superpolynomial speed (via considering $\frac{A+B}{2}$ and using the convexity of the logarithm). So optimal estimators are unique up to "small" deviations.

  • 1
    $\begingroup$ Computation $\mapsto$ Computational $\;$ ? $\;\;\;\;$ $\endgroup$ – user6973 Jun 6 '14 at 19:42
  • 1
    $\begingroup$ How is it "easy to see that"? $\:$ I only see how to show "for infinitely many $n$", $\hspace{1.37 in}$ rather than "for sufficiently large $n$". $\;\;\;\;$ $\endgroup$ – user6973 Jun 6 '14 at 19:47
  • $\begingroup$ @RickyDemer: You're absolutely right, the claim as it stands is false e.g. you can take a complete language which contains strings of only even length. Thx! $\endgroup$ – Squark Jun 15 '14 at 18:50

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.