Перейти к содержанию

Новости го · хроника событий, люди и первоисточники

ГО-ДАЙДЖЕСТВесь мир го. История продолжается.
Материалов на сайте: 1698Историческая хроника 400–2026
Рубрики
Найти по теме
Страны и регионы

Весь архив: статьи и биографии. Материал может относиться к нескольким странам.

Выбрать другую страну
Исторические периоды
■ Популярные темы архиваЧемпионатыЛенинградКонгрессы
Архивная хроникаКлубы и сообщество

Лихтенштейн и Сипсер доказали сложность обобщённого го

Работа Journal of the ACM формально связала анализ позиций на доске произвольного размера с PSPACE-трудными задачами.

1980ВРЕМЯ СОБЫТИЯ

В апреле 1980 года Journal of the ACM опубликовал статью Дэвида Лихтенштейна и Майкла Сипсера GO Is Polynomial-Space Hard. Результат относился к определению победителя из произвольной позиции на доске n×n.

Авторы свели к го задачу об истинности булевых формул с кванторами, используя промежуточную игру на графе. Тем самым была доказана PSPACE-трудность: общий алгоритмический анализ таких позиций не проще широкого класса задач, допускающих решение с полиномиальным объёмом памяти.

Для истории го это означало появление строгой оценки вычислительной сложности, дополнившей практические трудности программирования. Однако теорема не утверждала невозможность сильной программы. Она не определяла исход игры с пустой доски и не была прямым доказательством сложности фиксированной доски 19×19: сами авторы отдельно разъясняют это ограничение. Предварительная версия результата появилась в техническом отчёте 1978 года; 1980-й — дата развёрнутой журнальной публикации.

Основание материала

Источники и проверка

  1. Исследование

    David Lichtenstein, Michael Sipser: GO Is Polynomial-Space Hard

    Journal of the ACM 27 (2), 1980, 393–401; аннотация, введение и формулировка ограничений.

    Проверен:

Раскрытие связи

Материал входит в общий проект сайтов о го.

История продолжается.

Другие события в хронике →