Hey fellas,
I have a Problem in understanding on how to proof the following:
Let Q = {max,f,L} be a NPO-Problem, where f only supports integers.
LQ* ={(x0,1k)|there exists x such that L(x0,x) and f(x0,x) >=k}
The instance of x0 is binary coded while the numerical parameter k is unary coded.
Show that if LQ* is NP-Complete, then there is no full polynomial approximation scheme for Q.
Normally I have so sort of idea, but this time I am really stumped
I would be grateful if you could show me on how to solve such issues.
Sincerely yours
heliodromus