Cualquier consecuencia importante con presuposición de $\mathbf{P} \neq \mathbf{NP}$

Question

Como sabemos, hay muchas consecuencias con la presuposición de la Hipótesis de Riemann.

Del mismo modo, ¿existen consecuencias importantes con la presuposición de $\mathbf{P} \neq \mathbf{NP}$ ?

Una declaración alternativa de $\mathbf{P} \neq \mathbf{NP}$ es la Tesis de Church-Turing ampliada. Así que si tenemos un algoritmo de aceleración de otro modelo que no sea la máquina de Turing clásica, tenemos que encontrar un nuevo algoritmo para la máquina de Turing con la suposición $\mathbf{P} \neq \mathbf{NP}$ ? eso significa que tenemos que encontrar un nuevo algoritmo de aceleración de la factorización y similares.

Answer 1

Debido a que hay problemas computacionales naturales que involucran muchos objetos matemáticos, hay un montón de implicaciones de las separaciones de clases de complejidad como $\mathrm{P} \neq \mathrm{NP}$ . Creo que el primer artículo que investiga esta idea es probablemente el de Mike Freedman Clases de complejidad como axiomas matemáticos que supone una separación de clases de complejidad (a saber $\mathrm{NP} \neq \mathrm{P}^{\#\mathrm{P}}$ que es más fuerte que $\mathrm{P} \neq \mathrm{NP}$ ) para demostrar que existen nudos con ciertas propiedades.

La idea principal de todos estos argumentos es demostrar una implicación como "Si todos los objetos de tipo $T$ satisfacer la propiedad $P$ entonces hay un algoritmo eficiente para un problema que suponemos no tiene algoritmo eficiente". Entonces se puede deducir la existencia de objetos de tipo $T$ que satisfacen la propiedad $\neg P$ . (Aquí el significado de "eficiente" depende de la separación de clases que se asuma).

Lo que Freedman demuestra exactamente es un poco esotérico, así que permítanme dar otros dos ejemplos que tienen un sabor algo similar.

• El sístole de una variedad métrica es la longitud del bucle más corto no contratable en ella (también utilizaré la palabra para el bucle más corto en sí). Probablemente el primer colector cuya sístole trataría de entender es un toro plano $\mathbb{T}^d = \mathbb{R}^d / \Lambda$ para algún entramado $\Lambda = \langle v_1, \dots, v_d \rangle$ ya que se trata de las variedades métricas más sencillas.

  Una cosa natural podría ser intentar decir algo sobre la duración de la palabra de la sístole $\gamma$ cuando se considera como un elemento de $\pi_1(\mathbb{T}^d)$ equipado con el grupo electrógeno $\{ v_1^*, \dots, v_d^* \}$ donde $v_i^*$ es el bucle en $\mathbb{T}^d$ asociado naturalmente a $v_i$ . Por ejemplo, tal vez la sístole siempre tenga una palabra relativamente corta que la exprese. Por ejemplo, tal vez podamos escribir siempre $\gamma =_{\pi_1(\mathbb{T}^d)} \sum_i n_i v_i^*$ con $\sum_i |n_i| < \sqrt{d}$ o algo así.

  Resulta que un modesto refuerzo de $\mathrm{P} \neq \mathrm{NP}$ en realidad descarta esto. Específicamente, asumiendo que $\mathrm{NP}$ -los problemas difíciles no tienen tiempo $2^{o(n)}$ algoritmos probabilísticos de error limitado, podemos demostrar lo siguiente: Para cualquier $\ell(d) = o(d / \log d)$ existe un número infinito de $d$ y $\Lambda=(v_1, \dots, v_d)$ tal que cada bucle sistólico $\gamma$ en el toroide $\mathbb{R}^d / \Lambda$ tiene una longitud de palabra de al menos $\ell(n)$ en el grupo electrógeno $\{ v_1^*, \dots, v_d^* \}$ .

  La idea del argumento es simplemente que tal límite implicaría un algoritmo de tiempo sub-exponencial para el $\mathrm{NP}$ -Problema difícil de calcular la sístole: a saber, basta con enumerar todas las palabras posibles en los generadores de la longitud de palabra dada y elegir la que está representada por el bucle más corto (esto es fácil de calcular).

• Se puede utilizar un argumento similar para demostrar que las representaciones fieles de $S_n$ tienen una dimensión de al menos $n^{\varepsilon}$ para algunos $\varepsilon > 0$ (asumiendo alguna versión de la hipótesis del tiempo exponencial fuerte.) La idea básica está dada aquí -- el argumento es muy sencillo.

Creo que estos argumentos dan una idea de por qué debe ser difícil demostrar la separación de clases. Implican inmediatamente que los objetos matemáticos de todo tipo deben tener ciertos tipos de complejidad, o de lo contrario podrían utilizarse para dar algoritmos que contradigan las separaciones de clases. Así, la separación de clases demuestra simultáneamente la existencia de dicha complejidad en todos esos objetos matemáticos a la vez.

Bonificación: Tim Roughgarden e Inbal Talgam-Cohen tienen algunos escritos en esta línea y que las separaciones de clase implican mercados en los que no existen ciertos tipos de equilibrio.

Answer 2

Permítanme tomar un ángulo ligeramente diferente de esta cuestión e interpretarla como una pregunta sobre qué tipo de resultados de dureza requieren P != NP solamente, y cuáles requieren supuestos más fuertes.

Por sí mismo, P != NP implica (o más pedantemente, se sabe que implica) menos de lo que mucha gente piensa. Por ejemplo, estas son algunas de las cosas que P != NP es no conocido por implicar:

1. La factorización no tiene un algoritmo de tiempo polinómico.
2. El isomorfismo de grafos no tiene un algoritmo de tiempo polinómico.
3. Existen funciones unidireccionales.
4. En general, no hay un certificado corto de que un gráfico es no Hamiltoniano.
5. No existe una familia de circuitos de tamaño polinómico para SAT.
6. Los problemas NP-completos no tienen algoritmos de tiempo subexponencial.
7. Los problemas NP-completos son difíciles en promedio.
8. No existe ningún algoritmo aleatorio de tiempo polinómico para un problema NP-completo.
9. No existe ningún algoritmo de tiempo polinómico para un problema NP-completo en un ordenador cuántico.

Por otro lado, P != NP hace implican algunos resultados que a primera vista podrían parecer más fuertes que P != NP. Una clase notable de ejemplos son los resultados de inaproximabilidad que se derivan de la Teorema PCP . Por ejemplo, si P != NP entonces no hay ningún algoritmo de aproximación en tiempo polinómico para el tamaño del conjunto máximo independiente de un grafo que esté garantizado para llegar dentro de un factor constante (o incluso logarítmico) del óptimo. Otro ejemplo es Teorema de Mahaney que si P != NP entonces no hay ningún conjunto disperso que sea NP-completo.