¿Es esta conjetura estrictamente más débil que P=NP?

Question

Mi tres computabilidad preguntas están relacionados con la siguiente pregunta de teoría de grupos (planteada por primera vez por Bridson en 1996):

Para qué real $\alpha\ge 2$ la función $n^\alpha$ es equivalente a la función de Dehn de un grupo finitamente presentado (es decir, qué números pertenecen al espectro isoperimétrico )?

Claramente $\alpha\ge 1$ por cada $\alpha$ en el espectro isiperimétrico, y por el teorema de Gromov, el espectro isoperimétrico no contiene números de $(1,2)$ .

En lo que sigue, todas las funciones están acotadas por polinomios, por lo que dos funciones $f(n), g(n)$ son equivalentes si $af(n)<g(n)<bf(n)$ para algún positivo $a, b$ . No es necesario saber qué es la función de Dehn de un grupo (es una importante invariante asintótica de un grupo ). En este demostramos que si $\alpha\ge 4$ pertenece al espectro isoperimétrico si $\alpha$ puede ser calculado por una máquina de Turing no determinista en un tiempo máximo de $2^{c2^m}$ para algunos $c>0$ . Recientemente Olshanskii demostró la misma afirmación para todos $\alpha\ge 2$ (el artículo aparecerá en el Journal of Combinatorial Algebra). Por otra parte, si $\alpha$ está en el espectro isoperimétrico, entonces $\alpha$ puede calcularse en un tiempo máximo de $2^{2^{c2^{m}}}$ para algunos $c>0$ . Si P=NP, entonces se puede reducir el número de 2's a dos y hacer que el límite superior sea igual al inferior, completando la descripción del espectro isoperimétrico. Pero la prueba de nuestro trabajo (Corolario 1.4) daría dos 2's también si se cumple la siguiente conjetura, aparentemente más débil.

Conjetura. Dejemos que $T(n)$ sea la función de tiempo de una máquina de Turing no determinista que esté entre $n^2$ y $n^k$ para algunos $k$ . Entonces hay una máquina de Turing determinista $M$ calcular una función $T'(n)$ lo que equivale a $T(n)$ y teniendo la función de tiempo como máximo $T(n)^c$ para alguna constante $c$ (dependiendo de $T$ ). (Para la definición de la función temporal, véase esta pregunta ).

Pregunta ¿Es la conjetura estrictamente más débil que P=NP?

Actualización Mi nota con referencia a la respuesta de Emil es aquí .

Answer 1

En efecto, la conjetura es estrictamente más débil que $\mathrm{P = NP}$ en el sentido de que se deduce de $\mathrm E=\Sigma^E_2$ que no se sabe si implica $\mathrm{P = NP}$ . Por supuesto, no podemos probar esto incondicionalmente con la tecnología actual, ya que establecería $\mathrm{P\ne NP}$ .

Aquí, $\mathrm E$ denota $\mathrm{DTIME}(2^{O(n)})$ , $\mathrm{NE}$${}=\mathrm{NTIME}(2^{O(n)})$ y $\Sigma^E_2=\mathrm{NE^{NP}}$ es el segundo nivel de la jerarquía exponencial (con exponente lineal), $\mathrm{EH}$ . (Véase, por ejemplo, [2]; advertencia: su notación para $\mathrm{(N)E}$ y $\mathrm{EH}$ es $\mathrm{(N)EXPTIME}$ y $\mathrm{EXPH}$ que hoy en día se utilizan para clases algo diferentes). De forma equivalente, podemos definir $\Sigma_2^E$ utilizando máquinas de Turing alternas (véase [1,§5.3]) como $\Sigma^E_2=\Sigma_2\text-\mathrm{TIME}(2^{O(n)})$ .

Tenga en cuenta que a la inversa, $\mathrm{P = NP}$ implica $\mathrm{P=PH}$ , lo que implica $\mathrm E = \Sigma^E_2=\mathrm{EH}$ mediante un argumento de relleno similar al de [1,§2.6.2].

Para ver que $\mathrm E = \Sigma^E_2$ implica la conjetura, dejemos que $t$ sea la función definida exactamente como $T$ pero con los enteros de entrada y salida escritos en binario y que $g_t=\{(x,y):y\le t(x)\}$ sea su subgrafo. Entonces $g_t\in\Sigma^E_2$ para mostrar $(x,y)\in g_t$ sólo tenemos que adivinar (de forma no determinista) una entrada $w$ de la NTM original de longitud $x$ junto con un cómputo de aceptación, y (de forma codeterminada) comprobar que no hay ningún cómputo de aceptación de longitud $<y$ . Este es un $\Sigma_2$ -máquina que funciona en tiempo polinómico en $x$ o exponencial en la longitud de la representación binaria de $x$ .

Por lo tanto, si $\mathrm E = \Sigma^E_2$ entonces $g_t\in\mathrm E$ . Entonces podemos calcular $t$ (como función) de forma determinista en tiempo exponencial utilizando la búsqueda binaria, y por lo tanto podemos calcular $T(n)$ en tiempo polinómico en $n$ .

Referencias:

[1] Sanjeev Arora y Boaz Barak, Complejidad computacional: Un enfoque moderno , Cambridge University Press, 2009.

[2] Juris Hartmanis, Neil Immerman y Vivian Sewelson, Conjuntos dispersos en NPP: EXPTIME frente a NEXPTIME , Information and Control 65 (1985), no. 2-3, pp. 158-181, doi: 10.1016/S0019-9958(85)80004-8 .