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

Improve this question
$\endgroup$
1
  • $\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$ Commented Sep 16, 2017 at 7:02

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
0
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$

Improve this answer
$\endgroup$
0

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.