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

Книга «Золотой билет» Лэнса Фортноу представляет собой увлекательное и доступное введение в одну из величайших нерешённых проблем математики и информатики — проблему P против NP. Эта задача, включённая в список «проблем тысячелетия» Математического института Клэя, имеет фундаментальное значение для теории вычислений и определяет границы того, что могут и не могут компьютеры.

Автор прослеживает историю проблемы, начиная с времён холодной войны, и показывает, как она возникает в самых разных областях: экономике, физике, биологии и повседневной жизни. Фортноу объясняет, что класс P включает задачи, которые компьютер может решить «быстро» (за полиномиальное время), а класс NP — задачи, для которых легко проверить правильность предложенного решения. Равенство P = NP означало бы революцию, позволив мгновенно решать сложнейшие задачи оптимизации, от составления расписаний до разработки лекарств. Неравенство же подтвердило бы существование принципиально «трудных» задач, которые никогда не поддадутся быстрому решению.

Книга написана живым языком, без излишнего углубления в формальные математические детали, что делает её понятной для широкого круга читателей — от студентов и специалистов в области computer science до всех, кто интересуется современной наукой и её пределами. Это не только рассказ о сложной математической проблеме, но и размышление о природе вычислений, интеллекта и границ человеческого познания.