Главная
Новости
Строительство
Ремонт
Дизайн и интерьер




07.05.2021


07.05.2021


01.05.2021


26.04.2021


21.04.2021





Яндекс.Метрика





Класс PSPACE

24.03.2021

В теории сложности вычислений PSPACE — набор всех проблем разрешимости, которые могут быть разрешены машиной Тьюринга с полиномиальным ограничением пространства.

Машина Тьюринга с полиномиальным ограничением пространства

Если для данной машины Тьюринга верно, что существует полином p(n), такой что на любом входе размера n она посетит не более p(n) клеток, то такая машина называется машиной Тьюринга с полиномиальным ограничением пространства.

Можно показать, что:

1. Если машина Тьюринга с пространством, полиномиально ограниченным p(n), то существует константа c, при которой эта машина допускает свой вход длины n не более, чем за c 1 + p ( n ) {displaystyle c^{1+p(n)}} шагов.

Отсюда следует, что все языки машин Тьюринга с полиномиальным ограничением пространства — рекурсивные.

Классы PSPACE, NPSPACE

Класс языков PSPACE — множество языков, допустимых детерминированной машиной Тьюринга с полиномиальным ограничением пространства.

Класс языков NPSPACE — множество языков, допустимых недетерминированной машиной Тьюринга с полиномиальным ограничением пространства.

Для классов языков PSPACE и NPSPACE верны следующие утверждения:

1. PSPACE = NPSPACE (этот факт доказывается теоремой Сэвича)

2. Контекстно-зависимые языки являются подмножеством PSPACE

3. NL ⊆ P ⊆ NP ⊆ PSPACE ⊆ EXPTIME {displaystyle {mbox{NL}}subseteq {mbox{P}}subseteq {mbox{NP}}subseteq {mbox{PSPACE}}subseteq {mbox{EXPTIME}}}

4. NL ⊊ PSPACE ⊊ EXPSPACE {displaystyle {mbox{NL}}subsetneq {mbox{PSPACE}}subsetneq {mbox{EXPSPACE}}}

5. Если язык принадлежит PSPACE, то существует машина Тьюринга с полиномиальным ограничением пространства, такая что она остановится за c p ( n ) {displaystyle c^{p(n)}} шагов для некоторого c и полинома p(n).

Известно, что хотя бы один из трёх символов включения ⊆ {displaystyle subseteq } в утверждении NL ⊆ P ⊆ NP ⊆ PSPACE {displaystyle {mbox{NL}}subseteq {mbox{P}}subseteq {mbox{NP}}subseteq {mbox{PSPACE}}} должен быть строгим ( ⊊ ) {displaystyle (subsetneq )} (то есть исключать равенство множеств, отношение между которыми он описывает), но неизвестно, который из них. Также хотя бы одно подмножество в утверждении P ⊆ NP ⊆ PSPACE ⊆ EXPTIME {displaystyle {mbox{P}}subseteq {mbox{NP}}subseteq {mbox{PSPACE}}subseteq {mbox{EXPTIME}}} должно быть собственным (то есть хотя бы один символ включения должен быть строгим). Есть предположение, что все эти включения строгие ( ⊊ ) {displaystyle (subsetneq )} .

PSPACE-полные языки

PSPACE-полный язык — язык L ∈ PSPACE , {displaystyle {mbox{L}}in {mbox{PSPACE}},} к которому сводятся по Карпу все PSPACE-языки за полиномиальное время.

Для PSPACE-полных языков известны следующие факты:

Если L {displaystyle {mbox{L}}} является PSPACE-полным языком, то

1. L ∈ P ⇒ P = PSPACE ; {displaystyle {mbox{L}}in {mbox{P}}Rightarrow {mbox{P}}={mbox{PSPACE}};}

2. L ∈ NP ⇒ NP = PSPACE . {displaystyle {mbox{L}}in {mbox{NP}}Rightarrow {mbox{NP}}={mbox{PSPACE}}.}

Пример PSPACE-полного языка: язык истинных булевых формул с кванторами.