Games, Puzzles, and Computation — книга о сложности игр , написанная Робертом Хирном и Эриком Демейном и опубликованная в 2009 году издательством AK Peters . Она является переработанной версией докторской диссертации Хирна, которая была написана под руководством Демейна. [1] [2] Комитет по списку основных библиотек Математической ассоциации Америки рекомендовал ее для включения в библиотеки по математике для студентов старших курсов. [3]
Игры, головоломки и вычисления касаются теории вычислительной сложности решения логических головоломок и принятия оптимальных решений в двух- и многопользовательских комбинаторных играх . Основное внимание уделяется играм и головоломкам, которые были использованы в реальном мире, а не тем, которые были придуманы для чисто математических целей. [2] В этой области обычно такие головоломки и игры, как судоку , час пик , реверси и шахматы (в обобщенных формах с произвольно большими досками), являются вычислительно сложными: судоку является NP-полной , час пик и реверси являются PSPACE-полными , а шахматы являются EXPTIME-полными . Помимо доказательства новых результатов в этом направлении, книга направлена на предоставление унифицированной структуры для доказательства таких результатов с помощью недетерминированной логики ограничений , абстрактной комбинаторной задачи, которая больше напоминает игровой процесс, чем более классические задачи, ранее использовавшиеся для доказательств полноты . [1] [3]
Она разделена на три части. Первая часть касается логики ограничений, [3] [4] , которая включает назначение ориентаций ребрам неориентированного графа таким образом, чтобы каждая вершина имела входящие ребра с достаточно большим общим весом. [1] [3] Вторая часть этой книги применяет логику ограничений в новых доказательствах сложности различных реальных игр и головоломок, [3] [4] показывая, что в каждом случае вершины и ребра экземпляра логики ограничений могут быть закодированы ходами и частями игры. Некоторые из этих доказательств сложности упрощают ранее известные доказательства; около десяти из них являются новыми, включая открытие того, что оптимальная игра в определенных многопользовательских играх может быть неразрешимой проблемой . [1] Третья часть книги содержит сборник известных результатов сложности в игровой сложности, [3] [4] обновляя гораздо более короткий список полных проблем в игровой сложности из книги 1979 года Computers and Intractability . В приложении представлен обзор методов теории сложности вычислений, необходимых в этом исследовании, для читателей, незнакомых с этой областью. [3]
Хотя в первую очередь это исследовательская монография и справочная работа для исследователей в этой области, рецензент Освин Айххольцер рекомендует книгу в целом всем, кто интересуется математикой игр и их сложностью. [2] Лиляна Бабинкостова пишет, что «Игры, головоломки и вычисления» — увлекательное чтение, успешное в своей «цели построения моста между играми и теорией вычислений». [4]
Леон Харклроуд настроен несколько более критически, написав, что книга местами кажется раздутой, [3] а Джозеф О'Рурк жалуется, что ее структура, с множеством страниц абстрактной математики перед тем, как перейти к играм реального мира, не подходит для чтения от корки до корки. [1] Однако и Харклроуд, и О'Рурк сходятся во мнении, что книга хорошо написана и заставляет задуматься. [1] [3]