Determinismo y P=NP

Este me ha estado rompiendo el cerebro durante bastante tiempo. Por lo que la física nos dice actualmente, vivimos en un mundo donde las leyes físicas son inductivas pero no deterministas, porque en algún nivel subyacente existe lo que creemos que es la verdadera aleatoriedad.

Así que imaginemos un mundo donde todo es perfectamente determinista, no hay aleatoriedad subyacente. Por lo tanto, cada proceso físico puede resolverse mediante un algoritmo determinista exactamente cada vez. En tal mundo, ¿P = NP? Si podemos concebir tal mundo, ¿P = NP? ¿O los dos conceptos de determinismo en informática y física no están relacionados en absoluto? Tiene que haber al menos alguna conexión. Por favor, no hay respuestas de una sola palabra, quiero una idea aquí.

Respuestas (4)

Las matemáticas abstractas no tienen que estar relacionadas con la física. Hay muchas cosas que los matemáticos consideran rutinariamente (como conjuntos no medibles, etc.) que no pueden existir en el mundo físico.

En particular, las leyes del mundo físico no tienen nada que ver con el problema P=NP.

Para agregar a esto, el no determinismo utilizado en la teoría de la complejidad computacional se define matemáticamente. La cuestión de si la clase P es la misma que la clase NP es matemática. Es decidible solo por consideraciones matemáticas. Un algoritmo determinista para un problema en NP puede tomar un tiempo probablemente exponencial (o puede que no, ¡aún no lo sabemos porque no hay una prueba matemática!).
No estoy seguro de que tu última oración sea correcta; la computabilidad es una idea abstracta, mientras que la computabilidad práctica está determinada por las leyes físicas que conocemos. Si P = NP o no parece decir algo acerca de la realidad física. Considere el poder del cerebro humano: ¿resuelve problemas NP-completos? Simplemente no lo sabemos todavía; si lo hace, eso es bastante interesante. Si no es así, ¿siempre encuentra una manera de "hacer trampa" teniendo en cuenta la información específica del dominio para mover el problema a P? ¿Son todas las preguntas "interesantes" de alguna manera reducibles a menos de NP, o son lo suficientemente pequeñas en tamaño?
@labreuer, estás asumiendo poderes cerebrales humanos que puede que no tenga. Cierto, muchos problemas interesantes, incluidos los que aborda nuestro cerebro, son NP-difíciles, pero ¿quién les dijo que somos buenos para encontrarles soluciones? La mayoría de las veces, una solución aproximada es suficiente para fines prácticos, y muchos problemas NP-difíciles tienen aproximaciones P (aunque no todos las tienen). Además, a efectos prácticos, a veces es suficiente ser "significativamente más correcto que incorrecto", y esto hace que la clase de complejidad BPP sea más relevante que P.
@Michael, muy cierto. Tal vez todos los problemas NP-completos interesantes tengan aproximaciones lo suficientemente buenas una vez que se utiliza todo el conocimiento del dominio. Sin embargo, la afirmación de que la física y la computación están completamente separadas me parece engañosa. Si el futuro trabajo de física puede informar la teoría de la computación, diría que hay algún tipo de conexión. Ofrecí una respuesta a esta pregunta que desarrolla un poco mi posición.
@labreuer: no todos los problemas NP-completos tienen aproximación, que se deriva del teorema PCP. Independientemente, el no determinismo en la teoría de la complejidad no significa exactamente lo mismo que en la filosofía; eso hace que el problema P v. NP sea menos relevante para la física.
@Michael, es por eso que dije "una vez que se utiliza todo el conocimiento del dominio". :-p Tal vez todas las preguntas que necesitamos responder para explorar más a fondo la realidad tienen buenas aproximaciones; sería decepcionante si simplemente nos 'atascáramos' en algún nivel de avance, debido a una mera barrera computacional. En cuanto a la conexión entre la computación y la física, creo que es una pregunta abierta si existe una conexión profunda. Sucede que creo que nuestro mundo es una cosificación de un sistema formal particular. Esto hace que 'lo abstracto' no sea tan distante como algunos pensarían. ¿Quién tiene razón? ¡No estoy seguro de que lo sepamos!

Un universo determinista podría no ser un universo cuántico, en cuyo caso los algoritmos como el algoritmo de Shor serían imposibles; Se desconoce si habrá un método cuántico o poscuántico para resolver problemas NP en tiempo P. Supongamos que hay. Esto no significará que P = NP; El algoritmo de Shor está en la clase de complejidad BQP : tiempo polinomial cuántico de error acotado.

La clase de complejidad NP es un tipo diferente de no determinista que nuestro conocimiento actual de la mecánica cuántica y su naturaleza no determinista. Sabemos esto porque ninguna computadora cuántica conocida puede resolver problemas NP-completos en tiempo polinomial. Esto se debe a que para resolver problemas NP-completos en tiempo P, necesitaría poder generar n – 1 nuevas instancias del programa en cada punto de decisión con n decisiones posibles. No es exactamente "probar todo simultáneamente", pero está cerca. Ninguna computadora cuántica conocida puede "probar todo a la vez"; esto se debe a que los circuitos cuánticos no son 'lo suficientemente potentes'.

Supongamos que encontramos un nuevo tipo de computadora cuántica que puede resolver problemas NP-completos en tiempo P. Si el universo tenía que ser así o no, probablemente será un asunto de filósofos. Pero seguramente puedes ver que en un universo determinista, esa computadora cuántica [probablemente] no estaría disponible. Entonces, si crea un mundo digital poblado por seres conscientes y hace que ese mundo sea determinista, esos seres probablemente no podrán calcular tanto como pueda en un período de tiempo determinado.

Dicho todo esto, podría resultar que las computadoras clásicas se pueden usar para resolver problemas NP en tiempo P, si resulta que P = NP. En ese caso, si el mundo es o no determinista o indeterminista sería completamente irrelevante. En este punto, simplemente no lo sabemos. Si quiere que su mente se vuelva loca con respecto a la computación y la física, vea este manual sobre la computación de agujeros negros y luego diríjase a la discusión de Scott Aaronson sobre las recientes controversias sobre firewalls . "¿Qué es realmente computable en nuestro universo?" es una pregunta fascinante. ¡Quizás haya un vínculo profundo entre la computación y la física!

La cuestión de si P = NP no tiene relación con si los procesos son deterministas no lo son, solo con la cantidad relativa de esfuerzo que pueden tomar los procesos deterministas frente a los no deterministas por pasos para llegar a soluciones a tipos particulares de problemas. El no determinismo considerado siempre se limita a una selección finita y enumerable de alternativas, por lo que para cualquiera de los procesos no deterministas considerados, siempre existe un 'equivalente' determinista (por ejemplo, obtenido probando exhaustivamente todas las alternativas de alguna manera sistemática).

En palabras sencillas, lo que Michael dice es que las cuestiones de las matemáticas (como P=NP) no se relacionan con las propiedades de ningún mundo físico. La física usa y desarrolla las matemáticas, las matemáticas no toman las observaciones o los conocimientos de la física como entrada.

Determinismo y P=NP
RespuestasAquíPolítica de privacidad1y, 0v