¿Qué tan difícil sería indicar P contra NP en un asistente de prueba?

Question

gj woeginger enumera 116 pruebas inválidas del problema P vs. NP .Scott Aaronson publicó " Ocho letreros, una prueba p ≠ NP está incorrecta " para reducir el bomboCada vez que alguien intenta resolver P vs. NP.Algunos investigadores incluso Negado a los papeles de lectura a prueba de conformidad con el "P contrausNP "Pregunta .

Tengo 3 preguntas relacionadas:

1. ¿Por qué las personas no utilizan los asistentes de prueba que podrían verificar si una prueba de P vs. NP es correcta?
2. ¿Qué tan difícil o cuánto esfuerzo sería declarar P vs. NP en un asistente de prueba en primer lugar?
3. ¡Actualmente hay algún software que sea al menos en principio capaz de verificar una prueba P vs. NP?

Answer 1

Voy a estar en desacuerdo con DW. Creo que es posible (aunque difícil) para un resultado P vs. NP se indica en un asistente de prueba, y además, no confiaría en ninguna supuesta pruebas a menos que se formalizaran de esta manera, a menos que venían de Muy fuentes de buena reputación.

En particular, ninguno de los recursos de DW estados se basa en la teoría de tipo, que es una dirección muy prometedora para los asistentes de prueba. CoQ se ha utilizado para formalizar la prueba del teorema de 4 colores entre otros, por lo que es claramente Capaz de un levantamiento matemático pesado.

Para responder a sus preguntas específicas:

1. La razón principal es que los bromeros teoremas no son ampliamente aceptados en la comunidad matemática. Aprenderlos requiere esfuerzo, y los matemáticos son a menudo escépticos de las técnicas subyacentes (teoría de tipo, matemáticas constructivas, etc.) Pero hay algunos campos donde los líderes investigadores se sienten muy cómodos con hacer grandes desarrollos formalizados en un asistente de prueba, como la teoría de la categoría, la teoría del lenguaje de programación, la lógica formal, etc., por lo que creo que existe la mayor cantidad de un problema cultural como un problema de viabilidad inherente .

   La otra razón es que, hasta ahora, la mayoría de las supuestos "pruebas" han sido por manivelas, que no quieren formalizar su resultado porque inevitablemente revelará las fallas.

2. No es difícil indicar que establezca P vs. NP en un asistente de prueba. Uno podría usar las máquinas de Turing, pero probablemente sería más fácil modelar un lenguaje de programación completo de Turing-Turing utilizando familias inductivas para modelar semánticas de pequeño paso, y definir el tiempo de ejecución como el número de pasos que toma un programa. Puede definir $ P $ como los idiomas aceptados por los programas de detención en un número polinomial de pasos, y $ np $ Como lenguajes que se pueden verificar en poliamenta con un certificado de longitud polinomial.

   Editar: Resulta Hay técnicas existentes < / a> para mostrar que los algoritmos se ejecutan en tiempo polinomial en un prover teorema. Así que esto podría usarse para mostrar un algoritmo de polianza para un problema de NP-DURO, o para derivar una contradicción de la existencia de dicho algoritmo.

3. Hay toneladas de software que es capaz de verificar dicha prueba, siempre que la prueba se escribió usando ese software . Los dos candidatos en los que más en la mayoría de las acciones son coq y magra . CoQ en particular se ha utilizado para verificar varios resultados principales en matemáticas.

Answer 2

El uso de asistentes a prueba de este propósito es ciertamente posible en principio, pero sospecho que tomaría más esfuerzo que la mayoría de las personas que escriben tales pruebas estarían interesadas en ponerse. Requeriría una cantidad sustancial de esfuerzo del autor de una Preguntó la prueba P vs NP para formalizar su prueba.

Translando una prueba escrita para los humanos en un formato que un asistente de prueba puede verificar fue tedioso y lento. He visto estimaciones de entre un día a una semana de esfuerzo por página de prueba escrita humana. Luego, también debe formalizar todos los resultados anteriores que la prueba está construyendo. Cuando observamos los recientes intentos de demostrar P VS NP, generalmente usan una gran cantidad de maquinaria avanzada y sofisticados resultados preexistentes de los documentos anteriores, lo que deberían formalizarse también.

Debido a esto, espero que sea completamente práctico formalizar tanto a la nueva prueba propuesta como las pruebas de todos los resultados anteriores que confía, para los tipos de pruebas supuestas que hemos visto hasta ahora. Como user21820 señala , lo que sería más práctico sería formalizar solo la declaración de todos los resultados anteriores que se basan, pero no su prueba. Por lo tanto, en lugar de demostrar el teorema $ t $ , formalizaríamos una prueba de que $ (x \ tierres y \ tierra \ CDOTS) \ implica T $ , donde $ x, y, \ dots $ son los resultados anteriores de los que se basa la prueba. Esto se limita a verificar completamente el resultado de la integridad del NP, pero si las personas tienen fe en los resultados anteriores, permitiría a las personas ganar confianza en el nuevo resultado. Esto sería mucho más realista que la formalización de toda la prueba de $ t $ : mientras que tomaría algún esfuerzo formalizar todos los resultados anteriores $ X, Y, \ DOTS $ , es mucho menos que el esfuerzo por formalizar las pruebas de los resultados anteriores.

Aún así, sería un reto y requeriría un gasto no trivial de esfuerzo para formalizar una prueba, incluso con este truco.

Puede ver las bibliotecas existentes de teoremas en matemáticas e informática que se han formalizado y verificado formalmente: consulte http://us.metamath.org/ y http://formalmath.org/ y https://www.isa-afp.org/topics.html y http://mizar.org/library/ . Es posible que se note que muchos de lo que se formaliza se refiere al material de pregrado básico. Estamos lejos de formalizar todos los teoremas que se enseñan en un nivel de pregrado, y mucho menos aquellos que se enseñan en un nivel de posgrado, y mucho menos nuevos resultados de investigación.

Para más detalles, consulte https://math.stackexchange.com/q/792010/14578 y https://math.stackexchange.com/q/113316/14578 y https://math.stackexchange.com/q/1767070/14578 y https://math.stackexchange.com/q/2747661/14578 y http://www.ams.org/notices/200811/tx081101370p.pdf .

Answer 3

I can give a direct answer to (2): $P\ne NP$ has been stated in Lean (along with the other main results of Cook's paper, where the conjecture was first described), as part of the Formal Abstracts project.

Answer 4

I believe your question is not that much of a proper theory question, so with your permission I'll give it a not-so-technical answer.

Why are people not using proof assistants that could verify whether a proof of P vs. NP is correct?

Because CS theorists rarely (perhaps extremely rarely) write proofs in machine-verifiable form.

How hard or how much effort would it be to state P vs. NP in a proof assistant in the first place?

Very hard at least in the "uninteresting" sense that @DW explained; but it could be anywhere from easy to impossible in the "interesting" sense of expressing the concepts in a proof, if it were to exist.

But you know, this will never happen because:

1. Until a proof is found it can't be done anyway
2. You have to know the proof like the back of your hand to convert it into machine-verifiable form.
3. ... and when enough people know the proof, they will either have found a flaw or be satisfied that it's valid and not care about machine-checking it.

Is there currently any software that would be at least in principle capable of verifying a P vs. NP proof?

I'm not well-versed enough in proof verification software to comment about what's actually implemented, but it's probably nearly-impossible to answer your question, because - who knows what form such a proof will take? And thus - how would you know, now, if it's expressible in such a way that your proof verifier can process?