Análogos de P vs. NP en la historia de las matemáticas.

Question

Hace poco me escribió una entrada en su blog titulada "el Caso Científico de La P≠NP". El argumento traté de articular no es que no parece ser "invisible cerco eléctrico" que separa los problemas en P de la NP-completo, y que este fenómeno se debe aumentar nuestra confianza en que P≠NP. Así, por ejemplo, la NP-completo Conjunto de Cubierta problema es approximable en el polinomio de tiempo dentro de un factor de ln(n), pero es NP-duro aproximado dentro de un incluso ligeramente menor factor (es decir, 0.999 ln(n)). Observe que, si el algoritmo de aproximación o la dureza resultado había sido un poco mejor de lo que era, entonces P=NP hubiera seguido inmediatamente. Y hay docenas de otros ejemplos como ese. Entonces, ¿cómo hacer que nuestros algoritmos y nuestro NP-resultados de dureza siempre se las arreglan para "evitar" que cruzan el uno al otro, incluso cuando la evitación requiere que "ambos sabemos acerca de" algunos especiales numérico del parámetro? A mí me parece que esto es mucho más fácil de explicar en el P≠NP hipótesis de que P=NP uno.

De todos modos, una de las preguntas que surgieron de la discusión de ese post fue lo suficientemente interesante (al menos para mí) que quería compartir en MO.

La pregunta es esta: Cuando, en la historia de las matemáticas, tienen problemas "como P vs NP" surgido, y luego ha sido resuelto? En esos casos, ¿cuáles fueron las resoluciones?

Me gustaría aclarar mejor lo que quiero decir por un problema de "como P vs NP"! Me refiero a lo siguiente:

1. Los matemáticos logró clasificar un gran número de objetos de interés para ellos, en dos grandes clases. (Idealmente, estas serían las dos de equivalencia de clases, como P y NP-completo los problemas, que se conjetura que es distinto. Pero me conformo con dos clases, una de las cuales claramente contiene a la otra, como P y NP, mientras muchos de los objetos conjetura que es en $\operatorname{Class}_2 \setminus \operatorname{Class}_1$ estaban conectadas entre sí por una compleja red de reducciones, como la NP-completos, los problemas son---así que poniendo uno de estos objetos en $\operatorname{Class}_1$ podría hacerlo también a otros muchos).

2. Los matemáticos conjeturó que las dos clases eran desiguales, pero fueron incapaces de demostrar o refutar que por un largo tiempo, incluso como ejemplos de objetos en las dos clases proliferado.

3. Finalmente, la conjetura fue probar o refutar.

4. Antes de la eventual solución, las dos clases que parecía ser separados por una barrera invisible," en el mismo sentido que P y NP-completo problemas. En otras palabras: había muchos de los resultados que, de haber sido ligeramente diferentes (por ejemplo, en algunos arbitrarias-en busca de parámetro), habría colapsado las dos clases, pero los resultados siempre abstenido de hacerlo.

Para dar una idea de lo que tengo en mente, aquí están los mejores ejemplos que hemos encontrado hasta el momento (yo diría que cumplan alguna de las condiciones anteriores, pero probablemente no todos ellos):

• David Speyer dio el ejemplo de Diophantine conjuntos de enteros y recursivamente enumerable conjuntos. El primero fue una vez que cree que ser un subconjunto de la última, pero ahora sabemos que son la misma.

• Sam Hopkins dio el ejemplo de simpléctica colectores frente a Kähler colectores. El primero contiene al segundo, pero la contención fue sólo resultó ser estricta por Thurston en la década de 1970.

• Me dio el ejemplo de la independencia de los resultados en la teoría de conjuntos. Hasta Cohen, hubo muchos demostrado declaraciones acerca de transfinito conjuntos y, a continuación, toda una clase de otras declaraciones---V=L, GCH, CH, CA, el Lema de Zorn, bien orderability...---que eran conocidos para ser interrelacionados por una red de implicaciones (o equivalentes, como en los tres últimos casos), pero se había resistido a la prueba de los intentos. Sólo con obligando fueron las dos clases de "separados", un resultado que algunos (como Gödel) había anticipado correctamente.

Answer 1

Esto no es exactamente análogo a P != NP, en la que dos grandes clases de existir y es indeciso si son iguales o no; en cambio, dos de los grandes "universos" que existen, de las cuales sólo una es la verdad, con uno de ellos creía firmemente que no existe, pero para que todos los intentos de desvirtuar este universo paralelo han sido derrotados por una barrera invisible. (Tal vez una teoría de la complejidad analogía sería un escenario en el que sabíamos que de Impagliazzo cinco mundos, sólo Algorithmica o Cryptomania eran posibles, pero no hemos podido determinar que, con ambos mundos, mostrando una igual propensión a "quieren que existe".)

De todos modos, la situación es en la teoría analítica de números, donde hay dos mundos (que, a muy grandes rasgos, correspondería a "Algorithmica" y "Cryptomania" en Impagliazzo de la lista):

• Siegel cero: Los números primos, de conspirar (es decir, muestran muy anómala de correlación) con algunos multiplicativo de la función, tales como un carácter de Dirichlet $\chi$; a grandes rasgos, esto significa que hay algún módulo de q tales que existe un gran sesgo entre los números primos a ser cuadrática nonresidues mod q en vez de residuos cuadráticos. (Dirichlet del teorema nos dice que la tendencia se va a disminuir con el tiempo, para los números primos exponencialmente mayor que p - pero esto no es útil en muchas aplicaciones). La manera más común para describir esta situación es a través de un "Siegel cero" - un cero de una L-función que está muy, muy lejos de la línea crítica (y muy cercano a 1). Extrañamente, tal conspiración en realidad hace que muchos problemas de la teoría acerca de los números primos más fácil que difícil, porque uno se pone a "fingir" que la función de Möbius es esencialmente un carácter. Por ejemplo, hay un lindo resultado de Salud-Marrón que si hay una familia infinita de Siegel ceros, entonces el doble primer conjetura es verdadera. (Básicamente, el principio es que en la mayoría de una conspiración en la teoría de los números pueden estar en vigor para cualquier universo; un Siegel cero de la conspiración se chupa toda la "conspiración de oxígeno" para un doble primer conspiración para celebrar también.) Eso lleva a algún otro comportamiento extraño; ya que, por ejemplo, la existencia de un Siegel cero obliga a muchos de los ceros de la de Riemann zeta función a tumbarse en la línea crítica y ser casi en progresión aritmética.

• Modelo estándar: este es el universo que se cree que existe, en la que los números primos no presentan especiales correlación con cualquier otro estándar de la multiplicación de la función. En este mundo, GRH se cree para ser verdad (y los ceros deben ser distribuidos de acuerdo a la GUE, en lugar de en progresiones aritméticas (esta última hipótesis en ocasiones se ha llamado la "hipótesis Alternativa")).

[Esta es una simplificación; tanto como cómo la complejidad de los teóricos no han descartado los mundos intermedios entre Algorithmica y Cryptomania, no tenemos tan fuerte de una separación entre estos dos el número de la teoría de los mundos como nos gustaría. Por ejemplo, no se podría pensar en los mundos intermedios donde no hay Siegel ceros, pero GRH o GUE todavía no (algo análogo a Impagliazzo del "Pessiland"). En la práctica, tenemos que debilitar a uno u otro de estos mundos, por ejemplo, mediante la sustitución de GRH con una mucho más débil cero región libre. Estoy quitar importancia a estos detalles técnicos, aunque para esta discusión. Mi sensación es que tenemos alguna posibilidad con la tecnología actual de la eliminación de algunos más de estos mundos intermedios, pero estamos bastante atascado en la eliminación de cualquiera de los extremos de los mundos.]

En muchos problemas diferentes en la teoría analítica de números, uno ha de dividirse en dos casos, dependiendo de cuál de las anteriores universos es en realidad la que vivimos, y el uso de argumentos diferentes para cada uno (que es la fuente principal de la famosa ineffectivity fenómeno en la teoría analítica de números, que muchas de las estimaciones implican totalmente ineficaz constantes, ya que podría depender de que el conductor de un Siegel cero, para el que no tenemos límite superior); encontrar una manera alrededor de esta dicotomía en uno solo de estos problemas sería un gran avance y podría llevar pronto a la eliminación de uno de estos universos a partir de la consideración. Pero hay una barrera invisible que parece bloquear nosotros de hacerlo; ambos universos presentan una sorprendente cantidad de "auto-consistencia", lo que sugiere que se podría modificar nuestro universo matemático muy ligeramente de una manera u otra a la "fuerza" uno de los dos escenarios en efecto (un poco como ¿cómo se puede obligar P igual o no igual a NP por la relativización). La "paridad de la barrera" en el tamiz de la teoría es uno de los grandes (y visible) de la sección de la valla, pero esta valla parece ser mucho más largo y más importante que esto de la paridad de la barrera.

Yo hable de estas cosas un poco más en este blog. Véase también la encuesta de Conrey que también fue vinculado anteriormente.

Answer 2

El conjunto de teoremas (lo que ahora llamamos) "la geometría absoluta" y el conjunto de los teoremas de "geometría euclidiana". Es decir, la historia del postulado paralelo. Ahora sabemos (después de Tarski de la formalización de la "primaria" de la geometría) que cada (de primer orden) euclidiana, pero no absoluta afirmación tiene un "NP-completos, como" papel (y su negación tiene la misma separación de papel para la absoluta y la geometría hiperbólica).

Edit: bueno, es un ejemplo fueron los conjuntos donde se espera que sea la misma, de modo que (2) se produce un error, así que quizás yo debería borrar este como respuesta y el post como los comentarios.

Edición de$^2$: formalmente (2) consideran que "la geometría absoluta" (se espera que se euclidiana) y "geometría hiperbólica" (se espera que sea inconsistente). En efecto, son diferentes, pero por razones muy diferentes de los esperados.

Edición de$^3$: en el mismo sentido, "problemas geométricos solucionable por regla y compás solos" y otros tipos de problemas (en Vilano de la clasificación de "avión" o "sólido" o "lineal").

Answer 3

El gran cardenal de la jerarquía en la teoría de conjuntos puede ser visto como un ejemplo de este fenómeno. Parece haber poca razón por la que en principio esperaba que las preguntas acerca de qué tipos de conjuntos infinitos existen tendría tan fundamentalmente diferentes meta-matemática personaje que otras preguntas comunes en las matemáticas. Seguramente hubiera parecido razonable, por ejemplo, a la espera de resolver las preguntas, ya sea por la prueba de la existencia de reclamaciones o la refutación de ellos, y hubo muchas preguntas detalladas acerca de las grandes cardenales de los primeros días. Me imagino que en los primeros días, las diversas grandes cardenales fueron tal vez se agruparon en un par de grupos. Por ejemplo, no fue entendido hasta mucho más tarde de lo que usted esperaría de cómo la medibles cardenales relacionados con el inaccesible cardenales. Mientras tanto, ahora, resulta que no sólo la independencia fenómeno se ejecuta por completo a través de la jerarquía, pero lo peor, no podemos aceptar la independencia de la existencia de grandes cardenales, incluso por medio de el tipo de consistencia relativa se encontraron resultados con la hipótesis continua y el axioma de elección. Esto es debido a que la jerarquía no es sólo el aumento en el deductivo de la fuerza sino también en la consistencia de la fuerza. Así que el gran cardenal de la jerarquía resulta para crear instancias de la consistencia de la fuerza de la jerarquía de lo predicho por Gödel del teorema de la incompletitud. Además, lo hace no con extraños auto-referencial afirmaciones o puramente sintáctica de coherencia de las afirmaciones, de la clase que aparecen en la prueba del teorema de la incompletitud, sino, más bien, con muy naturales afirmaciones acerca de la infinita combinatoria, afirmaciones de que la respuesta natural de las preguntas que habían surgido de forma independiente. La resolución final es que esta torre parece ser más alto de lo que podemos imaginar, y muy finamente separados en niveles, cada uno de los cuales refleja parte importante de su naturaleza a niveles más bajos, un rascacielos fractal.

Answer 4

un buen histórica y posiblemente pertinentes analogía de P vs NP en matemáticas (otros que el paralelo de la geometría postulado de la ya citada) es la imposibilidad de "cuadrar el círculo". el problema es, simplemente, afirmó y, naturalmente, conjeturó. para, literalmente, de aproximadamente dos milenios (este problema se remonta a los Griegos) muchos aficionados a la "experimentalistas" intento de encontrar construcciones donde se puede cuadrar el círculo o trisect un ángulo y hubo muchos defectuosa de la prueba de reclamaciones, algunos de los cuales implican muchos pasos [y eran difíciles de refutar incluso por los expertos que dedicó mucho tiempo].

el problema fue demostrado que es imposible en 1882 por Lindemanns prueba de la irracionalidad de la Pi. la prueba era extremadamente compleja en el tiempo y tomaron decenas de páginas.

así que un simple-declaró pregunta matemática/hecho acerca de la clasificación de un muy fundamentales de la constante matemática, el cual está relacionado con construcciones básicas de la geometría, se requiere una muy difícil solución que abarca muchos siglos de análisis.

por lo que el equivalente moderno/fenómeno de la búsqueda de P=NP algoritmos/pruebas pueden ser similares, en formas a esta antigua pregunta si es que alguna vez probado que P≠NP. uno también podría razonablemente esperar/suponer que P≠NP prueba va a ser muy complejos y requieren de muchas páginas por un experto. aquí los aficionados de los geómetras con su círculo cuadrado pruebas son análogos a los aficionados a los programadores que piensan que tienen P-algoritmos en tiempo de la NP completo de los problemas.

es mucho incluso para los expertos para refutar estas afirmaciones, y la mayoría de los expertos obstinadamente se niegan a participar en ese ejercicio. también si P≠NP, a continuación, que nunca puede ser demostrada por el hallazgo de un algoritmo, parece fundamentalmente requieren una construcción a prueba por un matemático y no el código escrito por el programador (y a pesar de Curry-Howard correspondencia que existen diferencias fundamentales que hay).

Answer 5

Solo voy a aclarar Sela es el resultado. No estoy seguro de que lo que realmente corresponde a la edición original. Morley se conjeturó en la década de 1960 que el número de modelos (hasta el isomorfismo) de un total de primer orden de la teoría con el cardenal $\kappa$, debe aumentar en $\kappa$ (con la conocida excepción de las teorías tales como algebraicamente cerrado campos que han countably muchos modelos contables y uno en todas las grandes cardinalidades).

Sela notable estrategia para responder a esta fue la conjetura alrededor de 1970 todos los posibles espectro de funciones de una lista corta pero con parámetros. Más tarde, en los años 70 se demostró que esto era "eventualmente corregir". El trabajo de Hart, Hrushovski, y Laskowski limpiado el más pequeño de los cardenales. La idea de que el argumento es mostrar que una teoría tiene una propiedad que implica que el número máximo de modelos o de lo contrario el fracaso de esta condición lleva a uno hacia la asignación de los invariantes. (por ejemplo, inestable - no hay una fórmula $\phi(\bar{x},\bar{y})$ y una secuencia $\bar{a}_i, \bar{b}_i$ tal que $\phi(\bar{a}_i, \bar{b}_j)$ fib $i < j$ - esto se llama el orden de la propiedad; con el fin de no surgir aquí.) Una colección de 5 de tales dicotomías, lo lleva a uno a clasificable teorías; cada modelo está determinado por un 'cardenal invariante' y por tanto el número de modelos en $\kappa$ está delimitado, bien por debajo de $2^\kappa$.