# A complexity class between P and FPTAS

The question is about approximation algorithms to NP-hard optimization problems. For concreteness, let $$M$$ be a minimization problem with $$n$$ inputs, where all inputs and outputs are integers in the range $$1,\ldots,V$$, and $$\log V$$ is polynomial in $$n$$, so that the problem size is polynomial in $$n$$.

A FPTAS (Fully Polynomial Time Approximation Scheme) for $$M$$ as an algorithm that, for every $$\epsilon>0$$, returns a solution with value at most $$(1+\epsilon)$$ of the optimal solution, in time $$\text{poly}(n,1/\epsilon)$$.

Define a RPTAS (Range-based Polynomial Time Approximation Scheme) as an algorithm that, for every $$\epsilon>0$$ and $$v\in\{1,\ldots,V\}$$, returns a solution in the range $$[v,\ldots,(1+\epsilon)v]$$, if and only if the optimal solution is in that range, and runs in time $$\text{poly}(n,1/\epsilon)$$.

If there exists an RPTAS, then there exists an FPTAS: partition the range $$1,\ldots,V$$ into intervals $$[(1+\epsilon)^i,(1+\epsilon)^{i+1}]$$ for $$i\geq 0$$, and run the RPTAS on each range. Note that the number of ranges is $$\log_{1+\epsilon}V = \log V / \log {(1+\epsilon)}\approx \log{V}/\epsilon$$, so the total run-time is polynomial in $$n$$ and $$1/\epsilon$$.

My question is if the opposite is also true: given an FPTAS, can it somehow be adapted to an RPTAS? Stated differently: denote by FPTAS / RPTAS the class of optimization problems that have an FPTAS / RPTAS respectively. Obviously, P is a subset of RPTAS, and I showed above that RPTAS is a subset of FPTAS. Is it a strict subset (assuming P$$\neq$$NP)?

More generally: was this notion of RPTAS studied before? I checked the complexity zoo and they do not mention subsets of FPTAS, but maybe it was studied under a different name?

Suppose that you have an RPTAS. For each $$v$$, you can determine in polynomial time whether the optimal solution is at least $$v$$ by running your RPTAS on $$[2^iv,2^{i+1}v]$$ for $$0 \leq i \leq \log_2 V$$. Now you can use binary search to find the optimal value in polynomial time.
• Thanks! So my definition of RPTAS was equivalent to P. What if we change the definition as follows: an RPTAS does not work for arbitrary ranges $[v,(1+\epsilon)v]$, but only for ranges $[(1+\epsilon)^i,(1+\epsilon)^{i+1}]$ for $i\geq 0$. Then RPTAS is still contained in FPTAS. Is it now equivalent to P? Dec 16 '21 at 13:24
• My guess is that by playing with $\epsilon$, you will be able to mimic the argument. Dec 16 '21 at 13:28
• Indeed: assuming $v\geq 2$, we can take $\epsilon=v-1$. Then the RPTAS can check all the ranges $[v^i,v^{i+1}]$ for $0\leq i\leq \log_v V$. Dec 16 '21 at 13:49