Me estaba preguntando? ¿O si alguien sabe algún trabajo relacionado con los dos? ¿También un resultado negativo? Aquí CH es la hipótesis del continuo.
Respuesta
¿Demasiados anuncios?
Greg Case
Puntos
10300
P=NP es una media aritmética declaración: podemos código de las correspondientes máquinas de Turing deterministas por números de una manera bastante explícita recursiva (que también explícitamente es el de los códigos para el polinomio límites superior) y, a continuación, la igualdad entre ambas clases pueden ser discutidas por discutir numéricos de las propiedades de los índices que intervienen en la codificación, y el uso de una NP-completos problema, tales como 3SAT. La costumbre de formalización, muestra que P=NP" puede ser descrito por una declaración acerca de los números naturales de la forma $\exists n\,\forall m\,\varphi(n,m)$ donde todos los cuantificadores en $\varphi$ son acotados.
El estado de CH es completamente independiente de tales declaraciones: Cohen obligando técnica para la modificación de los modelos de la teoría de conjuntos nos permite pasar de un modelo de $M$ a un modelo de $M[G]$ algunas de cuyas propiedades hemos de control. La técnica no cambia nunca aritmética de las declaraciones. Con obligando podemos obtener modelos de CAD y modelos de su negación.
Por lo tanto, si suponiendo CH (o su negación) nos permite demostrar (o refutar) P=NP, el mismo puede ser realizado sin esta suposición. Y suponiendo que P=NP (o su negación) no nos permite demostrar (o refutar) CH, a menos que estamos en el absurdo de la situación en la que ZFC, el sistema estándar de la teoría de conjuntos, es en sí mismo incompatible, o es consistente y (decir) demuestra que P=NP, y, sin embargo, asumimos que P$\ne$NP (o viceversa). En ese tonto escenario, a continuación, podemos probar CH. Y su negación. (Porque inconsistente teorías de demostrar todo.)
