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
  • $\begingroup$ The Wikipedia page is related to your question: en.wikipedia.org/w/… $\endgroup$ Commented May 5, 2023 at 7:43

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$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.