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.

  • $\begingroup$ 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. $\endgroup$ – Neal Young Jan 20 at 1:49
  • $\begingroup$ 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? $\endgroup$ – Neal Young Jan 20 at 2:07
  • $\begingroup$ 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. $\endgroup$ – Chandra Chekuri Jan 20 at 3:43
  • $\begingroup$ 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. $\endgroup$ – Neal Young Jan 20 at 19:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.