В апреле 1980 года Journal of the ACM опубликовал статью Дэвида Лихтенштейна и Майкла Сипсера GO Is Polynomial-Space Hard. Результат относился к определению победителя из произвольной позиции на доске n×n.
Авторы свели к го задачу об истинности булевых формул с кванторами, используя промежуточную игру на графе. Тем самым была доказана PSPACE-трудность: общий алгоритмический анализ таких позиций не проще широкого класса задач, допускающих решение с полиномиальным объёмом памяти.
Для истории го это означало появление строгой оценки вычислительной сложности, дополнившей практические трудности программирования. Однако теорема не утверждала невозможность сильной программы. Она не определяла исход игры с пустой доски и не была прямым доказательством сложности фиксированной доски 19×19: сами авторы отдельно разъясняют это ограничение. Предварительная версия результата появилась в техническом отчёте 1978 года; 1980-й — дата развёрнутой журнальной публикации.
Основание материала
Источники и проверка
- Исследование
David Lichtenstein, Michael Sipser: GO Is Polynomial-Space Hard
Journal of the ACM 27 (2), 1980, 393–401; аннотация, введение и формулировка ограничений.
Проверен:
Раскрытие связи
Материал входит в общий проект сайтов о го.
История продолжается.
Другие события в хронике →