Складні класи, пов'язані з пам'яттю. Теорема Севіча. PSPACE-повнота. Обчислення на логарифмічній пам'яті. NL-повнота

Питання:
Складні класи, пов'язані з пам'яттю.
Теорема Севіча.
PSPACE-повнота.
Обчислення на логарифмічній пам'яті.
NL-повнота

Складні класи, пов'язані з пам'яттю
Функція ?: N → N називається функцією, що конструктується за пам’яттю, якщо існує машина Тьюринга, яка по входу 1? обчислює ?(?), використовуючи пам'ять ?(?(?)).
Нехай ?(?) – неспадна функція. Класом DSPACE(?(?)) називається клас мов, які можна розпізнати на детермінованій машині Тьюринга, на будь-якому вході довжини ?, що використовує ?(?(?)) осередків на робочих стрічках.
Нехай ?(?) - неспадна функція. Класом NSPACE(?(?)) називається клас мов, які можна розпізнати на недетермінованій машині Тьюринга, на будь-якому вході довжини ?, що використовує ?(?(?)) осередків на робочих стрічках (при будь-яких результатах недетермінірованного вибору).

Класом PSPACE називається DSPACE (??). Класом NPSPACE називається NSPACE (??).
Теорема 9.1. Мають місце співвідношення
DTIME(?(?))⊂NTIME(?(?))⊂DSPACE(?(?)) ⊂NSPACE(?(?))⊂DTIME(2?(?(?)))
Зауваження до теореми 9.1. Розглядаючи клас DTIME(?(?)), ми фактично говоримо про те, що ? (?)≥ ?. Втім, вкладення NSPACE(?(?))⊂DTIME (2?(?(?))) виконано вже для ? (?) ≥ log ?.
Слідство 9.1:

Теорема 9.2. Нехай ? і ? - зростаючі функції, що конструюються по пам’яті, причому ?(?)=?(?(?)) і ?(?)≥log?. Тоді DSPACE(?(?)) (DSPACE(?(?)).
Теорема 9.3. Теорема Севіча: Якщо ?(?)≥log?, то NSPACE(?(?)) ⊂DSPACE(?(?)2).
Слідство 9.2. PSPACE = NPSPACE.

PSPACE-повнота
Мова ? називається PSPACE - складною, якщо для будь-якої мови ? з PSPACE виконано ? ≤? ?.
Мова називається PSPACE-повною, якщо вона PSPACE - складна і лежить в PSPACE.
Якщо ? є PSPACE-складною і ? ≤? ?, то ? також PSPACE - складна.
Якщо ? є PSPACE-складною і лежить в P (в NP), то P = PSPACE (відповідно, NP = PSPACE).

Мовою SPACETMSAT називається множина {(?, ?, 1?) | ? (?) = 1 і ? (?) займає не більше ? осередків пам'яті}.
Теорема 9.4. Мова SPACETMSAT є PSPACE-повною.
Мовою SUCCINCTPATH називається множина {( , ?, ?) | в графі, побудованому за формулою , є шлях з ? в ?}. Граф за формулою будується таким чином: ? і ? є слова з ? бітів, а формула залежить від 2 ? змінних. Ребро між ? і ? проводиться в разі, коли (?, ?) = 1.
Теорема 9.5. Мова SUCCINCTPATH є PSPACE-повною.

Приклади повних задач
Мовою GG називається множина {(?, ?) | в узагальненій грі в міста на графі ? з початковою вершиною ? виграє перший гравець}.
Гра відбувається наступним чином: спочатку фішка ставиться в вершину ?, потім двоє по черзі зрушують її по ребрах, при цьому заборонено зрушувати фішку в вершину, де вона вже була. Програє той, хто не може зробити хід.
Теорема 9.6. Мова GG є PSPACE-повною.

Обчислення за логарифмічною пам'яті
Класом L називається DSPACE (log ?). Класом NL називається NSPACE (log ?).
Класом coNL називається множина мов ?, таких що ? ∈ NL.
Твердження1. Мова LE = {(?, ?) | ? ≤ ?} належить L.
Твердження2. Мова ADD = {(?, ?, ?) | ? + ? = ?} належить L.
Твердження3. Мова TREE = { ? | неорієнтовані граф ? є деревом } лежить в L .

Таким чином, алгоритм такий:
• Перевірити, що число ребер на одиницю менше числа вершин;
• Перевірити, що немає ізольованих вершин;
• Запустити обхід, починаючи з довільного ребра, перевірити, що він вперше повториться через 2 ( ? - 1) кроків.

NL-повнота
Функція ? обчислюється на логарифмічній пам'яті тоді і тільки тоді, коли мови ?? = {(?, ?): |? (?)| ≤ ?} і ?? = {(?, ?) | ? (?)? = 1} лежать в L, при цьому максимальне ?, при якому (?, ?) ∈ ??, обмежена поліномом від | ? |.
Композиція функцій, обчислюваних на логарифмічній пам'яті, обчислювана на логарифмічній пам'яті.

Мова ? логарифмічно зводиться до мови ?, якщо існує функція ?, обчислювана на логарифмічній пам'яті, така що для всіх ? виконано ? ∈ ? тоді і тільки тоді, коли ? (?) ∈ ?. Позначення ?≤??.
Твердження :
1. Логарифмічна зведеність рефлексивна: ?≤? ?;
2. Логарифмічна зведеність транзитивна: якщо ?≤? ? і ?≤? ?, то
?≤? ?;
3. Якщо ? ∈ L, а ?≠Ø і ?≠{0, 1} *, то ? ≤? ?;
4. Якщо ? ∈ L і ? ≤? ?, то ? ∈ L;
5. Якщо ? ∈ NL і ? ≤? ?, то ? ∈ NL.