¿Existe un problema natural en el tiempo cuasi polinomial, pero no en el tiempo polinomial?

László Babai demostró recientemente que el problema del isomorfismo gráfico está en tiempo cuasipolinomial . Véase también su discurso en la Universidad de Chicago, nota de las charlas de Jeremy Kun GLL post 1 , GLL post 2 , GLL post 3 .

Según el teorema de Ladner, si , entonces no está vacío, es decir, contiene problemas que no están ni en ni en completos. Sin embargo, el lenguaje construido por Ladner es artificial y no es un problema natural. No se sabe que ningún problema natural esté en incluso condicionalmente bajo . Pero se cree que algunos problemas son buenos candidatos para , como Factoring enteros y GI.$P \neq NP$$NPI$$NP$$P$$NP$$NPI$$P \neq NP$$NPI$

$NP \not\subseteq QP = DTIME(n^{poly\log n})$

Hay algunos problemas para los que conocemos algoritmos de tiempo cuasi-polinomiales, pero no se conoce ningún algoritmo de tiempo polinomial. Tales problemas surgen en los algoritmos de aproximación; Un ejemplo famoso es el problema del árbol de Steiner dirigido, para el cual existe un algoritmo de aproximación de tiempo cuasi polinomial que logra una relación de aproximación de ( n es el número de vértices). Sin embargo, mostrar la existencia de tal algoritmo de tiempo polinómico es un problema abierto.$O(\log^3 n)$$n$

Mi pregunta:

¿Conocemos algún problema natural que esté en $QP$ pero no en $P$ ?

De hecho, se han realizado bastantes trabajos recientes para probar el tiempo de ejecución cuasi-polinomial límite inferior para problemas computacionales, principalmente basados ​​en la hipótesis del tiempo exponencial. Aquí hay algunos resultados para problemas que considero bastante naturales (todos los resultados a continuación están condicionados a ETH):

• Aaronson, Impagliazzo y Moshkovitz [1] muestran un límite inferior de tiempo cuasi polinomial para problemas de satisfacción de restricciones densas (CSP). Tenga en cuenta que la forma en que CSP se define en este documento permite que el dominio sea polinomialmente grande, ya que se sabe que el dominio pequeño es PTAS.

• Braverman, Ko y Weinstein [2] demostrar un tiempo quasi-polinomio límite inferior para la búsqueda de -mejor ε -approximate equilibrio de Nash, que coincide con Lipton del et al. Algoritmo de [3].$\epsilon$$\epsilon$

• Braverman, Ko, Rubinstein y Weinstein [4] muestran un límite inferior de tiempo cuasi polinomial para aproximar el subgrafo más denso con integridad completa (es decir, dado un gráfico que contiene una k- clique, encuentra una subgrafía de tamaño k que es ( 1 - ϵ ) -denso para alguna pequeña constante ϵ ). Nuevamente, existe un algoritmo de tiempo cuasi-polinomial para el problema (Feige y Seltser [5]).$k$$k$$k$$(1 - \epsilon)$$\epsilon$

Referencias

1. AM con múltiples Merlins. En Computational Complexity (CCC), 2014 IEEE 29th Conference on, páginas 44–55, junio de 2014.

2. Mark Braverman, Young Kun Ko y Omri Weinstein. Aproximar el mejor equilibrio nash en -time rompe la hipótesis del tiempo exponencial. En Actas del Vigésimo Sexto Simposio Anual ACM-SIAM sobre Algoritmos Discretos, SODA '15, páginas 970–982. SIAM, 2015.$n^{o(log n)}$

3. Richard J. Lipton, Evangelos Markakis y Aranyak Mehta. Jugar juegos grandes usando estrategias simples. En Actas de la 4ª Conferencia ACM sobre Comercio Electrónico, EC '03, páginas 36–41, Nueva York, NY, EE. UU., 2003. ACM.

4. Mark Braverman, Young Kun-Ko, Aviad Rubinstein y Omri Weinstein. Dureza ETH para Densest- -Subgraph con perfecta integridad. Coloquio electrónico sobre la complejidad computacional (ECCC), 22:74, 2015.$k$

5. U. Feige y M. Seltser. En los problemas más densos de -subgraph. Informe técnico, 1997.$k$

Meguido y Vishkin demostraron que mínimo conjunto dominante en torneos está en . Mostraron que el conjunto dominante del torneo tiene un algoritmo de tiempo P si el SAT tiene un algoritmo de tiempo subexponencial. Por lo tanto, el problema de conjunto dominante del torneo no puede estar en P a menos que el ETH sea falso.$QP$$P$

Es muy interesante observar que la hipótesis del tiempo exponencial implica simultáneamente que el conjunto dominante del torneo no puede tener algoritmos de tiempo polinomiales y no puede ser completo$NP$ . En otras palabras, ETH implica que el conjunto dominante del torneo está en intermedio.$NP$

Woeginger sugiere un problema candidato que se puede resolver en tiempo cuasi polinomial y probablemente no tiene algoritmos de tiempo polinomial: dados enteros, ¿puede seleccionar log n de ellos que sumen 0 ?$n$$\log n$$0$

El cálculo de la dimensión VC parece improbable en tiempo polinómico, pero tiene un algoritmo de tiempo cuasipolinomial.

Además, parece difícil detectar una camarilla plantada de tamaño en un gráfico aleatorio, pero se puede encontrar en tiempo cuasipolinomial; aunque la naturaleza de este problema prometedor es algo diferente de los otros mencionados.$O(\log n)$

Si la hipótesis del tiempo exponencial es correcta (o incluso versiones más débiles), entonces no se puede resolver 3SAT para instancias con número de variables poliglog en tiempo polinómico. Por supuesto, el tiempo cuasi polinomial puede resolver estos casos fácilmente.

$T(n ) * \log n$$T(n)$$T(n)$

Recientemente se ha demostrado que los juegos de resolución de paridad están en QP: https://www.comp.nus.edu.sg/~sanjay/paritygame.pdf

$\mu$

$NP\cap coNP$$UP\cap coUP$

Sin embargo, el reciente artículo anterior dio un salto significativo a QP. Todavía se desconoce si estos juegos están en P.

En algoritmos clásicos, decaimiento de correlación y ceros complejos de funciones de partición de sistemas cuánticos de muchos cuerpos por Aram Harrow, Saeed Mehraban y Mehdi Soleimanifar

Un algoritmo clásico de tiempo cuasi polinomial que estima la función de partición de sistemas cuánticos de muchos cuerpos a temperaturas superiores al punto de transición de fase térmica

es presentado.

No se puede decir mucho sobre la parte de la pregunta "pero no en tiempo polinómico". Incluso puede ser probable que más adelante se encuentre un algoritmo de tiempo polinómico, dada la historia del trabajo anterior, ver más abajo.

¿Cómo se relaciona la "estimación de la función de partición" con los algoritmos de aproximación? Trabajo previo (p. 11):

Existe un enfoque conceptual diferente reciente para estimar la función de partición, que es la base de este trabajo. Este enfoque considera la función de partición como un polinomio de alta dimensión y utiliza la expansión truncada de Taylor para extender la solución en un punto computacionalmente fácil a un régimen de parámetros no trivial. Desde su introducción [Bar16a], este método se ha utilizado para obtener algoritmos deterministas para varios problemas interesantes, como los modelos de Ising ferromagnéticos y antiferromagnéticos [LSS19b, PR18] en gráficos acotados.

incluye

[LSS19b] Jingcheng Liu, Alistair Sinclair y Piyush Srivastava. La función de partición de Ising: ceros y aproximación determinista. Journal of Statistical Physics, 174 (2): 287–315, 2019. arXiv: 1704.06493

que menciona lo siguiente en esta sección sobre trabajo relacionado:

En una línea de trabajo paralela, Barvinok inició el estudio de la aproximación de Taylor del logaritmo de la función de partición, lo que condujo a algoritmos de aproximación de tiempo cuasipolinomial para una variedad de problemas de conteo [6, 7, 9, 10]. Más recientemente, Patel y Regts [41] mostraron que para varios modelos que pueden escribirse como sumas inducidas de subgrafías, uno puede obtener un FPTAS a partir de este enfoque.

[41] V. Patel y G. Regts. Algoritmos deterministas de aproximación de tiempo polinómico para funciones de partición y polinomios de grafos. SIAM J. Comput., 46 (6): 1893–1919, diciembre de 2017. arXiv: 1607.01167

En conclusión, "estimar la función de partición" está estrechamente relacionado con los algoritmos de aproximación, y ha habido algoritmos de aproximación de tiempo cuasipolinomial para una variedad de problemas de conteo, y para algunos de esos FPTAS se han obtenido. Entonces, en general, esta clase de problemas relacionados con la función de partición parece producir algoritmos de aproximación de tiempo cuasipolinomial, pero a menudo las mejoras posteriores alcanzan el tiempo polinomial.