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

  1. $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
  2. $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.


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.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.