Оглавление
Лэнс Фортноу. Золотой билет. P, NP и границы возможного
Предисловие
Золотой билет
Задача о разбиении
Немного о руках
P против NP
В поисках билета
Долгая дорога
Решение задачи о разбиении
Глава 2. Совершенный мир
Урбанский алгоритм
Компьютеры – рак – 1: 0
Пост-урбанский бейсбол
Бритва Оккама
Автоматизация творческого процесса
Первоклассный детектив
Обратная сторона медали
С небес на землю
Глава 3. Классы P и NP
Заклятые друзья
Шесть степеней отчуждения
Задача о числе паросочетаний
В поисках клики
Передай скипетр
Раскраска домов
На первый-второй рассчитайсь!
P против NP
За границей королевства
Биология
Физика
Экономика
Математика
Решение головоломки «Путешествие по додекаэдру»
Глава 4. Самые трудные задачи класса NP
Первая NP-полная задача
Двадцать плюс одна
Что в имени?
После Карпа
Доминирующее множество
Разбиение на треугольники
Гигантские судоку
Цепочка из почек
Мастера конспирации
Изоморфизм графов
Простые числа. Разложение на множители
Линейное программирование
Глава 5. Хроника предшествующих событий
На Западе
Алан Тьюринг
Вычислительная сложность
Классы P и NP
На Востоке
Сергей Всеволодович Яблонский
Андрей Николаевич Колмогоров
Леонид Анатольевич Левин
Письмо Гёделя
Правило марсианина
Глава 6. Преодолевая трудности
Полный перебор
Эвристические методы
Иголка в стоге сена
Приближенные методы
Другая задача
Время смириться
Весь боевой арсенал
Глава 7. Как доказать, что P ≠ NP
Парадокс лжеца
Схемы
Как не доказать, что P ≠ NP
Текущее положение дел
Глава 8. Совершенно секретно
Очень краткая история классической криптографии
Современная криптография
Криптография в совершенном мире
Судоку с нулевым разглашением
Криптография в играх
Облако секретных вычислений
В поисках случайности
Проблемы разрастаются
Глава 9. Его величество квант
Квантовый видеорекордер
Квантовая криптография
Квантовая телепортация
Квантовое будущее
Глава 10. Будущее вычислений
Параллельные вычисления
Большие данные
Интернет вещей
На пути научно-технического прогресса
И снова про P и NP
Благодарности
Примечания и список литературы
Отрывок из книги
В Америке почти у каждого второго есть смартфон. Этот маленький компьютер давно обогнал своих более крупных собратьев, которые еще каких-то двадцать лет назад считались очень мощными. Компьютеры снабжают нас информацией о мире и не дают в ней потеряться; позволяют выходить на связь почти из любой точки планеты; справляются с неимоверно сложными вычислительными задачами, будь то составление расписаний для загруженных аэропортов или моделирование космических явлений. Компьютеры распознают наши лица и голоса, регистрируют перемещения, определяют предпочтения и советуют книги, музыку и фильмы… не за горами то время, когда они будут сами управлять автомобилем. Похоже, для них в этом мире нет ничего невозможного?
На самом деле пока они могут не все. Из этой книги вы узнаете о вычислительных задачах, которые мы, вероятно, никогда не научимся быстро решать. Виной тому труднейшая математическая проблема с загадочным названием «P против NP» – главный вопрос теории алгоритмов, а, может, и всей математики или даже всей науки в целом.
.....
Так что же дальше? Похоже, самые большие трудности ждут нас впереди. Как организовать совместную работу нескольких компьютеров над одной задачей? Как проанализировать колоссальные объемы данных, которые мы создаем изо дня в день? Каким станет мир, когда интернет людей превратится в интернет вещей? Чем больше перед нами возникает подобных задач, тем большую значимость приобретает вопрос о равенстве P и NP.
Упомянутые ранее тридцать восемь чисел
.....
