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" 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 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.
