Игры, головоломки и вычисления
 Обложка книги, первое издание | |
| Автор | Роберт А. Хирн, Эрик Д. Демейн |
|---|---|
| Язык | Английский |
| Издатель | АК Петерс |
Дата публикации | 1 июля 2009 г. |
| ISBN | 978-1568813226 |
«Игры, головоломки и вычисления» — книга о сложности игр , написанная Робертом Хирном и Эриком Демейном и опубликованная в 2009 году издательством AK Peters . Он составлен на основе докторской диссертации Хирн, которую курировал Демейн. [1] [2] Комитет по основным спискам библиотек Американской математической ассоциации рекомендовал его для включения в библиотеки по математике для студентов. [3]
Темы [ править ]
Игры, головоломки и вычисления касаются теории вычислительной сложности решения логических головоломок для двух и нескольких игроков и принятия оптимальных решений в комбинаторных играх . Основное внимание уделяется играм и головоломкам, которые использовались в реальной жизни, а не тем, которые были изобретены для чисто математических целей. [2] В этой области головоломки и игры, такие как судоку , «Час пик» , реверси и шахматы (в обобщенных формах с произвольно большими досками), обычно являются вычислительно сложными: судоку является NP-полным , «Час пик» и реверси являются PSPACE-полными , и шахматы EXPTIME-полны . Помимо доказательства новых результатов в этом направлении, книга призвана предоставить объединяющую основу для доказательства таких результатов посредством использования недетерминированной логики ограничений — абстрактной комбинаторной задачи, которая больше напоминает игру, чем более классические задачи, ранее использовавшиеся для доказательства полноты . [1] [3]
Он разделен на три части. Первая часть касается логики ограничений, [3] [4] который включает в себя назначение ориентаций ребрам неориентированного графа так, чтобы каждая вершина имела входящие ребра с достаточно большим общим весом. [1] [3] Во второй части этой книги логика ограничений применяется в новых доказательствах сложности различных реальных игр и головоломок. [3] [4] показывая, что в каждом случае вершины и ребра экземпляра логики ограничений могут быть закодированы ходами и частями игры. Некоторые из этих доказательств твердости упрощают ранее известные доказательства; около десяти из них являются новыми, включая открытие того, что оптимальная игра в некоторых многопользовательских играх может быть неразрешимой проблемой . [1] Третья часть книги представляет собой сборник известных результатов по сложности игры. [3] [4] обновление гораздо более короткого списка полных проблем сложности игр из книги 1979 года « Компьютеры и трудноразрешимость» . Для читателей, незнакомых с этой областью, в приложении представлен обзор методов теории сложности вычислений, необходимых в этом исследовании. [3]
и Аудитория прием
Хотя это в первую очередь исследовательская монография и справочный материал для исследователей в этой области, рецензент Освин Айххольцер рекомендует книгу в более широком смысле всем, кто интересуется математикой игр и их сложностью. [2] Лиляна Бабинкостова пишет, что «Игры, головоломки и вычисления» — это приятное чтение, успешно достигающее своей «цели построить мост между играми и теорией вычислений». [4]
Леон Харклроуд настроен несколько более критично, написав, что книга местами кажется мягкой, [3] а Джозеф О'Рурк жалуется, что его организация, состоящая из многих страниц абстрактной математики, прежде чем перейти к реальным играм, не позволяет читать ее от корки до корки. [1] Однако и Харклроуд, и О'Рурк согласны с тем, что книга хорошо написана и заставляет задуматься. [1] [3]
Ссылки [ править ]
- ^ Jump up to: Перейти обратно: а б с д и ж О'Рурк, Джозеф (декабрь 2010 г.), «Обзор игр, головоломок и вычислений », SIAM Review , 52 (4): 782–785, JSTOR 41062032
- ^ Jump up to: Перейти обратно: а б с Айххольцер О. (декабрь 2012 г.), «Обзор игр, головоломок и вычислений » (PDF) , International Mathematical News (на немецком языке), 66 (221): 58
- ^ Jump up to: Перейти обратно: а б с д и ж г час я Харклроуд, Леон (декабрь 2009 г.), «Обзор игр, головоломок и вычислений » , MAA Reviews , Математическая ассоциация Америки
- ^ Jump up to: Перейти обратно: а б с д Бабинкостова, Лиляна (декабрь 2009 г.), «Обзор игр, головоломок и вычислений », zbMATH , Zbl 1175.91035