0
$\begingroup$

We have two $NP$ complete problems $\Pi_1$ and $\Pi_2$. Suppose $\Pi_1\rightarrow\Pi_2$ be a many one parsimonious reduction.

  1. If $\Pi_1$ has an FPTAS then does $\Pi_2$ also have?

  2. If $\Pi_2$ has an FPTAS then does $\Pi_1$ also have?

$\endgroup$
0
$\begingroup$

Regarding number 1: The reduction to 3-SAT in the Cook-Levin theorem is many-one and parsimonious. There's no FPTAS for 3-SAT unless $\mathcal{P=NP}$, yet any problem in $\mathcal{NP}$, including those with a FPTAS, reduce to it in the fashion you describe.
With respect to number 2: I don't know many problems with FPTAS's but I strongly suspect that, if you look through a few and the reductions that prove them to be $\mathcal{NP}$-complete, you'll quickly find a counterexample. That's because I don't see any connection between being able to count solutions and being able to approximate them.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.