4
$\begingroup$

I have a problem in understanding how to prove the following question.

Let $Q = \langle\max,f,L\rangle$ be an NPO-Problem, where $f$ only supports integers. Define $$L_Q^* =\{(x_0,1^k) : \exists x . L(x_0,x) \land f(x_0,x) \geq k\}.$$ The instance of $x_0$ is binary coded, while the numerical parameter $k$ is unary coded. Show that if $L_Q^*$ is NP-complete, then there is no FPTAS for $Q$. It can be assumed that $P \neq NP$.

Normally I have some ideas, but this time I am really stumped. My only idea was to use the fact that if $L_Q^*$ has an approximation scheme, then $f$ must run in time polynomial in $|x_0|+|x|$.

$\endgroup$
  • $\begingroup$ The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Sep 16 '17 at 7:02
4
$\begingroup$

Hint: Show that an FPTAS for $Q$ implies a polytime algorithm for $L_Q^*$. This contradicts the assumption $P \neq NP$, which is missing from your question but seems to be tacitly assumed.

$\endgroup$
1
$\begingroup$

Short on the Question: The most important step was to use that f supports only integers.

I have to say my idea was not nearly as neat as the one the author suggested. First we remind us of the concept of FPTAS for Q: $$f(x,x_0) \geq (1-\epsilon) \cdot f(x_0,x^*)$$ for some optimal solution $x^*$
Idea: If there is an FPTAS for Q, then $P = NP$ (Proof by Contradiction).

Show that: $$f(x_0,x) \geq (1-\epsilon) \cdot f(x_0,x^*) \geq k-\frac{1}{2}$$. If we solve $f(x_0,x^*)$ we get $(1-\epsilon)\cdot k$: $$f(x_0,x) \geq (1-\epsilon) \cdot k$$ We know that f will give us an integer, so we take $\epsilon = \frac{1}{2k}$.Now we can decide $L_Q^*$ in time $$poly(|x_0|,\frac{1}{\epsilon}) = poly(|x_0|,2k) = poly|(x_0,1^k)|$$. This contradicts our assumption that $P \neq NP$

$\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.