# Decision version of optimization problems with polynomial-time approximation algorithms

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

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.