Esta pergunta é uma continuação da pergunta sobre algoritmos de DNA feita por Aadita Mehra .
Nos comentários, Joe Fitzsimmons disse, em parte:
[O] raio do sistema deve escalar proporcionalmente à massa para evitar isso. A potência computacional escala no máximo linearmente na massa. Assim, sua quantidade exponencial de maquinaria tem um raio exponencial. Como você não pode sinalizar mais rápido que a luz, um sinal de um lado para outro leva um tempo exponencialmente longo para chegar ao outro lado; portanto, se todas as máquinas contribuírem para a resposta, é impossível resolver o problema em menos do que exponencial Tempo.
Minha pergunta tem duas partes.
(1) Qual é a melhor maneira / formal de formalizar uma afirmação como "O poder computacional escala no máximo linearmente na massa"? Esta afirmação não está realmente em debate?
(2) Suponha que a afirmação seja verdadeira. Mesmo assim, a natureza já poderia ter realizado uma quantidade exponencial de pré-processamento, da qual poderíamos usar, por exemplo, a criação de sistemas de visão pela evolução por meio da "randomização da força bruta".
Ouvi e li um bom número de respostas suaves (pseudocientíficas) para perguntas desse tipo e ficaria grato por todas as respostas aqui, mas estou mais interessado em como (1) e (2) podem ser reformuladas no rigor do TCS.
fonte
Respostas:
A afirmação que fiz não foi particularmente bem escrita. Eu estava me referindo a uma combinação do teorema de Margolus-Levitin (que dá o tempo mínimo para se mover entre dois estados ortogonais e, portanto, um limite mais baixo para o tempo necessário para executar uma porta) e o raio de Schwarzschild (que fornece o raio mínimo de um sistema de energia fixa antes de formar um buraco negro). A combinação dos dois leva a um limite superior do número de portas que podem ser executadas em uma região fixa do espaço-tempo. Você pode pensar nisso como o número máximo de portas por unidade de tempo que pode ser executado.
fonte