En informática (en particular en algoritmia ), un esquema de aproximación de tiempo polinomial ( PTAS ) es un tipo de algoritmo de aproximación para problemas de optimización (más frecuentemente, problemas de optimización NP-hard ).
Un PTAS es un algoritmo que toma una instancia de un problema de optimización y un parámetro ε > 0 y produce una solución que está dentro de un factor 1 + ε de ser óptima (o 1 – ε para problemas de maximización). Por ejemplo, para el problema euclidiano del viajante de comercio , un PTAS produciría un recorrido con una duración máxima de (1 + ε) L , donde L es la duración del recorrido más corto. [1]
Se requiere que el tiempo de ejecución de un PTAS sea polinómico en el tamaño del problema para cada ε fijo, pero puede ser diferente para diferentes ε. Por lo tanto, un algoritmo que se ejecuta en un tiempo O ( n 1/ε ) o incluso O ( n exp(1/ε) ) cuenta como un PTAS.
Un problema práctico con los algoritmos PTAS es que el exponente del polinomio podría aumentar drásticamente a medida que ε se contrae, por ejemplo, si el tiempo de ejecución es O ( n (1/ε)! ) . Una forma de abordar esto es definir el esquema de aproximación de tiempo polinomial eficiente o EPTAS , en el que se requiere que el tiempo de ejecución sea O ( n c ) para una constante c independiente de ε . Esto garantiza 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é utilizando; sin embargo, la constante bajo el gran O aún puede depender de ε arbitrariamente. 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 n como en 1/ε .
A menos que P = NP , se cumple que FPTAS ⊊ PTAS ⊊ APX . [2] En consecuencia, bajo este supuesto, los problemas APX-hard no tienen PTAS.
Otra variante determinista del PTAS es el esquema de aproximación de tiempo cuasi-polinomial o QPTAS . Un QPTAS tiene una complejidad temporal n polylog ( n ) para cada ε > 0 fijo . Además, un PTAS puede ejecutarse en tiempo FPT para cierta 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 en tiempo polinomial o PRAS . Un PRAS es un algoritmo que toma una instancia de un problema de optimización o conteo y un parámetro ε > 0 y, en tiempo polinomial, produce una solución que tiene una alta probabilidad de estar dentro de un factor ε de óptimo. Convencionalmente, "alta probabilidad" significa probabilidad mayor que 3/4, aunque como con la mayoría de las clases de complejidad probabilística la definición es robusta a las variaciones en este valor exacto (el requisito mínimo es generalmente mayor que 1/2). Al igual que un PTAS, un PRAS debe tener un polinomio de tiempo de ejecución en n , pero no necesariamente en ε ; con restricciones adicionales en el tiempo de ejecución en ε , se puede definir un esquema de aproximación aleatoria en tiempo polinomial eficiente o EPRAS similar al EPTAS, y un esquema de aproximación aleatoria en tiempo polinomial completamente o FPRAS similar al FPTAS. [3]
El término PTAS también puede utilizarse para referirse a la clase de problemas de optimización que tienen un PTAS. PTAS es un subconjunto de APX y, a menos que P = NP , es un subconjunto estricto. [2]
La pertenencia a PTAS se puede demostrar mediante una reducción PTAS , una reducción L o una reducción P , todas las cuales preservan la pertenencia a PTAS, y también se pueden usar para demostrar la completitud de PTAS. 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-duro, después de lo cual la existencia de un PTAS mostraría P = NP. La dureza APX se demuestra comúnmente mediante la reducción PTAS o la reducción AP .