Золотой билет. P, NP и границы возможного. Лэнс Фортноу
это чудо природной инженерии функционировать не будет. От головного мозга должны приходить соответствующие инструкции: рука мертвеца не способна двигаться и вообще что-либо делать.
Рука – это «железо», т. е. натуральное аппаратное обеспечение. А значит, для работы ей обязательно нужна программа – сообщение от мозга, объясняющее, как выполнить то или иное задание.
Профессор Йоки Мацуока из Вашингтонского университета – специалист по робототехнике. Под ее руководством группа исследователей разработала так называемую «анатомически правильную» кисть, пальцы которой в точности повторяют движения человеческих. Технически искусственная рука способна творить те же чудеса, что и настоящая, однако на деле под силу ей оказываются лишь самые простые операции. Нелегко создать программу, которая управляла бы всеми функциями кисти; простейшие движения требуют идеальной координации большого числа мышц, и реализующие их алгоритмы далеко не тривиальны.
Впрочем, наш мозг умудряется контролировать руки без особых проблем. По сути мозг представляет собой сверхмощный компьютер, и раз он может объяснить рукам, как завязать шнурки или создать картину, то написать подобную программу теоретически возможно.
Конечно, одно дело знать, что некий алгоритм существует, и совсем другое – найти его. Программы со временем будут становиться все сложнее и сложнее; искусственная рука научится выполнять намного более трудные операции и однажды – как знать! – вполне может даже превзойти человеческую. Очевидно, нас ждет безумно увлекательное путешествие, вот только скорость движения, похоже, будет очень низкой.
Или не очень? Представьте, что для любой поставленной задачи тут же появляется программа со всей необходимой функциональностью. Например, вы загружаете в компьютер ролик, в котором человек завязывает галстук, и через секунду механические руки уже воспроизводят этот процесс. Или подаете на вход полное собрание сочинений Шекспира, а компьютер в ответ сочиняет новую «шекспировскую» пьесу. Представьте: все, что можно описать словами, можно и создать. Реально ли это? Да – но только если P равно NP.
Вот почему проблема равенства P и NP так будоражит умы. Неужели все задачи мы сможем щелкать как орешки? Или над некоторыми все же придется трудиться? Ответа пока нет, хотя на самом деле на «халяву» мало кто надеется. Вряд ли когда-нибудь выяснится, что P = NP; и все же помечтать об идеальном мире бывает очень и очень приятно.
P против NP
Проблема «P против NP» касается не только описанных выше задач, но и тысяч других, схожих с ними по сути. Насколько быстро можно перебрать огромное число потенциальных вариантов? Насколько трудно будет отыскать тот самый золотой билет, т. е. оптимальное решение поставленной задачи?
Впервые проблема равенства классов упоминается еще в 1956 году – в письме, которое один величайший математик XX века, Курт Гёдель, отправил другому величайшему математику XX века, Джону фон Нейману. К сожалению, вплоть до восьмидесятых о