Tiempo cuasi-polinomial

En la teoría de la complejidad computacional y el análisis de algoritmos , se dice que un algoritmo toma un tiempo cuasipolinomial si su complejidad temporal está acotada cuasipolinomialmente . Es decir, debe existir una constante tal que el tiempo de ejecución del algoritmo en el peor de los casos , con entradas de tamaño , tenga un límite superior de la forma ${\estilo de visualización c}$${\estilo de visualización n}$$${\displaystyle 2^{O{\bigl (}(\log n)^{c}{\bigr )}}.}$$

Los problemas de decisión con algoritmos de tiempo cuasi-polinomial son candidatos naturales para ser NP-intermedios , ya que no tienen tiempo polinomial ni es probable que sean NP-difíciles .

La clase de complejidad QP está formada por todos los problemas que tienen algoritmos de tiempo cuasi-polinomial. Puede definirse en términos de DTIME de la siguiente manera. ^[1]

${\displaystyle {\mathsf {QP}}=\bigcup _{c\in \mathbb {N}}}{\mathsf {DTIME}}\left(2^{(\log n)^{c}}\right)}$

Un ejemplo temprano de un algoritmo de tiempo cuasi-polinomial fue la prueba de primalidad de Adleman-Pomerance-Rumely ; ^[2] sin embargo, posteriormente se ha demostrado que el problema de comprobar si un número es primo tiene un algoritmo de tiempo polinomial, la prueba de primalidad AKS . ^[3]

En algunos casos, se puede demostrar que los límites temporales cuasipolinómicos son óptimos bajo la hipótesis del tiempo exponencial o un supuesto de dificultad computacional relacionado . Por ejemplo, esto es cierto para encontrar el subconjunto disjunto más grande de una colección de discos unitarios en el plano hiperbólico ^[4] y para encontrar un gráfico con la menor cantidad de vértices que no aparezca como un subgráfico inducido de un gráfico dado ^{[5] .}

Otros problemas para los cuales el algoritmo más conocido toma un tiempo cuasi-polinomial incluyen:

• El problema de la camarilla plantada , que consiste en determinar si un gráfico aleatorio ha sido modificado añadiendo aristas entre todos los pares de un subconjunto de sus vértices. ^[6]
• Dualización monótona , varios problemas equivalentes de conversión de fórmulas lógicas entre forma normal conjuntiva y disyuntiva, enumeración de todos los conjuntos mínimos coincidentes de una familia de conjuntos, o enumeración de todas las cubiertas de conjuntos mínimos de una familia de conjuntos, con complejidad temporal medida en el tamaño combinado de entrada y salida. ^[7]
• Juegos de paridad , que implican el paso de fichas a lo largo de los bordes de un gráfico dirigido de color. ^[8] El artículo que presenta un algoritmo cuasipolinomial para estos juegos ganó el Premio Nerode 2021. ^[9]
• Cálculo de la dimensión de Vapnik-Chervonenkis de una familia de conjuntos . ^[10]
• Encontrar el conjunto dominante más pequeño en un torneo , un subconjunto de los vértices del torneo que tiene al menos una arista dirigida a todos los demás vértices. ^[11]

Los problemas para los cuales se ha anunciado un algoritmo de tiempo cuasipolinomial pero no se ha publicado en su totalidad incluyen:

• El problema del isomorfismo de grafos , que determina si dos grafos pueden hacerse iguales entre sí reetiquetando sus vértices, anunciado en 2015 y actualizado en 2017 por László Babai . ^[12]
• El problema del desanudamiento , reconocer si un diagrama de nudos describe el desanudamiento , anunciado por Marc Lackenby en 2021. ^[13]

El tiempo cuasi-polinomial también se ha utilizado para estudiar algoritmos de aproximación . En particular, un esquema de aproximación de tiempo cuasi-polinomial (QPTAS) es una variante de un esquema de aproximación de tiempo polinomial cuyo tiempo de ejecución es cuasi-polinomial en lugar de polinomial. Los problemas con un QPTAS incluyen la triangulación de peso mínimo ^[14] y la búsqueda de la camarilla máxima en el gráfico de intersección de discos. ^[15]

Más fuertemente, el problema de encontrar un equilibrio de Nash aproximado tiene un QPTAS, pero no puede tener un PTAS bajo la hipótesis del tiempo exponencial. ^[16]