<<
>>

PSPACE

Мы будем изучать класс 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

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме PSPACE:

  1. Л.О. Доліненко, В.О. Доліненко, С.О. Сарновська. Цивільне право України, 2006
  2. ЦИВІЛЬНЕ ПРАВО УКРАЇНИ
  3. ПЕРЕДМОВА
  4. Частина І ПРОГРАМА КУРСУ «ЦИВІЛЬНЕ ПРАВО УКРАЇНИ»
  5. Розділ І. Загальні положення цивільного права
  6. Тема 1. Поняття цивільного права. Предмет та метод, система цивільного права. Функції та принципи цивільного права
  7. Тема 2. Цивільне законодавство України
  8. Тема 3. Поняття, елементи та види цивільних правовідносин
  9. Тема 4. Здійснення цивільних прав і виконання обов’язків
  10. Тема 5. Захист цивільних прав та інтересів
  11. Тема 6. Об’єкти цивільних прав
  12. Тема 7.ФІЗИЧНІ особи як суб’єкти цивільного права
  13. Тема 8. Юридичні особи
  14. Тема 9. Держава як суб’єкт цивільного права. Територіальні громади та Автономна Республіка Крим як суб’єкти цивільного права