Considere el problema de encontrar el casco convexo para puntos en un plano. No existen algoritmos de tiempo constante para resolverlo.
Ahora digamos que representas los puntos como postes de igual altura que clavas en el suelo. Luego colocas una banda de goma gigante estirada alrededor de ellos y la sueltas. La elasticidad de la goma hará que tome la forma con el menor perímetro posible (abrazará fuertemente a los postes). La forma que toma es el casco convexo de los polos. La cantidad de tiempo que tarda la banda 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 "causando" que el problema se resuelva más rápido ( que cualquier algoritmo conocido.
Digamos que se muestra que el tiempo mínimo para que algún problema se resuelva computacionalmente está acotado por para alguna variable del problema . Tengo curiosidad por saber si se puede violar el límite como consecuencia de que las leyes de la física actúen sobre algo.
La suposición de trabajo actual de la mayoría de los físicos que investigan la complejidad computacional es que el cálculo que se puede lograr en la física clásica es equivalente en potencia, hasta factores polinómicos, con una máquina de Turing clásica, y que el cálculo que se puede lograr en la física cuántica es equivalente, hasta el polinomio factores, con una máquina cuántica de Turing.
Como entrada a la vasta y fascinante literatura sobre este tema, recomiendo:
David Deutsch, Teoría cuántica, el principio de Church-Turing y la computadora cuántica 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 detallada que lo que he mencionado anteriormente, ya que su pregunta es sobre algoritmos de tiempo constante versus lineal. Tal aceleración no contradiría las suposiciones teóricas de complejidad estándar, ya que podría deberse efectivamente a la computación paralela clásica convencional. Sin embargo, en realidad no creo que el tiempo de cálculo para su computadora de banda elástica sea asintóticamente constante. Si imagina que la banda elástica solo se puede estirar alrededor de los postes a una velocidad finita (la velocidad de la luz proporciona un límite superior), mientras más postes tenga, más tiempo le llevará colocar la banda elástica alrededor de ellos. Podría intentar compensar haciendo que las publicaciones sean más pequeñas y más juntas, pero esto también tiene limitaciones: ¡uno no puede hacer que las publicaciones tengan menos de un átomo de espesor! Entonces, en la práctica, su computadora de 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, que esté interesado en el escalado asintótico del tiempo de ejecución en el límite de que el tamaño del problema tiende a infinito, diría que la computadora de banda elástica no logra un tiempo constante.
Por cierto, un ejemplo similar, a saber, una computadora de pompas de jabón para encontrar árboles de expansión mínimos (que es un problema NP-difícil) se analiza en:
Scott Aaronson, Problemas NP-completos y realidad física (2005) https://www.scottaaronson.com/papers/npcomplete.pdf
En cierto sentido, sí, se puede violar el límite, pero no porque se viole, sino porque el algoritmo es completamente diferente. Dejame explicar.
En Matemáticas, los elementos y las reglas se definen según una lógica estricta ya 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 reales y fenómenos a partir de sus similitudes relevantes con elementos matemáticos. En otras palabras, es decir que las ondas en 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 pueda establecer la conexión, puede usar todas las conclusiones lógicas de las matemáticas para seguir estudiando y comprender la naturaleza de una manera 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 relacionas fenómenos con problemas matemáticamente formulados, 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.
Finalmente, 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 hemos encontrado. Pero la naturaleza ya "soluciona" estos y muchos otros problemas a través de mecanismos aún fuera de nuestro alcance.
Sin embargo, podemos y hemos utilizado las "habilidades computacionales" de la naturaleza a nuestro favor, como diferenciar/integrar 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 cosas realmente rápidas, como cómo mantener el equilibrio, y nuestros algoritmos matemáticos para esto todavía están en pasos de bebé.
Entonces, respondiendo a su pregunta, nuestros algoritmos son, en cierto modo, lo mejor que podemos encontrar para resolver un problema que generalmente tiene una contraparte en la naturaleza. Pero los fenómenos naturales no siguen algoritmos matemáticos y no están limitados por esto. La pregunta es entonces, ¿cómo "calcula" la naturaleza? Aún no lo sabemos.
Brandon Enright
curioso
DanielSank