Читать «Золотой билет» онлайн - страница 32

Последовательности ДНК содержат закодированную информацию о последовательностях матричных РНК, а те, в свою очередь, хранят информацию о синтезе белков. Белки – или, иначе, протеины – играют ключевую роль в работе клеток, формирующих любой живой организм. Для выполнения своих функций протеин должен особым образом свернуться, т. е. принять определенную пространственную форму. Сложный механизм сворачивания биологами пока не разгадан; известно только, что процессом командуют матричные РНК. Решение проблемы равенства P и NP помогло бы продвинуться на пути понимания этого механизма и, как следствие, – лечения и предотвращения болезней.

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

Физика

К классу NP принадлежит и проблема поиска состояния минимальной энергии физической системы – например, множества взаимодействующих магнитных частиц или скопления мыльных пузырей. Эффективно находить такие состояния мы пока не умеем. Но разве это не то же самое, что и состояние равновесия? Нет – потому что в состоянии равновесия энергия физической системы не обязательно падает до минимума.

Рис. 3.17. Простейшая физическая система

Рассмотрим простейшую физическую систему: шарик на неровной поверхности (рис. 3.17). При x = 3,0 уровень потенциальной энергии шарика минимален, а при x = 1,0 – нет, хотя шарик будет оставаться в этой точке до тех пор, пока его не толкнут. Таким образом, состояние покоя еще не гарантирует минимального уровня энергии. Поиск состояния минимальной энергии для сложных физических систем – задача чрезвычайно трудная, с которой подчас не справляются не только компьютеры, но и сами физические системы.

С некоторыми особо трудоемкими NP-задачами можно бороться при помощи квантовой механики; подробнее об этом вы узнаете в девятой главе.

Экономика

Менеджер хедж-фонда ищет наилучшую форму помещения капитала. Покупатель в супермаркете старается уложиться в бюджет. Оба сталкиваются с труднейшей вычислительной задачей из класса NP, решить которую получается далеко не всегда, и часто выбирают совсем не оптимальную стратегию. Каким образом отсутствие эффективных с вычислительной точки зрения алгоритмов в различных сферах рынка сказывается на экономике и на жизни общества в целом? Прекрасный вопрос; к сожалению, достойного ответа на него не может дать никто.

В книге «Игры разума» и в одноименном фильме описывается жизнь известного экономиста Джона Нэша. Нэш доказал, что в любом процессе стратегического взаимодействия нескольких сторон, или игроков, существует состояние равновесия, при котором стратегия каждого игрока такова, что он не выиграет от ее изменения в одностороннем порядке. За свою работу ученый спустя несколько десятилетий получил Нобелевскую премию. Доказательство Нэша не дает нам алгоритм поиска оптимальных стратегий; впрочем, позже выяснилось, что эта поисковая задача обладает огромной вычислительной сложностью. Маловероятно, что различные сферы рынка сами, естественным образом, смогут достичь состояния равновесия; по всей видимости, они так и будут непрерывно перетекать из одного состояния в другое, поскольку люди постоянно меняют стратегии в стремлении добиться наилучших результатов.