Siempre me he preguntado si las pruebas en ciencias de la computación se considerarían pruebas suficientes de la propuesta si tuvieran que asumir leyes físicas.
Por ejemplo, me pregunto qué pasaría si algún día alguien 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 suposiciones físicas?
8
Respuestas:
Al menos me parece posible, pero actualmente es muy poco probable. Para resumir lo siguiente, es porque la declaración matemática actual de (digamos) P vs NP es completamente independiente de cualquier ley de física, por lo que sería necesario describir nuevos modelos de computación que sí dependen 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 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, uno a menudo tiene leyes empíricas, como la tesis de Church-Turing, que establece 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 deben 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 euclidiano. El modelo es mucho más simple que el mundo real y no involucra, por ejemplo, la gravedad, el electromagnetismo, la termodinámica, etc. E incluso si el teorema de Pitágoras a veces fuera falso en realidad debido a estas complicaciones, esto no afectaría su verdad matemática.
Del mismo modo, el modelo para 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 vs. NP no depende de si la computación puede suceder efectivamente 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 tener en cuenta 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 con conciencia física, uno podría tener axiomas físicos que se usan en pruebas. Pero esto parece muy poco probable / lejos de suceder, al menos para mí.
fuente
Me gusta la pregunta ... pero la respuesta sigue siendo "no", como lo han indicado otros colaboradores. La pregunta en sí es metamatemática, por eso me gusta.
Las matemáticas y la física son universos epistemológicos diferentes, y nunca se encontrarán los dos. Un universo matemático está construido de 1) definiciones (como los enteros) 2) axiomas y 3) reglas para contraer nuevas declaraciones verdaderas de declaraciones verdaderas conocidas (como Modus Ponens, que dicta que A-> B y A juntas implican B). Los objetos físicos no tienen entrada en tal universo.
El universo físico es materia, y, como dijo Schopenhauer, la materia es causalidad y la causalidad es materia. Los objetos matemáticos y las pruebas no tienen ningún impacto como tal en el mundo físico (aunque puede haber impactos de personas que creen en afirmaciones matemáticas y sus pruebas). La ciencia consiste en sistemas que describen, más o menos fielmente, fenómenos observables del mundo físico. Creo que Karl Popper capturó esta epistemología mejor en su teoría de la falsificación empírica. La ciencia utiliza las matemáticas en sus descripciones, pero la ciencia no es en sí misma el mundo fenoménico.
Los fenómenos naturales no tienen que obedecer nuestras matemáticas, y nuestras matemáticas no pueden ser probadas como verdaderas o falsas por el mundo físico. Pero no es casualidad que las matemáticas parezcan capturar aspectos de lo que observamos, lo hicimos así. El mundo fenomenal inspiró las definiciones que son el material del universo matemático.
No es tan sorprendente que esta pregunta surja en informática, ya que la computadora es el objeto físico fundamental para imitar el mundo matemático .
fuente
La premisa de la pregunta está orientada a la investigación pero un tanto confusa / al revés en el siguiente sentido. De hecho, se ha demostrado una conexión profunda entre la termodinámica y la complejidad CS en el área de los "vidrios giratorios", donde el proceso de orientación magnética que se establece durante el enfriamiento imita de cerca la transición de fase que se encuentra en SAT, y esta conexión continúa siendo explorada y se considera mucho más significativo que meramente casual.
en cierto sentido, la "dureza" computacional parece ser una "explicación" o modelo matemático básico para un proceso termodinámico fundamental. También la termodinámica tiene la proscripción contra las máquinas de energía perpetua, pero que también puede verse como una restricción general contra las máquinas que no pueden exceder ciertos "límites de velocidad física". si P! = NP, entonces una máquina física que resolvió los problemas de NP en el tiempo P no podría existir y "desafiaría las leyes de la física", es decir, en la "velocidad" a la que "manipula la información". pero muchos físicos están concluyendo que las leyes de la física aparentemente se reducen esencialmente a la manipulación de la información. en resumen, es muy probable que la tendencia sea que la teoría de la complejidad computacional en el futuro explique mejor las leyes fundamentales de la termodinámica.
más detalles, ver por ejemplo esta tesis doctoral (2013):
fuente