Por ejemplo, para el problema de viajante Euclidiano, un PTAS produciría una visita con longitud máximo (1 + ε)L, siendo L la longitud de la visita más corta.
[1] El tiempo que toma en correr un PTAS es requerido ser polinomial en la longitud del problema para cada ε fijo, pero puede ser diferente para distintos valores de ε.
Un problema práctico con los algoritmos PTAS es que el exponente del polinomio podría aumentar drásticamente a medida que ε tiende a cero, por ejemplo, si el tiempo de ejecución es
Esto asegura que un aumento en el tamaño del problema tenga el mismo efecto relativo en el tiempo de ejecución, independientemente de qué
se esté usando; sin embargo, la constante bajo la notación O aún puede depender de
En otras palabras, un EPTAS se ejecuta en tiempo FPT donde el parámetro es
Aún más restrictivo, y útil en la práctica, es el esquema de aproximación de tiempo totalmente polinomial o FPTAS, que requiere que el algoritmo sea polinomial tanto en el tamaño del problema
[2] En consecuencia, bajo esta suposición, los problemas APX-difíciles no tienen PTAS.
Además, un PTAS puede ejecutarse en tiempo FPT para alguna parametrización del problema, lo que conduce a un esquema de aproximación parametrizado .
Algunos problemas que no tienen un PTAS pueden admitir un algoritmo aleatorio con propiedades similares, un esquema de aproximación aleatoria polinómica en tiempo o PRAS .
Convencionalmente, "alta probabilidad" significa una probabilidad superior a 3/4, aunque, como ocurre con la mayoría de las clases de complejidad probabilística, la definición es resistente a las variaciones de este valor exacto (el requisito mínimo es generalmente superior a 1/2).
Por otro lado, mostrar la no pertenencia a PTAS (es decir, la inexistencia de un PTAS), se puede hacer mostrando que el problema es APX-difícil, después de lo cual la existencia de un PTAS mostraría P = NP.
La dificultad APX se muestra comúnmente a través de la reducción PTAS o la reducción AP .