Первая технология. Данный материал основан на сообщениии о ДНК компьютерах из раздела events

Трудность задачи в комбинаторике определяется временем, необходимым для её решения на детерминированной и недетерминированной машинах Тьюринга (ДМТ и НДМТ). Эти воображаемые устройства принципиально отличаются друг от друга. ДМТ исполняет детерминированные алгоритмы, где все операции выполняются последовательно и предопределены заранее. Примером может служить сложение векторов. НДМТ, напротив, исполняет недетерминированные алгоритмы. В них имеются узловые точки, где происходит выбор направления дальнейших действий из некоторого множества вариантов. Рассматриваемая в теории сложности НДМТ может создавать в каждой точке новые копии самой себя в количестве = числу ветвлений алгоритма. Дальнейшие вычисления производятся этими копиями параллельно и возможны ещё и ещё деления копий копии и т.д. На основе того, известен или нет для данной задачи эффективный алгоритм для ДМТ и НДМТ, выделяют классы сложности P, NP, NP-Complate (NPC). К типу P (polynomial) относятся задачи, решаемые на ДМТ за полиномиальное время, т.е. за время порядка n в степени s, где n - определяет масштаб задачи (скажем длину ключа шифрования или количество вершин графа), а s - некоторое число, характеризующее алгоритм. К NP (nodetermministic polynomial) относятся задачи, которые решаются за экспонециальное время на ДМТ (т.е. за время порядка s в степени n) и за полиномиальное время на ДМТ. Такой например является задача о разложении числа на простые множители, на трудности которой базируется алгоритм RSA. Естественно, что любая задача, относящаяся к P, относится и к NP, ведь каждый детерминированный алгоритм можно рассматривать и как не детерминированный, но с одним вариантом выбора в том или ином узле. Поэтому НДМТ может решить за полиномиальное время задачу, на которую ДМТ потребуется экспоненциальное время. Математически доказано также, что множество NP\P не пустое, что существует хотя бы одна проблема, входящая в NP и не входящая в P. Математик Стивен Кук в 1971 г. показал, что существует подмножество задач, обладающих интересным свойством, что если находится детерминированный полиномиальный алгоритм для одной из них, то должны существовать алгоритмы для всех задач NP, то есть P = NP. Кук назвал этот класс NP-Complate (NPC). Все задачи, входящие в этот класс эквивалентны с вычислительной точки зрения, и можно показать, что любая задача из NP сводится к NPC проблеме за полиномиальное время. NPC задачи считаются наиболее сложными в NP и математики верят, что для этих задач полиномиальных детерминированных алгоритмов вообще не существует (ну и не надо). К NPC задачам относятся, например, проблемы нахождения Гамельтонова пути в графе (на этом алгоритме основано много различных криптостойких шифров). Суть проблемы отыскания Гамельтонова пути: Имеется граф с n вершинами, срединные рёбрами. Нужно найти путь из одной заданной вершины в другую (или из любой вершины в другую, отличную вершину, обойдя все остальные), проходя все остальные вершины ТОЛЬКО ОДИН РАЗ или доказать отсутствие такого пути. Задача дискретная, решать её можно только перебором, она имеет прикладное значение (к ней можно свести задачу разложения числа на множители) и все существующие для неё детерминированные алгоритмы имеют экспоненциальное время исполнения. Практическая важность проблем NP в том, что на детерминированной машине они перестают быть физически решаемыми при n гораздо меньшем, чем у задач класса P. Этот принцип широко используется в современной криптографии. Между тем новые типы вычислительных машин - квантовые и молекулярные компьютеры - являются ограниченными реализациями НДМТ и теоретически способны решать такие NP задачи за полиномиальное время, что, несомненно очень сильно уменьшает необходимое время на решение таких задач.
Вот мы и подобрались к существу применения био-ДНК-компьютеров. Существует три способа реализации таких био-компьютеров. Каждый хорош и совершенен по своему. У каждого есть свои трудности построения, обслуживания и надёжности. Есть свои плюсы и минусы. Вот об этом мы сейчас и поговорим.