<h2>Motivation</h2>

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

<h2>Definitions</h2>

<p>The following definitions use the approach to average-case complexity given in e.g. O. Goldreich "<a href="http://books.google.co.il/books/about/Computational_Complexity.html?id=EuguvA-w5OEC&amp;redir_esc=y" rel="nofollow">Computational Complexity</a>" chapter 10.</p>

<p>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.</p>

<p>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 <em>efficient</em> when the time of computing $k$ digits of $A(x)$ is bounded by $p(|x|, 2^k)$ with $p$ polynomial.</p>

<p>Define the <em>error function</em> to be</p>

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

<p>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.</p>

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

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

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

<h2>Question</h2>

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

<h2>Observations</h2>

<h3>Reductions</h3>

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

<p>$$\forall x: g(f(x))=x$$</p>

<p>$$\forall y: g(y) \ne \bot \rightarrow f(g(y))=y$$</p>

<p>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 <a href="http://www.wisdom.weizmann.ac.il/~oded/PS/aver.ps" rel="nofollow">Ben-David et al</a> 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.</p>

<h3>Uniqueness</h3>

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

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

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2014-06-15T18:50:57.733Z
@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!
Vanessa
CC BY-SA 4.0
2021-04-22T15:43:55.613Z
Very interesting Q! Possibly related to resource-bounded martingales and resource-bounded measure, e.g. https://doi.org/10.1137/0219076 and https://www.cs.uwyo.edu/~jhitchco/bib/rbm.shtml. Point being that if you can assign a *good enough* probability of each $x$ be in a language, then that language is not p-random. So if you *cannot* assign a good enough probability to each x for an NP-complete language, it would separate P from NP (amongst other consequences). But $\mu_p(NP) \neq 0$ is not known to follow from $P \neq NP$ alone. Would be interesting if it were directly related to $sampNP$!
Joshua Grochow
<cc.complexity-theory><p-vs-np><average-case-complexity>
Assigning probability to membership in an NP-complete language
Vanessa
# Assigning probability to membership in an NP-complete language

(Asked by: username_0 on 2014-06-06)

## Motivation

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.

## Definitions

The following definitions use the approach to average-case complexity given in e.g. O. Goldreich "[Computational Complexity](http://books.google.co.il/books/about/Computational_Complexity.html?id=EuguvA-w5OEC&redir_esc=y)" 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)|}$$

## Question

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

## Observations

### Reductions

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](http://www.wisdom.weizmann.ac.il/~oded/PS/aver.ps) 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.

### Uniqueness

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.

**Tags:** cc.complexity-theory, p-vs-np, average-case-complexity

> **Comments:**
> **username_0**: @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!  
> **username_1**: Very interesting Q! Possibly related to resource-bounded martingales and resource-bounded measure, e.g. https://doi.org/10.1137/0219076 and https://www.cs.uwyo.edu/~jhitchco/bib/rbm.shtml. Point being that if you can assign a *good enough* probability of each $x$ be in a language, then that language is not p-random. So if you *cannot* assign a good enough probability to each x for an NP-complete language, it would separate P from NP (amongst other consequences). But $\mu_p(NP) \neq 0$ is not known to follow from $P \neq NP$ alone. Would be interesting if it were directly related to $sampNP$!  

---

## 0 answers

