Tiempo cuasipolinomial

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, debería existir una constante tal que el tiempo de ejecución del algoritmo en el peor de los casos , en 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 cuasipolinomial son candidatos naturales para ser NP-intermedios , sin tener tiempo polinómico ni probablemente ser NP-difíciles .

Clase de complejidad

La clase de complejidad QP consta de todos los problemas que tienen algoritmos de tiempo cuasipolinomiales. Se puede definir 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 cuasipolinomial fue la prueba de primalidad de Adleman-Pomerance-Rumely ; ^[2] sin embargo, posteriormente se demostró que el problema de probar si un número es un número primo tiene un algoritmo de tiempo polinomial, la prueba de primalidad AKS . ^[3]

En algunos casos, se puede demostrar que los límites de tiempo cuasi polinomiales son óptimos según la hipótesis del tiempo exponencial o un supuesto de dureza 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 aparece como un subgrafo inducido de un gráfico determinado. ^[5]

Otros problemas para los cuales el algoritmo más conocido requiere un tiempo cuasi polinómico incluyen:

• El problema de la camarilla plantada , de determinar si un gráfico aleatorio ha sido modificado agregando 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, enumerando todos los conjuntos mínimos de aciertos de una familia de conjuntos, o enumerando todas las cubiertas de conjuntos mínimos de una familia de conjuntos, con la complejidad del tiempo medida en la entrada y salida combinadas. tamaño. ^[7]
• Juegos de paridad , que implican pasar fichas a lo largo de los bordes de un gráfico dirigido de color. ^[8] El artículo que proporciona un algoritmo cuasipolinomial para estos juegos ganó el Premio Nerode 2021 . ^[9]
• "Calcular 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 ventaja 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 han publicado en su totalidad incluyen:

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

En algoritmos de aproximación

El tiempo cuasipolinomial 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 polinomio en lugar de polinomio. Los problemas con un QPTAS incluyen la triangulación de peso mínimo , ^[14] y encontrar la camarilla máxima en el gráfico de intersección de discos. ^[15]

Más concretamente, el problema de encontrar un equilibrio de Nash aproximado tiene un QPTAS, pero no puede tener un PTAS según la hipótesis del tiempo exponencial. ^[dieciséis]

Referencias

1. Complexity Zoo : Clase QP: Tiempo cuasipolinomial
2. Adleman, Leonard M .; Pomerancia, Carl ; Rumely, Robert S. (1983), "Sobre la distinción de números primos de 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) polinómico", 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), "Cuasipolinomialidad 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. Hazán, 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", Matemáticas aplicadas discretas , 156 (11): 2035–2049, doi : 10.1016/j.dam.2007.04.017 , MR  2437000
8. Calude, Cristian S.; Jainista, Sanjay; Khoussainov, Bakhadyr; Li, Wei; Stephan, Frank (2022), "Decidir juegos de paridad en tiempo cuasi polinómico", SIAM Journal on Computing , 51 (2): STOC17-152–STOC17-188, doi :10.1137/17M1145288, 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. Meguido, Nimrod ; Vishkin, Uzi (1988), "Sobre la búsqueda de un conjunto dominante mínimo en un torneo", Ciencias de la Computación Teórica , 61 (2–3): 307–316, doi :10.1016/0304-3975(88)90131-4, SEÑOR  0980249
12. Klarreich, Erica (14 de enero de 2017), "El isomorfismo gráfico vencido, otra vez", Revista Quanta
13. Marc Lackenby anuncia un nuevo algoritmo de reconocimiento de nudos que se ejecuta en tiempo cuasi polinómico, Instituto de Matemáticas, Universidad de Oxford , 2021-02-03 , consultado el 2021-02-03
14. Remy, enero; Steger, Angelika (2009), "Un esquema de aproximación de tiempo cuasi polinómico 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. Hombre valiente, Mark ; Kun-Ko, joven; 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)}}$