# How does NP-completess of decision problems relate to NP-completeness of search problems?

## 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

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.

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