Класс NPSPACE

Класс NPSPACE

Содержание

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

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

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

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

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

Классы PSPACE, NPSPACE

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

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

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

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

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

3. :\mbox{NL} \subseteq \mbox{P} \subseteq \mbox{NP} \subseteq \mbox{PSPACE} \subseteq \mbox{EXPTIME}

4. :\mbox{NL} \subsetneq \mbox{PSPACE} \subsetneq \mbox{EXPSPACE}

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

Известно, что хотя бы один из трех \subseteq (Подмножество) символов в утверждении 3 должен быть строгим \subsetneq, но неизвестно какой. Есть предположение что все три \subsetneq.

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

PSPACE-полный язык - язык L \in PSPACE, к которому сводятся по Карпу все PSPACE-языки за полиномиальное время.

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

L\in PSPACEC \Rightarrow

1.L\in P \Rightarrow P = PSPACE

2.L\in NP \Rightarrow NP = PSPACE

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

Литература

  • Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман Введение в теорию автоматов, языков и вычислений = Introduction to Automata Theory, Languages, and Computation. — М.: «Вильямс», 2002. — С. 528. — ISBN 0-201-44124-1
  • Hopcroft, Monwani, Ulman: "Introduction to Automata Theory, Languages, and Computation"



Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Полезное


Смотреть что такое "Класс NPSPACE" в других словарях:

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

  • Сведение по Карпу — Любой язык программирования называется сводимым по Карпу к языку , если существует функция , вычисляемая за полиномиальное время, где F(x) принадлежит в том случае, если x принадлежит . Язык называется NP трудным, если к нему сводится любой язык… …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»