# Randomized Reduction for Maximization Problem

I have two maximization problems $$P_1$$ and $$P_2$$ where the decision version $$L_1 = \{(x, t) : \operatorname{Val}_1(x)\ge t\}$$ of $$P_1$$ is $$\mathsf{NP}$$-complete. Let $$f:P_1\to P_2$$ be a randomized reduction such that it holds with high probability that $$|\operatorname{OPT}_1(x) - \operatorname{OPT}_2(f(x))|\le\varepsilon.$$ I would like to show that $$L_2$$ is also hard under some complexity theoretic assumption like $$\mathsf{NP}\neq\mathsf{BPP}$$.

The issue I am running into is that simply knowing $$t^*:=\operatorname{OPT}_1(x)$$ and $$\hat{t}:=\operatorname{OPT}_2(f(x))$$ are close does not seem to imply the usual requirements of a randomized reduction (though this closeness seems to me that "morally" $$P_2$$ should also be hard if $$P_1$$ is, since if we could solve the optimization problem for $$P_2$$, we pretty much are able to solve it for $$P_1$$ up to some small error). Is there a version of reduction that formalizes what I think to be morally true? Any help is appreciated.

• I think you'd need to know more about the specific problems to get anywhere. I'm sure there are NP-hard problems such that, in poly time, one can compute an answer that approximates the optimum up to an additive $\epsilon$. So the condition you give isn't enough to ensure that $P_2$ is not in poly time. – Neal Young Jan 20 at 1:49
• For particular complexity classes (related to hardness of approximation), various approximation-preserving reductions have been defined that may capture what you have in mind, although they generally concern deterministic algorithms. Perhaps randomization is a red herring here? – Neal Young Jan 20 at 2:07
• As Neal said there are several NP-Hard problems for which an additive approximation can be obtained. Here is an example. Given a graph find a spanning tree with minimum maximum degree. This is NP-Hard but one can find a spanning tree with max degree OPT + 1. Same with edge coloring. Vizing's theorem says that every simple graph with max degree \Delta can be edge-colored with at most \Delta + 1 colors (\Delta is needed clearly) while determining whether a given graph requires \Delta or \Delta+1 is NP-Complete. So without knowing \epsilon etc your question is not clear. – Chandra Chekuri Jan 20 at 3:43
• And I'm sure there are NP-hard problems where OPT is in a bounded range (e.g. [0,1]) and a PTAS exists, so even if you say "for arbitrarily small epsilon", that's not enough. – Neal Young Jan 20 at 19:21