Background
Oded Goldreich differentiates in his textbook (Computational Complexity: A Conceptual Perspective) between the "decision" variant of NP problems and "search" variant of NP problems, denoted using binary relations between "instance" and "solution":
Call a binary relation $R$ an NP relation if
- $(x,y)\in R \implies |y|\leq q(|x|)$ for some polynomial $q$, i.e., solutions are only polynomially longer, and
- $R\in \mathrm{P}$, i.e, it can be efficiently checked if $y$ is a solution to $x$.
[Goldreich denotes the class of all NP relations as $\mathcal{PC}$, p. 49, Def. 2.3]
Similar to many-one-reductions between sets, Goldreich defines a Levin-reduction between NP relations:
$R$ Levin-reduces to $R'$ when there are two p-computable functions $f,g$ such that
- $f$ many-one-reduces from $S_R = \{ x\mid \exists y. (x,y)\in R\}$ to $S_{R'}=\{x'\mid \exists y'.(x',y')\in R'\}$, and
- $g$ translates solutions for $f(x)$ back into solutions for $x$, i.e., $(f(x), y')\in R' \implies (x, g(x, y'))\in R$.
As usual, we can now define NP-complete sets with respect to many-one-reductions, and NP-complete relations with respect to Levin-reductions (that is a NP relation $R$ such that every NP relation $Q$ can be Levin-reduced to $R$).
It is immediately clear that Levin-completeness is stronger than many-one-completeness: given a Levin-complete relation $R$, the corresponding decision variant $S_R = \{ x\mid \exists y. (x,y)\in R\}$ is many-one-complete. Also, there exist problems that are both Levin-complete and many-one-complete, e.g. SAT and the natural search variant $\mathit{SATR}=\{(\varphi, w) \mid w$ satisfies formula $\varphi\}$.
However, I am unsure if Levin-completeness and many-one-completeness are equally strong, in particular if many-one-completeness (of a relation's decision variant) implies Levin-completness.
Question
Does the following statement hold for all NP relations $R$?
the set $S_R=\{x\mid \exists y. (x,y)\in R\}$ is many-one-complete $\Rightarrow$ the relation $R$ is Levin-complete. (*)
I am tending towards a negative answer, and presume that under certain (cryptographic hardness) assumptions the statement (*) should fail to hold. However, I was unable to construct appropriate counterexamples when, e.g., assuming that one-way functions exist. Under which assumptions does the statement (*) hold/fail to hold?
Note that it can be showed that the statement (*) holds when asuming the hypothesis Q by Fenner et al. (2003). Conversely, when assuming $\neg$Q, one can show the weaker statement that there exists an NP relation $R$ (with $S_R=$SAT) such that the standard relation for SAT $\mathrm{SATR}$ does not Levin-reduce to $R$ if we insist that the reduction function $f$ (in 1.) is the identity function.
