Let $R_1, R_2 \subseteq \{0,1\}^* \times \{0,1\}^*$ be search problems. We say that there is a Levin reduction $R_1 \to R_2$ iff there exists polynomial-time computable and polynomial upper-bounded functions $f, g, h$ such that:
- $R_1(x_1, y_1) \implies R_2(f(x_1), g(x_1,y_1))$
- $R_1(x_1, h(f(x_1), y_2)) \impliedby R_2(f(x_1), y_2)$
Prove that the class $\widetilde{NP} = \{R \subseteq \{0, 1\}^*\times \{0,1\}^* \mid R\text{ is polynomial verifiable}\}$ is closed under Levin reductions, namely if $R_2 \in \widetilde{NP}$ and there is a Levin reduction $R_1 \to R_2$, then $R_1 \in \widetilde{NP}$.
The case of Karp reductions instead of Levin was straightforward to me, but I don't know where to start with this exercise.