proofs – ¿Se consideraría suficiente una prueba asumiendo una ley física?

Pregunta:

Siempre me he preguntado si las pruebas en informática se considerarían pruebas suficientes de la proposición si tuvieran que asumir leyes físicas.
Por ejemplo, me pregunto qué pasaría si alguien algún día probara P! = NP bajo el supuesto de la segunda ley de la termodinámica. ¿Resolvería esto el debate de P! = NP?
¿O el problema aún se consideraría sin resolver si se basa en supuestos físicos?

Respuesta:

Me parece al menos posible, pero actualmente muy poco probable. Para resumir lo siguiente, se debe a que el enunciado matemático actual de (digamos) P vs NP es completamente independiente de cualquier ley de la física, por lo que sería necesario describir nuevos modelos de cálculo que dependan de los axiomas de la física.

El punto clave que Peter Shor hizo en su comentario es que las preguntas de la teoría de la CS, como P vs NP, se refieren a modelos matemáticos muy simples y estilizados. No son declaraciones sobre el mundo real. Simplemente dicen "en este modelo matemático, ___ es cierto".

Ahora bien, a menudo se tienen leyes empíricas, como la tesis de Church-Turing, que establecen que el mundo real actúa como estos modelos matemáticos. Pero esa es una conexión unidireccional (¡no significa que los modelos matemáticos deban actuar como el mundo real!). Para desarrollar el ejemplo de Peter Shor, el teorema de Pitágoras solo necesita las ideas de números reales y el plano / distancia euclidiana. El modelo es mucho más simple que el mundo real y no involucra, por ejemplo, gravedad, electromagnetismo, termodinámica, etc. E incluso si el teorema de Pitágoras fuera a veces falso en realidad debido a estas complicaciones, esto no afectaría su verdad matemática.

De manera similar, el modelo de la máquina de Turing y las definiciones de P, NP, etc. son mucho más simples que el mundo real. El modelo no involucra cosas como la gravedad, la entropía termodinámica, etc. La verdad de P frente a NP no depende de si el cálculo realmente puede ocurrir de manera eficiente en el mundo real.

Ahora, me parece hipotéticamente posible que en el futuro podamos descubrir conexiones más estrechas entre las leyes de la física y las leyes de la computación. Lo que sucedería entonces es que el modelo matemático de la Máquina de Turing tendría que expandirse para dar cuenta de estas conexiones. Entonces, habría que formular nuevas definiciones de P y NP para este nuevo modelo y argumentar que son "mejores" que el modelo y las definiciones anteriores. Entonces, en este nuevo modelo consciente de la física, uno podría tener axiomas de física que se utilizan en las pruebas. Pero esto parece muy poco probable / lejos de suceder, al menos para mí.

Leave a Comment

Your email address will not be published.

Scroll to Top

istanbul avukat

-

web tasarım