# FPTAS definition

I read that a fully polynomial time approximation scheme (FPTAS) has time complexity polynomial in the input size and also polynomial in $1/\epsilon$. However, this leaves some ambiguity.

For example, $T(n,1/\epsilon)=\min(n^{1/\epsilon},(1/\epsilon)^n)$ is both polynomial in $n$ (when holding $1/\epsilon$ constant) and polynomial in $1/\epsilon$ (when holding $n$ constant). But $T$ is not polynomial in $n/\epsilon$ or $(n+1/\epsilon)$ because $\sqrt x^\sqrt x$ and $(x/2)^{x/2}$ aren't bounded by polynomials.

Does this mean an algorithm with running time $T$ isn't an FTPAS, and perhaps a better definition would be that it has to be polynomial in $n+1/\epsilon$?

The standard definition is incredibly ambiguous, since it is not clear what "polynomial in $n$ and in $1/\epsilon$" means. Judging from examples, it means $O(n^C(1/\epsilon)^D)$ for some constants $C,D$. Without loss of generality, $C=D$, and then we get the simpler definition $O((n/\epsilon)^C)$.

• Thanks for clarifying. Although might $O((n+1/\epsilon)^C)$ be more precise because when $\epsilon=n$ is very large, $n/\epsilon=1$ but it should still take at least $O(n)$ to find a feasible solution? – Akababa Aug 5 '18 at 23:22
• The big O holds in the limit $n\to\infty$ and $\epsilon\to0$. We can assume that $\epsilon < 1 < n$, say. – Yuval Filmus Aug 5 '18 at 23:28