https://discopal.ispras.ru/index.php?action=history&feed=atom&title=%D0%9E%D0%B1%D1%81%D1%83%D0%B6%D0%B4%D0%B5%D0%BD%D0%B8%D0%B5%3A%D0%92%D1%80%D0%B5%D0%BC%D0%B5%D0%BD%D0%BD%D0%B0%D1%8F_%D0%B8_%D0%BF%D1%80%D0%BE%D1%81%D1%82%D1%80%D0%B0%D0%BD%D1%81%D1%82%D0%B2%D0%B5%D0%BD%D0%BD%D0%B0%D1%8F_%D1%81%D0%BB%D0%BE%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D1%8C_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%BE%D0%B2%2F%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B8%2FQSAT_in_PSPACEОбсуждение:Временная и пространственная сложность алгоритмов/Задачи/QSAT in PSPACE - История изменений2026-04-14T12:48:51ZИстория изменений этой страницы в викиMediaWiki 1.26.4https://discopal.ispras.ru/index.php?title=%D0%9E%D0%B1%D1%81%D1%83%D0%B6%D0%B4%D0%B5%D0%BD%D0%B8%D0%B5:%D0%92%D1%80%D0%B5%D0%BC%D0%B5%D0%BD%D0%BD%D0%B0%D1%8F_%D0%B8_%D0%BF%D1%80%D0%BE%D1%81%D1%82%D1%80%D0%B0%D0%BD%D1%81%D1%82%D0%B2%D0%B5%D0%BD%D0%BD%D0%B0%D1%8F_%D1%81%D0%BB%D0%BE%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D1%8C_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%BE%D0%B2/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B8/QSAT_in_PSPACE&diff=498&oldid=prevStasFomin: Удалено содержимое страницы2011-06-14T21:46:45Z<p>Удалено содержимое страницы</p>
<table class='diff diff-contentalign-left'>
<col class='diff-marker' />
<col class='diff-content' />
<col class='diff-marker' />
<col class='diff-content' />
<tr style='vertical-align: top;' lang='ru'>
<td colspan='2' style="background-color: white; color:black; text-align: center;">← Предыдущая</td>
<td colspan='2' style="background-color: white; color:black; text-align: center;">Версия 21:46, 14 июня 2011</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l1" >Строка 1:</td>
<td colspan="2" class="diff-lineno">Строка 1:</td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;">== Решение ==</del></div></td><td colspan="2"> </td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;">Рассмотрим алгоритм проверки выполнимости формулы из QSAT, а затем рассмотрим количество необходимой ему памяти.</del></div></td><td colspan="2"> </td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;"></del></div></td><td colspan="2"> </td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;">'''Алгоритм:'''</del></div></td><td colspan="2"> </td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;"></del></div></td><td colspan="2"> </td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;">на фход получаем формулу длины n, имеющую m переменных.</del></div></td><td colspan="2"> </td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;"></del></div></td><td colspan="2"> </td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;">1) привести формулу к виду, в котором все кванторы вынесены перед формулой. Так же заметим, что если какая-то переменная свободна (не под квантором), то выполнимость этой формулы эквивалентна истинности формулы, в которой эта переменная находится под квантором существования.</del></div></td><td colspan="2"> </td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;">:Итак, имеем формулу, в которой присутствуют m литералов, никакой из которых не является свободным. Назовем P(x) - часть формулы без предикатов.</del></div></td><td colspan="2"> </td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;"></del></div></td><td colspan="2"> </td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;">2) имеем m переменных - число из m битов, проходим его от 0 до 2<sup>m-1</sup> и перебираем все возможные наборы переменных. </del></div></td><td colspan="2"> </td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;">:Составляем дерево:</del></div></td><td colspan="2"> </td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;">:[[Файл:QSATinPSPACE.png]]</del></div></td><td colspan="2"> </td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;">:верхний уровень соответствует изменению первой переменной, второй уровень - второй, и так далее. Начинаем обход дерева снизу: вычисляем значение 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> и так далее...</del></div></td><td colspan="2"> </td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;">:Если в вершине дерева получим 1 - значит формула выполнима.</del></div></td><td colspan="2"> </td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;"></del></div></td><td colspan="2"> </td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;">'''Количество используемой памяти:'''</del></div></td><td colspan="2"> </td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;">для перебора всех наборов значений переменных - m бит. Для вычисления значения P(x) на фиксированном наборе - не более n бит. При проходе по дереву максимальное количество бит, необходимых для запоминания, равно m.</del></div></td><td colspan="2"> </td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;">Таким образом, количество необходимой памяти равно m+n+m < 3n бит.</del></div></td><td colspan="2"> </td></tr>
</table>StasFominhttps://discopal.ispras.ru/index.php?title=%D0%9E%D0%B1%D1%81%D1%83%D0%B6%D0%B4%D0%B5%D0%BD%D0%B8%D0%B5:%D0%92%D1%80%D0%B5%D0%BC%D0%B5%D0%BD%D0%BD%D0%B0%D1%8F_%D0%B8_%D0%BF%D1%80%D0%BE%D1%81%D1%82%D1%80%D0%B0%D0%BD%D1%81%D1%82%D0%B2%D0%B5%D0%BD%D0%BD%D0%B0%D1%8F_%D1%81%D0%BB%D0%BE%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D1%8C_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%BE%D0%B2/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B8/QSAT_in_PSPACE&diff=497&oldid=prevFlid: Решение2011-06-13T23:50:56Z<p>Решение</p>
<p><b>Новая страница</b></p><div>== Решение ==<br />
<br />
Рассмотрим алгоритм проверки выполнимости формулы из QSAT, а затем рассмотрим количество необходимой ему памяти.<br />
<br />
'''Алгоритм:'''<br />
<br />
на фход получаем формулу длины n, имеющую m переменных.<br />
<br />
1) привести формулу к виду, в котором все кванторы вынесены перед формулой. Так же заметим, что если какая-то переменная свободна (не под квантором), то выполнимость этой формулы эквивалентна истинности формулы, в которой эта переменная находится под квантором существования.<br />
:Итак, имеем формулу, в которой присутствуют m литералов, никакой из которых не является свободным. Назовем P(x) - часть формулы без предикатов.<br />
<br />
2) имеем m переменных - число из m битов, проходим его от 0 до 2<sup>m-1</sup> и перебираем все возможные наборы переменных. <br />
:Составляем дерево:<br />
:[[Файл:QSATinPSPACE.png]]<br />
:верхний уровень соответствует изменению первой переменной, второй уровень - второй, и так далее. Начинаем обход дерева снизу: вычисляем значение 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> и так далее...<br />
:Если в вершине дерева получим 1 - значит формула выполнима.<br />
<br />
'''Количество используемой памяти:'''<br />
для перебора всех наборов значений переменных - m бит. Для вычисления значения P(x) на фиксированном наборе - не более n бит. При проходе по дереву максимальное количество бит, необходимых для запоминания, равно m.<br />
Таким образом, количество необходимой памяти равно m+n+m < 3n бит.</div>Flid