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

Версия 15:49, 20 мая 2020

QSAT — это обобщение SAT, когда можно использовать кванторы существования и всеобщности к каждой переменной.

Если кванторы у всех переменных, то свободных переменных нет, и можно спрашивать — истинна ли формула или нет?

Пример:

Докажите, что QSAT in PSPACE.

@@ Строка 1: / Строка 1: @@
-Маркеева Лариса 973б<br />
+{{:QSAT}}
-Рассмотрим рисунок работы алгоритма для http://discopal.ispras.ru/images/generated/amsmath/f/f1/f1acc7d9b969deeb6e7e279f2ce3f266/amsmath.source1.png: <br />
-http://s019.radikal.ru/i608/1410/56/e876697bff81.jpg <br />
-По этому дереву легко понять, что высказывание http://discopal.ispras.ru/images/generated/amsmath/f/f1/f1acc7d9b969deeb6e7e279f2ce3f266/amsmath.source1.png всегда истинно.
-Теперь посмотрим на то, как строится дерево для решений в QSAT <br />
+Докажите, что [[QSAT]] in [[PSPACE]].
-Этот алгоритм рекурсивно перебирает все варианты. Для хранения результата каждой подзадачи требуется 1 бит информации. <br />
-Количество информации, которую нужно хранить равна глубине дерева. В свою очередь глубина дерева равна количеству переменных. <br />
-Следовательно, QSTAT входит в PSPACE.<br />
+<!--Вообще-то, решения уже есть-->
-[[Категория:На проверку]]
+[[Категория:Решенные задачи]]