PSPACE
Мы будем изучать класс PSPACE — множество всех задач, которые могут быть решены алгоритмом с полиномиальной пространственной сложностью (то есть алгоритмом с затратами пространства, полиномиальными по размерам входных данных).
Для начала рассмотрим отношение PSPACE к классам задач, которые рассматривались выше. Прежде всего, за полиномиальное время алгоритм может потреблять не более чем полиномиальное пространство; итак, можно утверждать:
(9.1) P Ӭ PSPACE
Однако множество PSPACE намного шире. Например, рассмотрим алгоритм, который просто считает от 0 до 2n – 1 в двоичной системе. Он просто реализует n-разрядный счетчик, который работает по тому же принципу, что и одометр в автомобиле. Таким образом, алгоритм выполняется за экспоненциальное время, после чего останавливается; при этом он использует полиномиальное пространство.
И хотя этот алгоритм не делает ничего особенно интересного, он демонстрирует один важный принцип: пространство может повторно использоваться в вычислениях, тогда как для времени это по определению невозможно.
А вот более впечатляющее применение этого принципа.
(9.2) Существует алгоритм, решающий задачу 3-SAT с полиномиальными затратами пространства.
Доказательство. Просто используем алгоритм «грубой силы», который перебирает все возможные логические присваивания; каждое присваивание подается на множество условий для проверки того, выполняет ли оно эти условия. Важно реализовать это все с полиномиальными затратами пространства.
Таким образом, полиномиальное пространство выделяется под перебор всех возможных вариантов логического присваивания v.
Для каждого логического присваивания достаточно полиномиального пространства, чтобы подать данные на набор условий и проверить, обеспечивается ли их выполнение.
Если условия выполняются, алгоритм можно немедленно остановить. Если условия не выполняются, мы удаляем промежуточные данные, задействованные в этой итерации, и заново используем память для следующего варианта присваивания.
Таким образом, для проверки всех вариантов достаточно полиномиального пространства; тем самым доказывается граница для пространственных затрат алгоритма.
- Алгоритмы, которые работают бесконечно
- Бесконечные пространства выборки
- Независимые события
- Конечные вероятностные пространства
- Простой рандомизированный план
- Планы и их продолжительность
- Анализ алгоритмов маркировки
- Достижение линейного ожидаемого времени выполнения
- Структура данных для хранения подквадратов
- Оформление отчета по практике по ГОСТу 2021/2022
- Оформление ВКР по ГОСТу
- Как составить бизнес-план своими силами
- Оформление эссе по ГОСТу
- Оформление презентации по ГОСТу
- Оформление статьи по ГОСТу
- Оформление дипломной работы по ГОСТ 2021/2022
- Оформление курсовой работы по ГОСТу
- Оформление контрольной работы по ГОСТу