1
$\begingroup$

Given an optimization problem $X$, it is easy to construct a decision problem $Y$, such that there is a two-directional polynomial-time reduction between $X$ and $Y$. Therefore, we can define a class of optimization problems "$P^O$", which is the class of all optimization problems whose corresponding decision problem is in $P$; and "$NPH^O$", which is the class of all optimization problems whose corresponding decision problem is NP-hard.

But, problems in $NPH^O$ are not equal in terms of approximation. To be concrete, assuming $P\neq NP$, we can partition $NPH^O$ into two non-empty subsets: the problems that have an FPTAS, and the problems that do not.

My question is: is there any parallel partition of the class of NP-hard decision problems? For example, assuming $P\neq NP$, is there a natural class $C$ of decision problems, such that $C^O$ is exactly the class of optimization problems that have an FPTAS?

(by "natural" I mean that $C$ can be defined as a class of decision problems, without referring to optimization problems).

$\endgroup$
1

1 Answer 1

0
$\begingroup$

I did not find a class of decision problems that is equivalent to FPTAS, but I think FPTAS can be used to answer the following partial decision problem:

Given a number $r$ and an approximation-accuracy $\epsilon>0$:

  • If $OPT \leq r$, return "yes";
  • If $OPT > r\cdot(1+\epsilon)$, return "no";
  • Otherwise, return either "yes" or "no".

Given an FPTAS, we can solve the decision problem as follows:

  • If the value of the solution returned by the FPTAS is at most $r(1+\epsilon)$, return "yes";
  • Otherwise, return "no".

I do not know if, given a solution to the decision problem, we can construct an FPTAS.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.