Клас складності PSPACE

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

PSPACE (англ. Polynomial Space — поліноміальне місце) — клас задач, які розв'язні на машині Тюрінга з використанням поліноміального запасу пам'яті.

Формальне означення

[ред. | ред. код]

Позначимо як SPACE(t(n)) множину задач, які розв'язні на машині Тюрінга з використанням запасу пам'яті O(t(n)) для деякої функції t від входу обсягом n. Тоді можна визначити PSPACE як , де PSPACE — строга надмножина множини контекстно-залежних формальних мов.

Якщо замість детермінованої машини Тюрінга взяти недетерміновану, то це не додасть задач до класу PSPACE. За теоремою Севіча, NPSPACE еквівалентний PSPACE, оскільки детермінована МТ може змоделювати роботу недетермінованої МТ без використання додаткової пам'яті, записуючи варіанти (можливо експоненційну кількість) по черзі на те саме місце.

Зв'язки між класами

[ред. | ред. код]
Відношення вкладення між класами складності

Відомі такі зв'язки між PSPACE та класами NL, P, NP, PH, EXPTIME, EXPSPACE:

Відомо, що в першому і другому рядках наведених відношень між класами, принаймні одне відношення вкладення має бути строгим, але невідомо, котре. Досить імовірно, що всі ці відношення є строгими. Для обох відношень вкладення третього рядка точно відомо, що вони строгі. Перше випливає з прямої діагоналізації (теорема про ієрархію місця[en]) і факту PSPACE = NPSPACE. Друге випливає з теореми про ієрархію місця.

Найважчі задачі класу PSPACE — PSPACE-повні задачі.

Література

[ред. | ред. код]
  • Hopcroft, John E.; Motwani, Rajeev; Ullman, Jeffrey D. (2001). Вступ до теорії автоматів, мов і обчислень (вид. 2nd). Addison–Wesley. с. 521.(англ.)
  • Роджерс Х.(інші мови). Теория рекурсивных функций и эффективная вычислимость. — М. : Мир, 1972. — 416 с.(рос.)
  • Sipser, Michael (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X. Section 8.2–8.3 (The Class PSPACE, PSPACE-completeness), pp. 281–294.
  • Papadimitriou, Christos (1993). Computational Complexity (вид. 1st). Addison Wesley. ISBN 0-201-53082-1. Chapter 19: Polynomial space, pp. 455–490.