Золотой билет. P, NP и границы возможного. Лэнс Фортноу

Чтение книги онлайн.

СКАЧАТЬ а могут выкрутить запястья. Могут погладить с нежностью или больно ударить. Они общаются языком жестов, пишут слова на бумаге, набирают текст на компьютере. Выполняют ювелирную работу часового мастера и справляются с бензопилой. Руки гениев создают великие картины, симфонии, поэмы… Вероятно, все, чего мы достигли, стало возможным именно благодаря рукам.

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

      Рука – это «железо», т. е. натуральное аппаратное обеспечение. А значит, для работы ей обязательно нужна программа – сообщение от мозга, объясняющее, как выполнить то или иное задание.

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

      Впрочем, наш мозг умудряется контролировать руки без особых проблем. По сути мозг представляет собой сверхмощный компьютер, и раз он может объяснить рукам, как завязать шнурки или создать картину, то написать подобную программу теоретически возможно.

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

      Или не очень? Представьте, что для любой поставленной задачи тут же появляется программа со всей необходимой функциональностью. Например, вы загружаете в компьютер ролик, в котором человек завязывает галстук, и через секунду механические руки уже воспроизводят этот процесс. Или подаете на вход полное собрание сочинений Шекспира, а компьютер в ответ сочиняет новую «шекспировскую» пьесу. Представьте: все, что можно описать словами, можно и создать. Реально ли это? Да – но только если P равно NP.

      Вот почему проблема равенства P и NP так будоражит умы. Неужели все задачи мы сможем щелкать как орешки? Или над некоторыми все же придется трудиться? Ответа пока нет, хотя на самом деле на «халяву» мало кто надеется. Вряд ли когда-нибудь выяснится, что P = NP; и все же помечтать об идеальном мире бывает очень и очень приятно.

      P против NP

      Проблема СКАЧАТЬ