Return to Question

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

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

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

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 $LQ^*$ is NP-complete, then there is no FPTAS for $Q$.

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

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

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