En informática (particularmente algorítmica ), un esquema de aproximación en tiempo polinómico ( PTAS ) es un tipo de algoritmo de aproximación para problemas de optimización (más a menudo, 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 del viajante euclidiano , un PTAS produciría un recorrido con una duración máxima de (1 + ε) L , siendo L 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 el 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 reduce, por ejemplo, si el tiempo de ejecución es O ( n (1/ε)! ) . Una forma de abordar esto es definir el esquema eficiente de aproximación de tiempo polinomial o EPTAS , en el que se requiere que el tiempo de ejecución sea O ( n c ) para una constante c independiente de ε . 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é utilizando; sin embargo, la constante bajo la O grande todavía 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 en tiempo totalmente polinómico o FPTAS , que requiere que el algoritmo sea polinómico 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 cuasipolinomial o QPTAS . Un QPTAS tiene complejidad temporal n polilog ( n ) para cada ε fijo > 0 . 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 aleatorio en tiempo polinomial o PRAS . Un PRAS es un algoritmo que toma una instancia de un problema de optimización o de conteo y un parámetro ε > 0 y, en tiempo polinómico, produce una solución que tiene una alta probabilidad de estar dentro de un factor ε del óptimo. Convencionalmente, "alta probabilidad" significa probabilidad mayor que 3/4, aunque como ocurre con la mayoría de las clases de complejidad probabilística, la definición es sólida ante 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 eficiente de aproximación aleatoria en tiempo polinomial o EPRAS similar al EPTAS, y un esquema de aproximación completamente aleatorio en tiempo polinomial o FPRAS similar al FPTAS. [3]
El término PTAS también puede usarse 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 membresía en PTAS se puede demostrar usando una reducción de PTAS , una reducción L o una reducción P , todas las cuales preservan la membresía de PTAS, y también se pueden usar para demostrar que PTAS está completo. Por otro lado, mostrar la no membresía en PTAS (es decir, la inexistencia de un PTAS) se puede hacer demostrando que el problema es APX-duro, después de lo cual la existencia de un PTAS mostraría P = NP. La dureza APX se muestra comúnmente mediante la reducción de PTAS o la reducción de AP .