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

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

CC BY-SA 4.0
2020-01-20T01:49:16.417Z
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
CC BY-SA 4.0
2020-01-20T02:07:54.627Z
For particular complexity classes (related to hardness of approximation), various [approximation-preserving reductions](https://en.wikipedia.org/wiki/Approximation-preserving_reduction) 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
CC BY-SA 4.0
2020-01-20T03:43:17.150Z
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
CC BY-SA 4.0
2020-01-20T19:21:17.310Z
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
<cc.complexity-theory><complexity-classes><randomness>
Randomized Reduction for Maximization Problem
tc1729
# Randomized Reduction for Maximization Problem

(Asked by: username_0 on 2020-01-19)

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.

**Tags:** cc.complexity-theory, complexity-classes, randomness
> **Comments:**
> **username_1**: 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.  
> **username_1**: For particular complexity classes (related to hardness of approximation), various [approximation-preserving reductions](https://en.wikipedia.org/wiki/Approximation-preserving_reduction) have been defined that may capture what you have in mind, although they generally concern deterministic algorithms.  Perhaps randomization is a red herring here?  
> **username_2**: 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.  
> **username_1**: 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.  

---

## 0 answers

