ДНК-алгоритмы и NP-полнота

21

Какова связь между алгоритмами ДНК и классами сложности, определенными с помощью машин Тьюринга? Как соотносятся меры сложности, такие как время и пространство, в ДНК-алгоритмах? Могут ли они быть использованы для решения проблем NP-complete, таких как TSP, которые машины фон Неймана не могут реально решить на практике?

Аадита Мехра
источник
2
Я разместил следующий вопрос здесь: cstheory.stackexchange.com/questions/2758/…
Аарон Стерлинг,

Ответы:

31

Soundbite answer: ДНК-вычисления не дают волшебной палочки для решения NP-завершенных задач, хотя некоторые уважаемые исследователи в 1990-е годы думали, что это возможно.

Первый эксперимент по вычислению ДНК был проведен в лаборатории, которую возглавлял известный теоретик чисел Лен Адлеман. Адлеман решил небольшую проблему коммивояжера - хорошо известную проблему, полную NP-задачи, и он и другие некоторое время думали, что метод может расшириться. Адлеман описывает свой подход в этом коротком видео , которое я нахожу захватывающим. Проблема, с которой они столкнулись, заключалась в том, что для решения проблемы TSP скромного размера им потребуется больше ДНК, чем размер Земли. Они нашли способ сэкономить время, увеличив объем параллельной работы, но это не означало, что для решения проблемы TSP потребовалось меньше, чем экспоненциальные ресурсы. Они только сместили экспоненциальную стоимость с количества времени на количество физического материала.

(Возникает дополнительный вопрос: если вам требуется экспоненциальное количество оборудования для решения проблемы, вам автоматически требуется экспоненциальное количество времени или, по крайней мере, предварительная обработка, чтобы построить оборудование в первую очередь? Я оставлю этот вопрос на хотя одна сторона.)

Эта общая проблема - сокращение времени, необходимого для вычислений за счет какого-либо другого ресурса, - многократно проявлялась в моделях вычислений, основанных на биологическом опыте. На странице Википедии о мембранных вычислениях (абстракция биологической клетки) говорится, что определенный тип мембранной системы способен решать NP-полные проблемы за полиномиальное время. Это работает, потому что эта система позволяет создавать экспоненциально много подобъектов внутри общей мембраны за полиномиальное время. Ну ... как экспоненциальное количество сырья поступает из внешнего мира через мембрану с постоянной площадью поверхности? Ответ: это не считается. Они не платят за ресурс, который иначе потребовался бы для вычислений.

Наконец, чтобы ответить Энтони Лабарре, который связался с документом, показывающим, что AHNEPs может решить NP-полные проблемы за полиномиальное время. Есть даже статья, показывающая, что AHNEP могут решать 3SAT в линейномвремя. AHNEP = Приемлемая гибридная сеть эволюционных процессоров. Эволюционный процессор - это модель, вдохновленная ДНК, ядро ​​которой имеет строку, которая на каждом этапе может быть изменена путем замены, удаления или (что важно) вставки. Кроме того, на каждом узле доступно произвольно большое количество строк, и на каждом этапе связи все узлы отправляют все свои правильные строки всем присоединенным узлам. Таким образом, без затрат времени можно передавать экспоненциальные объемы информации, и из-за правила вставки отдельные строки могут становиться все больше в ходе вычислений, поэтому это двойной удар.

Если вас интересуют недавние работы в области биокомпьютеров, сделанные исследователями, которые сосредоточены на практических вычислениях, я могу предложить обзор этой книги, который я недавно написал для SIGACT News, который кратко затрагивает несколько областей.

Аарон Стерлинг
источник
@ Аарон: Спасибо! Теперь я должен пойти и прочитать ваш обзор.
Аадита Мехра
Я не мог бы сказать это лучше сам. Это также верно для множества других биологических методов решения проблем, таких как генетические алгоритмы и сворачивание белка.
user834
6
р>2грамммс2
5
(продолжение) Таким образом, ваше экспоненциальное количество техники имеет экспоненциальный радиус. Поскольку вы не можете передать сигнал быстрее, чем свет, сигнал от одной стороны к другой экспоненциально занимает много времени, чтобы достичь другой стороны, и поэтому, если все механизмы вносят свой вклад в ответ, невозможно решить проблему менее чем экспоненциально время.
Джо Фитцзимонс
@Joe: Спасибо. :-) Было бы хорошо для меня, чтобы процитировать часть ваших комментариев в последующем вопросе? Мне интересны формализмы, которые фиксируют такие утверждения, как «вычислительная мощность масштабируется максимально линейно по массе». Сколько стоит колмогоровская сложность на квадратный дюйм и т. Д.
Аарон Стерлинг,
13

Это очень сильно зависит от вашей модели.

В действительности, вычисления в ДНК следуют (нерелятивистским) физическим законам, и поэтому могут быть смоделированы на квантовом компьютере. Таким образом, лучшее, на что вы можете надеяться, это то, что он может решить проблемы, полные BQP Однако на самом деле это очень маловероятно, чтобы быть правдой (ДНК довольно большая, и поэтому согласованность не является проблемой), и поэтому при моделировании это почти наверняка P. Однако важно отметить, что это эффективность с точки зрения из числа используемых атомов, и, честно говоря, атомы достаточно дешевы, так что это число является астрономическим, делая практическое моделирование пробирки, полной ДНК, далеко за пределами того, что в настоящее время возможно.

В результате многие люди предпочитают работать с моделями, которые аппроксимируют то, что происходит на практике, но ломаются, когда их доводят до крайностей. Одним из примеров этого является абстрактная модель листов, которая оказывается завершенной NEXP (см. Статью Готтесмана и Ирана из FOCS в прошлом году).

Джо Фитцсимонс
источник
Спасибо за умную идею, чтобы рассматривать ДНК как физическую систему! Я собираюсь посмотреть на документ, который вы связали. Еще раз спасибо.
Аадита Мехра
@Aadita: Нет проблем. Надеюсь, это полезно.
Джо Фицсимонс
1
Модель тайла Ван не предназначена для моделирования физической динамики. Когда интерпретируется как инструмент для предсказания будущего состояния физической системы, то, что делает действительный тайлинг Ван, - это предсказание наиболее вероятного состояния системы в термодинамическом равновесии; т.е. самая низкая энергия. Но термодинамика не дает представления о том, сколько времени может занять система, чтобы приблизиться к равновесию; для этого вам нужна кинетика. Многие системы имеют термодинамическое равновесие, которое достигается только после экспоненциального времени. Для «физической вычислительной сложности» используйте кинетику, а не термодинамику; например, модель сборки плитки.
Дэйв Доти
@Dave: Спасибо за информацию. Я должен признать, что я совершенно не осведомлен об этой области и, возможно, очень плохо сформулировал эту часть ответа. Я не собирался утверждать, что это считается моделью динамики.
Джо Фицсимонс
2

Это частичный ответ

Из статьи Википедии, которую вы упомянули, алгоритмы вычисления молекулярной ДНК, которые решают NP-полные задачи, не доказывают, что NP-полные проблемы разрешимы за полиномиальное время на последовательных машинах (допустимо, что на практике это означает полиномиальное время). ДНК-вычисления можно считать формой параллельных вычислений. Наконец, с точки зрения теории вычислимости, ДНК-вычисления не более мощные, чем машины Тьюринга.

Мухаммед Аль-Туркистани
источник
1

Этот документ может быть вам интересен - кстати, я был бы признателен, если бы кто-то смог прояснить шокирующее утверждение, которое составляет его название.

Энтони Лабарре
источник
2
Некоторые проблемы вне PTIME могут быть решены параллельными машинами за полиномиальное время. Это не парадоксально, поскольку PTIME говорит о проблемах, решаемых определенным классом последовательных машин за полиномиальное время.
Чарльз Стюарт
5
Я попытался уточнить в ответе я разместил.
Аарон Стерлинг