¿Una prueba asumiendo que una ley física se considera suficiente?

8

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?

usuario541686
fuente
66
La segunda ley de la termodinámica no tiene nada que ver con P NP, que es una pregunta puramente matemática. Eso sería esencialmente como decir que la relatividad era necesaria para demostrar el teorema de Pitágoras.
Peter Shor
@ PeterShor: No veo por qué, aunque probablemente sea porque simplemente no sé lo suficiente para ver por qué. Pero siento que intuitivamente no me sorprendería por completo si hubiera una conexión. Esto es obviamente puramente hipotético, pero si cada cambio de bit tiene un aumento mínimo asociado en la entropía, por ejemplo, entonces tal vez podría usar el cambio de entropía de la entrada a la salida para argumentar que un cierto número de bits debe haberse invertido, lo que tomaría una cantidad mínima de, por ejemplo, tiempo exponencial. O algo así, no lo sé. ¿Es tal prueba completamente fuera de cuestión? (¿Por qué?)
user541686
@Kaveh: No tengo un ejemplo, pero aquí hay uno potencial: creo que es razonable preguntar si un axioma como el axioma de elección "realmente" se mantiene en el mundo físico. Tal vez lo sea, tal vez no; tal vez nunca tengamos una forma de probarlo. Pero ciertamente podemos preguntar. Y si hubiera una forma física de demostrar que lo hace (n't), entonces eso implicaría que cualquier teorema basado en él es (in) verdadero en el mundo físico. Entonces, si acepto que lo mencionado anteriormente es una pregunta válida, entonces no requiere un gran salto de fe preguntar si existe tal axioma subyacente, por ejemplo, P vs. NP.
user541686
66
En su comentario anterior, creo que está confundiendo dos cosas diferentes: el uso de ideas derivadas de las leyes físicas en las pruebas matemáticas y el uso de las leyes reales de la física en las pruebas matemáticas. Por ejemplo, hay muchas pruebas matemáticas que usan la definición matemática de entropía; sin embargo, esta definición matemática existe y es útil independientemente de si las leyes de la termodinámica son o no verdaderas en física. Otro ejemplo: podemos usar el espacio euclidiano en pruebas matemáticas, a pesar del hecho de que el espacio físico real es curvo y no euclidiano.
Peter Shor

Respuestas:

7

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í.

usul
fuente
44
Si revisamos los modelos y cambiamos P y NP, ya no sería lo que llamamos "P vs. NP", sería una pregunta diferente. Ya sabemos que P no es igual a eficientemente computable en la práctica. La razón por la que mantenemos P es porque es una simplificación útil, no porque captura la realidad de la computación en la práctica.
Kaveh
Para ser justos, tampoco sabemos si es imposible construir una máquina de torneado no determinista. O una máquina PostBQP. La parte extraña es que cuando probamos cosas sobre los modelos de computación que podemos crear, podemos decir cosas sobre esos modelos que algunos consideran más "verdaderos" porque se aplican a cosas reales. Pero también estudiamos algoritmos sin tiempo de ejecución factible o modelos de cómputo que nunca se pueden realizar en la práctica, porque si los modelos en sí pueden realizarse o no es independiente de lo que podamos probar sobre ellos.
Phylliida
5

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 .

Gara Pruesse
fuente
2

Por ejemplo, me pregunto qué pasaría si alguien algún día demostrara P! = NP bajo el supuesto de la segunda ley de la termodinámica.

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):

vzn
fuente