PSPACE
Для начала рассмотрим отношение PSPACE к классам задач, которые рас- сматривались выше. Прежде всего, за полиномиальное время алгоритм может потреблять не более чем полиномиальное пространство; итак, можно утверждать:
(9.1) P С PSPACE
Однако множество PSPACE намного шире. Например, рассмотрим алгоритм, который просто считает от 0 до 2й - 1 в двоичной системе. Он просто реализует w-разрядный счетчик, который работает по тому же принципу, что и одометр в ав- томобиле. Таким образом, алгоритм выполняется за экспоненциальное время, по- сле чего останавливается; при этом он использует полиномиальное пространство. И хотя этот алгоритм не делает ничего особенно интересного, он демонстрирует один важный принцип: пространство может повторно использоваться в вычисле- ниях, тогда как для времени это по определению невозможно.
А вот более впечатляющее применение этого принципа.
(9.2) Существует алгоритм, решающий задачу 3-SAT с полиномиальными за- тратами пространства.
Доказательство. Просто используем алгоритм «грубой силы», который пере- бирает все возможные логические присваивания; каждое присваивание подается на множество условий для проверки того, выполняет ли оно эти условия. Важно реализовать это все с полиномиальными затратами пространства.
Для этого мы увеличиваем w-разрядный счетчик с 0 до 2й - 1, как описано выше. Значения счетчика ставятся в соответствие логическим присваиваниям: когда счет- чик достигает значения q, оно интерпретируется как присваивание v, при котором x содержит значение /'-го бита q.
Таким образом, полиномиальное пространство выделяется под перебор всех возможных вариантов логического присваивания v. Для каждого логического при- сваивания достаточно полиномиального пространства, чтобы подать данные на на- бор условий и проверить, обеспечивается ли их выполнение. Если условия выпол- няются, алгоритм можно немедленно остановить. Если условия не выполняются, мы удаляем промежуточные данные, задействованные в этой итерации, и заново используем память для следующего варианта присваивания. Таким образом, для проверки всех вариантов достаточно полиномиального пространства; тем самым доказывается граница для пространственных затрат алгоритма. ■
Так как 3-SAT является NР-полной задачей, у (9.2) имеется одно важное след- ствие.
(9.3) NР с РSРACE
Доказательство. Рассмотрим произвольную задачу Y из NР. Так как Y
Еще по теме PSPACE:
- Л.О. Доліненко, В.О. Доліненко, С.О. Сарновська. Цивільне право України, 2006
- ЦИВІЛЬНЕ ПРАВО УКРАЇНИ
- ПЕРЕДМОВА
- Частина І ПРОГРАМА КУРСУ «ЦИВІЛЬНЕ ПРАВО УКРАЇНИ»
- Розділ І. Загальні положення цивільного права
- Тема 1. Поняття цивільного права. Предмет та метод, система цивільного права. Функції та принципи цивільного права
- Тема 2. Цивільне законодавство України
- Тема 3. Поняття, елементи та види цивільних правовідносин
- Тема 4. Здійснення цивільних прав і виконання обов’язків
- Тема 5. Захист цивільних прав та інтересів
- Тема 6. Об’єкти цивільних прав
- Тема 7.ФІЗИЧНІ особи як суб’єкти цивільного права
- Тема 8. Юридичні особи
- Тема 9. Держава як суб’єкт цивільного права. Територіальні громади та Автономна Республіка Крим як суб’єкти цивільного права