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 ${\displaystyle c}$ ${\displaystyle 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 .

Clase de complejidad

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)}$

Ejemplos

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]

En algoritmos de aproximación

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]

Referencias

1. Complexity Zoo : Clase QP: Tiempo cuasipolinomial
2. Adleman, Leonard M. ; Pomerance, Carl ; Rumely, Robert S. (1983), "Sobre la distinción entre números primos y números compuestos", Annals of Mathematics , 117 (1): 173–206, doi :10.2307/2006975, JSTOR  2006975
3. Agrawal, Manindra ; Kayal, Neeraj ; Saxena, Nitin (2004), "PRIMES está en P" (PDF) , Annals of Mathematics , 160 (2): 781–793, doi :10.4007/annals.2004.160.781, JSTOR  3597229
4. Kisfaludi-Bak, Sándor (2020), "Gráficos de intersección hiperbólica y tiempo (cuasi)polinomial", en Chawla, Shuchi (ed.), Actas del 31.º Simposio anual ACM-SIAM sobre algoritmos discretos, SODA 2020, Salt Lake City, UT, EE. UU., 5 al 8 de enero de 2020 , págs. 1621-1638, arXiv : 1812.03960 , doi : 10.1137/1.9781611975994.100, ISBN 978-1-61197-599-4
5. Eppstein, David ; Lincoln, Andrea; Williams, Virginia Vassilevska (2023), "Cuasipolinomia del subgrafo inducido faltante más pequeño", Journal of Graph Algorithms and Applications , 27 (5): 329–339, arXiv : 2306.11185 , doi : 10.7155/jgaa.00625
6. Hazan, Elad; Krauthgamer, Robert (2011), "¿Qué tan difícil es aproximarse al mejor equilibrio de Nash?", SIAM Journal on Computing , 40 (1): 79–91, CiteSeerX 10.1.1.511.4422 , doi :10.1137/090766991, MR  2765712 
7. Eiter, Thomas; Makino, Kazuhisa; Gottlob, Georg (2008), "Aspectos computacionales de la dualización monótona: un breve estudio", Discrete Applied Mathematics , 156 (11): 2035–2049, doi : 10.1016/j.dam.2007.04.017 , MR  2437000
8. Calude, Cristian S.; Jain, Sanjay; Khoussainov, Bakhadyr; Li, Wei; Stephan, Frank (2022), "Decidir juegos de paridad en tiempo cuasi-polinomial", SIAM Journal on Computing , 51 (2): STOC17-152–STOC17-188, doi :10.1137/17M1145288, hdl : 2292/31757 , MR  4413072
9. Premio IPEC Nerode, EATCS , consultado el 3 de diciembre de 2023
10. Papadimitriou, Christos H. ; Yannakakis, Mihalis (1996), "Sobre el no determinismo limitado y la complejidad de la dimensión VC", Journal of Computer and System Sciences , 53 (2): 161–170, doi : 10.1006/jcss.1996.0058 , MR  1418886
11. Megiddo, Nimrod ; Vishkin, Uzi (1988), "Cómo encontrar un set mínimo dominante en un torneo", Theoretical Computer Science , 61 (2–3): 307–316, doi :10.1016/0304-3975(88)90131-4, MR  0980249
12. Klarreich, Erica (14 de enero de 2017), "El isomorfismo gráfico fue derrotado, una vez más", Quanta Magazine
13. Marc Lackenby anuncia un nuevo algoritmo de reconocimiento de nudos que se ejecuta en tiempo cuasi-polinomial, Mathematical Institute, University of Oxford , 2021-02-03 , consultado el 2021-02-03
14. Remy, Jan; Steger, Angelika (2009), "Un esquema de aproximación temporal cuasi-polinomial para la triangulación de peso mínimo", Journal of the ACM , 56 (3), Artículo A15, doi :10.1145/1516512.1516517
15. Capo, Édouard; Giannopoulos, Panos; Kim, Eun Jung ; Rzazewski, Pawel; Sikora, Florian (2018), "QPTAS y algoritmo subexponencial para camarilla máxima en gráficos de disco", en Speckmann, Bettina ; Tóth, Csaba D. (eds.), 34.º Simposio internacional sobre geometría computacional, SoCG 2018, 11 al 14 de junio de 2018, Budapest, Hungría , LIPIcs, vol. 99, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, págs. 12:1–12:15, doi : 10.4230/LIPICS.SOCG.2018.12
16. Braverman, Mark ; Kun-Ko, Young; Weinstein, Omri (2015), "Aproximar el mejor equilibrio de Nash en el tiempo rompe la hipótesis del tiempo exponencial", en Indyk, Piotr (ed.), Actas del 26.º Simposio anual ACM-SIAM sobre algoritmos discretos, SODA 2015, San Diego, CA, EE. UU., 4 al 6 de enero de 2015 , págs. 970–982, doi :10.1137/1.9781611973730.66 ${\textstyle n^{o(\log n)}}$