Знаймо

Додати знання

приховати рекламу

Цей текст може містити помилки.

Клас PSPACE



План:


Введення

В теорії складності обчислень PSPACE - набір всіх проблем розв'язності, які можуть бути дозволені машиною Тьюринга з поліноміальних обмеженням простору.


1. Машина Тюрінга з поліноміальних обмеженням простору

Якщо для даної машини Тьюринга вірно, що існує поліном p (n), такий що на будь-якому вході розміру n вона відвідає не більше p (n) клітин, то така машина називається машиною Тюрінга з поліноміальних обмеженням простору.

Можна показати, що:

1. Якщо машина Тюрінга з простором, поліноміальних обмеженим p (n), то існує константа c, при якій ця машина допускає свій вхід довжини n не більше, ніж за c ^ {1 + p (n)} кроків.

Звідси випливає, що всі мови машин Тюрінга з поліноміальних обмеженням простору - рекурсивні.


2. Класи 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, то існує машина Тьюрінга з поліноміальних обмеженням простору, така що вона зупиниться за c ^ {p (n)} кроків для деякого c і полінома p (n).

Відомо, що хоча б один з трьох \ Subseteq ( Підмножина) символів в утвердженні 3 повинен бути суворим \ Subsetneq , Але невідомо який. Є припущення що всі три \ Subsetneq .


3. 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"


Вважається легкими P L NL AC NC P-complete BQP BPP RP ZPP
Предпологаются складними NP ( co-NP NP-Complete Co-NP-complete) UP # P (# P-complete) IP PSPACE (PSPACE-complete) R PP AM
Вважається складними EXPTIME NEXPTIME EXPSPACE 2-EXPTIME PR RE Co-RE RE-complete Co-RE-complete PH
Список алгоритмів

Цей текст може містити помилки.

Схожі роботи | скачати

Схожі роботи:
Клас R
Клас
Клас RP
Клас co-NP
Клас PP
Клас PH
Клас P
Клас NP
Клас (математика)
© Усі права захищені
написати до нас