Decision version of optimization problems with polynomial-time approximation algorithms

Question

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

• Samuel Bismuth: The Wikipedia page is related to your question: en.wikipedia.org/w/…

Answer 1

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.