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

Материал из DISCOPAL
Перейти к: навигация, поиск
(Массовая правка: добавление Категория:Теоретические задачи)
 
(не показано 16 промежуточных версий этого же участника)
Строка 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 />
+
<!--Вообще-то, решения уже есть-->
[[Категория:На проверку]]
+
 
 +
[[Категория:Решенные задачи]]
 +
[[Категория:Теоретические задачи]]

Текущая версия на 06:50, 4 мая 2023

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

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

Пример:

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