Временная и пространственная сложность алгоритмов/Задачи/QSAT in PSPACE

Ссылки сюда (9) →

Короткая ссылка: QSAT in PSPACE

Маркеева Лариса 973б
Рассмотрим рисунок работы алгоритма для http://discopal.ispras.ru/images/generated/amsmath/f/f1/f1acc7d9b969deeb6e7e279f2ce3f266/amsmath.source1.png:
http://s019.radikal.ru/i608/1410/56/e876697bff81.jpg
По этому дереву легко понять, что высказывание http://discopal.ispras.ru/images/generated/amsmath/f/f1/f1acc7d9b969deeb6e7e279f2ce3f266/amsmath.source1.png всегда истинно.

Теперь посмотрим на то, как строится дерево для решений в QSAT
Этот алгоритм рекурсивно перебирает все варианты. Для хранения результата каждой подзадачи требуется 1 бит информации.
Количество информации, которую нужно хранить равна глубине дерева. В свою очередь глубина дерева равна количеству переменных.
Следовательно, QSTAT входит в PSPACE.

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.