[Solved]: NP-hardness and FPTAS

Problem Detail: 

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

Asked By : heliodromus

Answered By : Yuval Filmus

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/16373

3.2K people like this

 Download Related Notes/Documents