Esta pregunta es un seguimiento de la pregunta sobre los algoritmos de ADN formulada por Aadita Mehra .
En los comentarios allí, Joe Fitzsimmons dijo, en parte:
[E] l radio del sistema debe escalar proporcionalmente a la masa para evitar esto. El poder computacional se escala a lo sumo linealmente en la masa. Por lo tanto, su cantidad exponencial de maquinaria tiene un radio exponencial. Como no se puede señalizar más rápido que la luz, una señal de un lado a otro tarda exponencialmente mucho tiempo en llegar al otro lado, por lo que si toda la maquinaria contribuye a la respuesta, es imposible resolver el problema en menos de exponencial hora.
Mi pregunta tiene dos partes.
(1) ¿Cuál es la mejor manera / formas de formalizar una declaración como, "El poder computacional se escala a lo sumo linealmente en la masa"? ¿Esta afirmación realmente no es debatible?
(2) Suponga que la afirmación es verdadera. Aun así, ¿podría la naturaleza haber realizado una cantidad exponencial de preprocesamiento que podríamos utilizar, por ejemplo, la creación de sistemas de visión a través de la "aleatorización de fuerza bruta" de la evolución.
He escuchado y leído un buen número de respuestas suaves (pseudocientíficas) a preguntas de este tipo, y agradecería cualquier respuesta aquí, pero estoy más interesado en cómo (1) y (2) pueden ser refundidos en rigor TCS.
fuente
Respuestas:
La declaración que hice no estaba particularmente bien escrita. Me refería a una combinación del teorema de Margolus-Levitin (que da el tiempo mínimo para moverse entre dos estados ortogonales y, por lo tanto, un límite inferior en el tiempo requerido para realizar una puerta) y el radio de Schwarzschild (que da el radio mínimo de un sistema de cierta energía fija antes de que forme un agujero negro). La combinación de ambos lleva a un límite superior en el número de puertas que se pueden realizar en una región fija de espacio-tiempo. Puede pensar en esto como el número máximo de puertas por unidad de tiempo que se puede realizar.
fuente