Временная и пространственная сложность алгоритмов/Задачи/QSAT in PSPACE — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
|||
| Строка 1: | Строка 1: | ||
| − | + | Маркеева Лариса 973б<br /> | |
| − | + | Рассмотрим рисунок работы алгоритма для 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 /> | |
| − | + | Этот алгоритм рекурсивно перебирает все варианты. Для хранения результата каждой подзадачи требуется 1 бит информации. <br /> | |
| − | [[ | + | Количество информации, которую нужно хранить равна глубине дерева. В свою очередь глубина дерева равна количеству переменных. <br /> |
| − | + | Следовательно, QSTAT входит в PSPACE.<br /> | |
| + | [[Категория:На проверку]] | ||
Версия 10:08, 7 октября 2014
Маркеева Лариса 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.