|
|
| Строка 1: |
Строка 1: |
| − | == Решение ==
| |
| | | | |
| − | Рассмотрим алгоритм проверки выполнимости формулы из QSAT, а затем рассмотрим количество необходимой ему памяти.
| |
| − |
| |
| − | '''Алгоритм:'''
| |
| − |
| |
| − | на фход получаем формулу длины n, имеющую m переменных.
| |
| − |
| |
| − | 1) привести формулу к виду, в котором все кванторы вынесены перед формулой. Так же заметим, что если какая-то переменная свободна (не под квантором), то выполнимость этой формулы эквивалентна истинности формулы, в которой эта переменная находится под квантором существования.
| |
| − | :Итак, имеем формулу, в которой присутствуют m литералов, никакой из которых не является свободным. Назовем P(x) - часть формулы без предикатов.
| |
| − |
| |
| − | 2) имеем m переменных - число из m битов, проходим его от 0 до 2<sup>m-1</sup> и перебираем все возможные наборы переменных.
| |
| − | :Составляем дерево:
| |
| − | :[[Файл:QSATinPSPACE.png]]
| |
| − | :верхний уровень соответствует изменению первой переменной, второй уровень - второй, и так далее. Начинаем обход дерева снизу: вычисляем значение P(x) для первых двух наборов значений переменных, запоминая вычисленные значения (2 бита - a<sub>1</sub> и b<sub>1</sub>). Это соответствует различным значениям последней переменной при фиксированных остальных. Теперь если на последней переменной присутствует квантор существования - сохраняем только c<sub>1</sub> = a<sub>1</sub> OR b<sub>1</sub>, если всеобщности - c<sub>1</sub> = a<sub>1</sub> AND b<sub>1</sub>. Теперь Аналогично вычисляем значение P(x) на следующих двух наборах значений переменных и сохраняем конъюнкцию или дизъюнкцию их значений в c<sub>2</sub>. Теперь тем же образом в зависимости от квантора на второй переменной сохраняем только конъюнкцию или дизъюнкцию c<sub>1</sub> и c<sub>2</sub> и так далее...
| |
| − | :Если в вершине дерева получим 1 - значит формула выполнима.
| |
| − |
| |
| − | '''Количество используемой памяти:'''
| |
| − | для перебора всех наборов значений переменных - m бит. Для вычисления значения P(x) на фиксированном наборе - не более n бит. При проходе по дереву максимальное количество бит, необходимых для запоминания, равно m.
| |
| − | Таким образом, количество необходимой памяти равно m+n+m < 3n бит.
| |