Suppose we have an NP optimization problem $A$ such that the problem of finding any valid solution, regardless of whether it is good or bad, is NP-hard (as it happens in NPO-complete problems such as Max-W-Sat, Max Ones, Max $\{0,1\}$ Integer Programming, and their corresponding Min versions). Does this imply $A$ is NPO-hard? If so: why? Can we write some general PTAS-reduction from some NPO-hard problem into $A$? If the answer is no: any known counterexample?

EDIT: Alternatively, I would appreciate to see an NP optimization problem which does not belong to Exp-APX (as long as $P\neq NP$) but is not NPO-hard.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.