«Золотой билет» – великолепное введение в P/NP-проблему, в котором описаны история этой задачи и ее влияние на нашу жизнь. В этой информативной и занимательной книге Лэнс Фортноу прослеживает работу, которая велась над задачей во времена холодной войны по обе стороны «железного занавеса», и приводит примеры ее возникновения во множестве дисциплин, включая экономику, физику и биологию.
Для студентов и специалистов в области теории вычислений, всех, интересующихся современными проблемами в математике.
В формате pdf A4 сохранен издательский дизайн.
Copyright © 2013 by Princeton University Press Все права защищены. Никакая часть этой книги не может быть воспроизведена или передана в любой форме или любыми средствами, электронными или механическими, включая фотокопирование, запись или использование средств хранения и поиска информации, без письменного разрешения Издателя.
© Лаборатория знаний, 2016
Предисловие
В Америке почти у каждого второго есть смартфон. Этот маленький компьютер давно обогнал своих более крупных собратьев, которые еще каких-то двадцать лет назад считались очень мощными. Компьютеры снабжают нас информацией о мире и не дают в ней потеряться; позволяют выходить на связь почти из любой точки планеты; справляются с неимоверно сложными вычислительными задачами, будь то составление расписаний для загруженных аэропортов или моделирование космических явлений. Компьютеры распознают наши лица и голоса, регистрируют перемещения, определяют предпочтения и советуют книги, музыку и фильмы… не за горами то время, когда они будут сами управлять автомобилем. Похоже, для них в этом мире нет ничего невозможного?
На самом деле пока они могут не все. Из этой книги вы узнаете о вычислительных задачах, которые мы, вероятно, никогда не научимся быстро решать. Виной тому труднейшая математическая проблема с загадочным названием «P против NP» – главный вопрос теории алгоритмов, а, может, и всей математики или даже всей науки в целом.
Математический институт Клэя присвоил ей статус задачи тысячелетия. Всего таких задач семь, и за решение каждой из них институт предлагает приз в миллион долларов. Однако за вопросом «P против NP» стоит нечто большее.
P – это класс задач, которые на компьютере решаются относительно быстро. NP – задачи, для которых мы хотим найти оптимальное решение. Равенство P и NP означает, что любую поставленную задачу можно быстро решить. В этом случае наша жизнь сразу перейдет на совершенно новый уровень; медицина, наука, индустрия развлечений шагнут далеко вперед, и почти любой процесс можно будет автоматизировать.
Неравенство P и NP, в свою очередь, означает, что для некоторых задач быстрое решение не найдется никогда, и отнимает у нас всякую надежду на создание универсального алгоритма. Впрочем, это еще не повод опускать руки: для борьбы с «крепкими орешками» разрабатываются специальные методы, которые во многих случаях работают вполне приемлемо. По крайней мере мы знаем, какие техники здесь точно не годятся, и это знание помогает понять, в каком направлении двигаться.
