Этот вопрос является продолжением вопроса об алгоритмах ДНК, заданного Аадитой Мехра .
В комментариях Джо Фитцсиммонс сказал, частично:
[T] Радиус системы должен масштабироваться пропорционально массе, чтобы избежать этого. Вычислительная мощность масштабируется максимально линейно по массе. Таким образом, ваше экспоненциальное количество машин имеет экспоненциальный радиус. Поскольку вы не можете передать сигнал быстрее, чем свет, сигнал от одной стороны к другой экспоненциально занимает много времени, чтобы достичь другой стороны, и поэтому, если все механизмы вносят свой вклад в ответ, невозможно решить проблему менее чем экспоненциально время.
Мой вопрос состоит из двух частей.
(1) Каков наилучший способ / способы формализовать утверждение типа «Вычислительная мощность максимально линейно масштабируется в массе»? Действительно ли это утверждение не подлежит обсуждению?
(2) Предположим, что утверждение верно. Даже в этом случае природа могла бы уже выполнить экспоненциальный объем предварительной обработки, которую мы могли бы использовать, например, создание эволюционных систем видения посредством «рандомизации методом грубой силы».
Я слышал и читал довольно много мягких (псевдонаучных) ответов на вопросы такого рода, и я был бы благодарен за любые ответы здесь, но меня больше всего интересует, как (1) и (2) могут быть изменены в TCS строгость.
источник
Ответы:
Заявление, которое я сделал, не было особенно хорошо написано. Я имел в виду комбинацию теоремы Марголуса-Левитина (которая дает минимальное время для перехода между двумя ортогональными состояниями и, следовательно, нижнюю границу времени, необходимого для выполнения ворот) и радиуса Шварцшильда (который дает минимальный радиус система некоторой фиксированной энергии, прежде чем она образует черную дыру). Объединение двух из них приводит к верхней границе числа ворот, которые могут быть выполнены в фиксированной области пространства-времени. Вы можете думать об этом как о максимальном количестве ворот в единицу времени, которое может быть выполнено.
источник