¿Están las leyes de la física sujetas a los mismos límites de rendimiento que los algoritmos?

Question

Consideremos el problema de encontrar el casco convexo para $n$ puntos en un plano. No hay tiempo constante algoritmos existen para solucionarlo.

Ahora digamos que representas los puntos como postes de igual altura que clavas en el suelo. A continuación, colocas una banda elástica gigante estirada alrededor de ellos y la sueltas. La elasticidad de la banda elástica hará que adopte la forma con el menor perímetro posible (abrazará fuertemente los postes). La forma que adopta es el casco convexo de los polos. El tiempo que tarda la goma elástica en trazar la forma del casco convexo es independiente del número de polos.

Entonces, para este caso, parecería que las leyes de la física están "provocando" que el problema se resuelva más rápido ( $O(1))$ que cualquier algoritmo conocido.

Digamos que se demuestra que el tiempo mínimo para resolver computacionalmente algún problema está acotado por $\mathbb{\Omega }(f(n))$ para alguna variable del problema $n$ . Tengo curiosidad por saber si el límite puede ser violado como consecuencia de que las leyes de la física actúen sobre algo.

Answer 1

La hipótesis de trabajo actual de la mayoría de los físicos que investigan la complejidad computacional es que la computación alcanzable en la física clásica es equivalente en potencia, hasta factores polinómicos, a una máquina de Turing clásica, y que la computación alcanzable en la física cuántica es equivalente, hasta factores polinómicos, a una máquina de Turing cuántica.

Como entrada a la vasta y fascinante literatura sobre este tema, recomiendo:

David Deutsch, La teoría cuántica, el principio de Church-Turing y el ordenador universal ordenador cuántico universal (1985) http://www.daviddeutsch.org.uk/wp-content/deutsch85.pdf

Además, el primer capítulo de mi tesis ofrece un breve resumen y una lista de referencias sobre este tema: https://arxiv.org/abs/0809.2307

Su pregunta es un poco más fina que lo que he referido anteriormente, ya que su pregunta es sobre algoritmos de tiempo constante vs. lineal. Este aumento de velocidad no contradice los supuestos estándar de la teoría de la complejidad, ya que podría deberse a la computación paralela clásica convencional. Sin embargo, en realidad no creo que el tiempo de cálculo de tu ordenador con banda elástica sea asintóticamente constante. Si imaginas que la banda elástica sólo puede estirarse alrededor de los postes a una velocidad finita (la velocidad de la luz proporciona un límite superior), entonces cuantos más postes tengas, más tiempo te llevará poner la banda elástica alrededor de ellos. Se podría intentar compensar haciendo los postes más pequeños y más juntos, pero esto también tiene sus limitaciones: ¡no se puede hacer que los postes tengan menos de un átomo de grosor! Así que, en la práctica, tu ordenador con banda elástica podría lograr un tiempo de ejecución aproximadamente lineal para instancias de problemas de tamaño razonable. Sin embargo, un teórico de la complejidad, interesado en la escala asintótica del tiempo de ejecución en el límite en que el tamaño del problema llega al infinito, diría que el ordenador de la banda elástica no consigue un tiempo constante.

Por cierto, un ejemplo similar, a saber, un ordenador de burbujas de jabón para encontrar árboles de extensión mínima (que es un problema NP-duro) se analiza en:

Scott Aaronson, NP-complete problems and physical reality (2005) https://www.scottaaronson.com/papers/npcomplete.pdf

Answer 2

En cierto sentido, sí se puede violar el límite, pero no porque se viole, sino porque el algoritmo es completamente diferente. Me explico.

En las matemáticas, los elementos y las reglas se definen según una lógica estricta y, a partir de ellos, se extraen conclusiones siguiendo esta lógica metódica y unívoca. Es un hito del pensamiento humano.

Esto permite "matematizar" la naturaleza (aunque históricamente la naturaleza y los problemas prácticos han impulsado elementos matemáticos abstractos). Es decir, establecer una correspondencia entre entidades y fenómenos reales a partir de sus similitudes relevantes con elementos de la matemática. En otras palabras, es decir que las ondas de una libra de una piedra lanzada son círculos, que las órbitas son elipses o que los estados cuánticos corresponden a una función de onda.

Una vez que se puede establecer la conexión, se pueden utilizar todas las conclusiones lógicas de las matemáticas para seguir estudiando y comprender la naturaleza de una forma mucho más compleja de lo que permite la simple observación, y formular el comportamiento natural en forma de leyes y relaciones matemáticas.

También se corresponden fenómenos con problemas formulados matemáticamente, como establecer que la cantidad de carga dentro de una superficie cerrada es proporcional a la integral de E a través de ella, o que la forma de una gota es la que minimiza su energía superficial.

Por último, un algoritmo sería el método estructurado para resolver un problema matemático, un conjunto de instrucciones para encontrar una solución a una pregunta formulada en términos matemáticos.

Dicho esto, nuestros algoritmos reflejan nuestra comprensión de la naturaleza a través de la mejor lógica que se nos ha ocurrido. Pero la naturaleza ya "resuelve" estos y otros muchos problemas a través de mecanismos que aún están fuera de nuestro alcance.

Sin embargo, podemos y hemos utilizado las "habilidades computacionales" de la naturaleza en nuestro beneficio, como diferenciación/integración de funciones complejas instantáneamente, o el uso de PNN para resolver problemas que serían muy difíciles incluso de formular matemáticamente. Los seres humanos calculan en situaciones complejas con gran rapidez cosas como el mantenimiento del equilibrio, y nuestros algoritmos matemáticos para ello están todavía en fase de aprendizaje.

Así que, respondiendo a tu pregunta, nuestros algoritmos son, en cierto modo, lo mejor que se nos ocurre para resolver un problema que, por lo general, tiene una contrapartida en la naturaleza. Pero los fenómenos naturales no siguen algoritmos matemáticos y no están limitados por ello. La pregunta es, entonces, ¿cómo "computa" la naturaleza? Todavía no lo sabemos.