¿Hay más problemas de tiempo polinomial con límites inferiores de complejidad?

Estoy buscando más problemas en con límites inferiores de complejidad temporal clásica. Algunas personas podrían preguntarse cómo podría probar un límite tan bajo. Vea abajo.$P$

Límites inferiores exponenciales:

Reclamación: Si tiene un problema que es E X P T I M E -completo bajo reducciones polinómicas, entonces hay una constante α ∈ R tal que X no se puede resolver en el tiempo O ( 2 n α ) . $X$$EXPTIME$$\alpha \in \mathbb{R}$$X$$O(2^{n^{\alpha}})$

Idea de prueba: según el teorema de la jerarquía de tiempo, hay un problema en el tiempo O ( 2 n ) que no está en o ( 2 $Y$$O(2^n)$tiempo. Además, debe haber una reducción polinomio deYaX. Por lo tanto, hay una constantecde tal manera que esta reducción tiene una instancia de tamañondeYa una instancia de tamañoncparaX. El límite inferior paraYdeO(2n 1 - ϵ ) eltiempo cambia a un límite inferior paraXdeO(2n 1 - $o(\frac{2^n}{n})$$Y$$X$$c$$n$$Y$$n^c$$X$$Y$$O(2^{n^{1-\epsilon}})$$X$tiempo.$O(2^{n^{\frac{1-\epsilon}{c}}})$

Límites inferiores polinómicos:

Algunos problemas completos tienen buenas parametrizaciones en problemas de tiempo polinomial. Considere el problema X de antes. Supongamos que tenemos una parametrización k - X para X tal que:$EXPTIME$$X$$k$$X$$X$

• Para cada fijo , k - X está en tiempo polinómico.$k$$k$$X$

Por supuesto, hay excepciones a esto, pero intuitivamente, a medida que crece, los problemas de k - X deberían ser más difíciles porque X tiene un límite inferior de complejidad de tiempo exponencial.$k$$k$$X$$X$

Un ejemplo:

Un problema de ejemplo que ha surgido es el no vacío de intersección para los autómatas de los árboles. Es decir, dada una lista finita de autómatas de árbol, ¿existe un árbol que satisfaga simultáneamente todos los autómatas?

$EXPTIME$$k$$k$$n^{\Theta(k)}$

Pregunta:

$EXPTIME$

Aquí hay uno que involucra un juego de guijarros para 2 jugadores. Tú decides si es natural (:

T. Kasai, A. Adachi, S. Iwata. Clases de juegos de piedras y problemas completos. 1979

El teorema 3.1 tiene la integridad EXPTIMA del peeling. El teorema 3.3 tiene la facilidad de k-pebble.

A. Adachi, S. Iwata, T. Kasai. Algunos problemas de juego combinatorio requieren tiempo Omega (n ^ k). 1984

El teorema 3.2 tiene el límite inferior en k-pebble. Por último, también te puede interesar:

T. Kasai y S. Iwata. Problemas gradualmente intratables y límites inferiores de espacio logarítmico no determinantes. 1985

Lamentablemente, estos están detrás de los muros de pago :(