<<
>>

Примечания и дополнительная литература

PSPACE — всего лишь один класс неразрешимых задач за пределами NP; изуче- нием этой области занимается теория сложности. По теме теории сложности на- писан ряд книг, таких как книги Пападимитриу (Papadimitгiou, 1995) и Сэвиджа (Savage, 1998).

PSPACE-полноту задачи QSAT доказали Стокмейер и Мейер (Stockmeyer, Meyer, 1973).

Некоторые базовые результаты PSPACE-полноты для игр с двумя участниками приведены у Шефера (Schaefer, 1978), а также у Стокмейера и Чандры (Stockmeyer, Chandra, 1979). Задача конкурентного размещения, рассматриваемая здесь, явля- ется адаптированным примером класса задач, изучаемых более общей областью размещения объектов; например, обзорную информацию по этой теме можно найти в книге под редакцией Дрезнера (Drezner, 1995).

Игры для двух игроков постоянно порождали сложные вопросы для ученых в области математики и искусственного интеллекта. Берлекамп, Конуэй и Гай (Berlekamp, Conway, Guy, 1982) и Новаковски (Nowakowski, 1998) обсуждают неко- торые математические вопросы в этой области.

Разработка шахматной программы уровня чемпиона мира в течение 50 лет считалась основной задачей прикладного программирования в области компьютерных интеллектуальных игр. Известно, что Алан Тьюринг работал над алгоритмами для игры в шахматы, как и многие ведущие специалисты в области искусственного интеллекта тех лет. Ньюборн (Newborn, 1996) рассказывает об истории работы над задачей вплоть до момента за год до того, как компьютеру IBM Deep Blue наконец-то удалось победить чемпиона мира.

Построение плана относится к числу фундаментальных задач в области ис- кусственного интеллекта; она занимает видное место в работе Рассела и Норвига (Russell, Norvig, 2002), а также является темой книги Галлаба, Нау и Траверсо (Ghallab, Nau, Traverso, 2004). Обоснование возможности решения задачи по- строения плана с полиномиальным пространством приводится в работе Савича (Savitch, 1970), посвященной вопросам теории сложности, а не задаче построения плана как таковой.

Примечания к упражнениям

Упражнение 1 основано на задаче, о которой мы узнали от Мэверика Ву и Райана Уильямса; упражнение 2 основано на результате Томаса Шефера.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Примечания и дополнительная литература:

  1. Дополнительная литература
  2. Дополнительная литература
  3. Дополнительная литература
  4. Дополнительная литература
  5. Дополнительная литература
  6. Дополнительная литература
  7. Дополнительная литература
  8. Дополнительная литература
  9. Дополнительная литература
  10. Дополнительная литература
  11. Список дополнительной литературы
  12. Дополнительная литература
  13. Дополнительная литература
  14. Дополнительная литература
  15. Дополнительная литература
  16. Дополнительная литература
  17. Дополнительная литература
  18. Дополнительная литература
  19. Дополнительная литература