Problemas con grandes brechas de complejidad abierta

Esta pregunta trata sobre problemas para los cuales existe una gran brecha de complejidad abierta entre el límite inferior conocido y el límite superior, pero no debido a problemas abiertos en las propias clases de complejidad.

Para ser más precisos, digamos que un problema tiene clases de brecha (con A ⊆ B , no definido de forma exclusiva) si A es una clase máxima para la cual podemos demostrar que es A -duro, y B es un límite superior mínimo conocido , es decir, tenemos un algoritmo en B para resolver el problema. Esto significa que si terminamos descubriendo que el problema es C -completo con A ⊆ C ⊆ B , no afectará la teoría de la complejidad en general, en lugar de encontrar un algoritmo P para un problema N P -completo.$A,B$$A\subseteq B$$A$$A$$B$$B$$C$$A\subseteq C\subseteq B$$P$$NP$

No estoy interesado en problemas con y B = N P , porque ya es el objeto de esta pregunta .$A\subseteq P$$B=NP$

Estoy buscando ejemplos de problemas con las clases gap que estén lo más lejos posible. Para limitar el alcance y precisar la pregunta, estoy especialmente interesado en los problemas con y B ⊇ E X P T I M E , lo que significa que tanto la membresía en P como E X P T I M E- completitud son coherentes con el conocimiento actual , sin hacer colapsar las clases conocidas (digamos clases de esta lista ).$A\subseteq P$$B\supseteq EXPTIME$$P$$EXPTIME$

El problema de la equivalencia de nudos .

Dados dos nudos dibujados en el plano, ¿son topológicamente iguales? Se sabe que este problema es decidible, y no parece haber ninguna obstrucción de la complejidad computacional para que esté en P. El mejor límite superior conocido actualmente en su complejidad temporal parece ser una torre de s de altura c n , donde c = 10 10 6 , yn es el número de cruces en los diagramas de nudos. Esto viene de un límite de Coward y Lackenby sobre la cantidad de movimientos Reidemeister necesarios para llevar un nudo a uno equivalente. Ver el artículo más reciente de Lackenby$2$$c^n$$c = 10^{10^{6}}$$n$ para algunos resultados relacionados más recientes y para la forma explícita del límite que doy arriba (página 16).

$2^n$$2^{n/2}$

$AC0$$NP$$NP$$AC0[2]$

$\sqrt{2}$$\mathsf{P^{{{PP}^{PP}}^{PP}}}$$\mathsf{BitSLP}$$n$$\mathsf{AC^0}$

$\mathbb{R}^3$$k$$\mathbb{R}^d$$k=1$$d=2$$k=2$$d=2$$k=2$$d=3$

El último artículo tiene muchas referencias para lecturas adicionales.

Los autómatas multicounter (MCA) son autómatas finitos equipados con contadores que se pueden incrementar y disminuir en un solo paso, pero solo toman números enteros> = 0 como números. A diferencia de las máquinas Minsky (también conocidas como autómatas de contador), los MCA no pueden probar si un contador es cero.

Uno de los problemas algorítmicos con una gran brecha relacionada con las MSC es el problema de accesibilidad. Por ejemplo, si el autómata puede alcanzar, desde una configuración con el estado inicial y todos los contadores a cero, una configuración con un estado de aceptación y todos los contadores a cero nuevamente.

El problema es difícil para EXPTIME (como lo muestra Richard Lipton en 1976), decidible (Ernst Mayr, 1981) y solucionable en Fω3 (gracias, Sylvain, por señalar esto). Una gran brecha.

$\mathsf{QMA}(2)$$\mathsf{QMA}$$\mathsf{NEXP}$

$\mathsf{EXPSPACE}$$\mathsf{P}$$\mathsf{P}$

Se sabe que el problema de Skolem (dada una recurrencia lineal con casos base enteros y coeficientes enteros, si alguna vez alcanza el valor 0) es NP-duro y no se sabe que sea decidible. Hasta donde sé, cualquier cosa intermedia sería coherente con nuestro conocimiento actual sin colapsos de clases de complejidad estándar.