Теорема Севіча

Теорема Севіча з теорії складності обчислень, доведена ^[en] у 1970 році, дає зв’язок між детермінованою та недетермінованою складністю простору .
У ньому зазначено, що для будь-якої функції ${\displaystyle f\in \Omega (\log(n))}$ ,

${\displaystyle {\mathsf {NSPACE}}\left(f\left(n\right)\right)\subseteq {\mathsf {DSPACE}}\left(f\left(n\right)^{2}\right).}$

Іншими словами, якщо недетермінована машина Тюрінга може вирішити проблему, використовуючи ${\displaystyle f(n)}$ пам'яті, детермінована машина Тюрінга може вирішити ту ж задачу за квадрат пам'яті. Хоча здається, що не детермінізм може призвести до експоненційного виграшу в часі, але ця теорема показує, що він має помітно більш обмежений вплив на вимоги до пам'яті.

Доведення

Доведення спирається на алгоритм для ^[en], задачі визначення того, чи існує шлях між двома вершинами в орієнтованому графі, який виконується в ${\displaystyle O\left((\log n)^{2}\right)}$ пам'яті для ${\displaystyle n}$ вершин. Основна ідея алгоритму полягає в тому, щоб рекурсивно розв’язати дещо більш загальну задачу, перевіряючи існування шляху від вершини s до іншої вершини t, яка використовує не більше k ребер, де k є параметром, який вводиться як вхідний параметр рекурсивного алгоритму. STCON можна вирішити з цієї проблеми, встановивши k на n . Щоб перевірити шлях k- краю від s до t, можна перевірити, чи кожна вершина u може бути серединою шляху s-t, шляхом рекурсивного пошуку шляхів половини довжини від s до u і u до t . Використовуючи псевдокод (у синтаксисі Python ), ми можемо виразити цей алгоритм таким чином:

def k_edge_path(s, t, k) -> bool:  """k initially equals n (which is the number of vertices)""" if k == 0: return s == t if k == 1: return (s, t) in edges for u in vertices: if k_edge_path(s, u, floor(k / 2)) and k_edge_path(u, t, ceil(k / 2)): return True return False 

Цей пошук викликає глибину рекурсії ${\displaystyle O(\log n)}$ рівнів, кожен з яких вимагає ${\displaystyle O(\log n)}$ біти для зберігання аргументів функції та локальних змін на цьому рівні: k і всі вершини ( s, t, u ) вимагають ${\displaystyle O(\log n)}$ біти кожен. Таким чином, загальна складність допоміжного простору ${\displaystyle O\left((\log n)^{2}\right)}$ . Хоч описана вище програма написана мовою високого рівня, але той самий алгоритм може бути реалізований з тим самим асимптотичним простором, обмеженим на машині Тюрінга .

Щоб зрозуміти, чому цей алгоритм має на увазі теорему, розглянемо наступне. Для будь-якої мови ${\displaystyle L\in {\mathsf {NSPACE}}(f(n))}$, є машина Тюрінга ${\displaystyle M}$ який вирішує ${\displaystyle L}$ у просторі ${\displaystyle f(n)}$ . Припустимо, що ^[en] алфавіт є двійковим ${\displaystyle \{0,1\}}$ (а саме ${\displaystyle L\subseteq \{0,1\}^{*}}$ ). Для будь-якого вхідного слова ${\displaystyle x\in \{0,1\}^{*}}$, існує орієнтований граф ${\displaystyle G_{x}^{M}}$ вершинами яких є конфігурації ${\displaystyle M}$ під час роботи на вході ${\displaystyle x}$ . Таких конфігурацій може бути нескінченно багато; наприклад, коли ${\displaystyle M}$ продовжує записувати символ на стрічці і рухати голову вправо в петлі до нескінченності. Потім конфігурації зростають довільно. Проте ми знаємо щонайбільше ${\displaystyle f\left(n\right)}$ потрібен простір, щоб вирішити чи ${\displaystyle x\in L}$, тому ми піклуємося лише про конфігурації розміру ${\displaystyle f\left(n\right)}$; назвемо будь-яку таку конфігурацію допустимою . Існує скінченна кількість допустимих конфігурацій; а саме ${\displaystyle 2^{O\left(f(n)\right)}}$ . Отже, індукований підграф ${\displaystyle [G_{x}^{M}]}$ з ${\displaystyle G_{x}^{M}}$ містить (точно) допустимі конфігурації та має ${\displaystyle 2^{O\left(f(n)\right)}}$ вершин. Для кожного входу ${\displaystyle x\in \{0,1\}^{n}}$, ${\displaystyle [G_{x}^{M}]}$ має шлях від початкової конфігурації до конфігурації, що приймає, тоді і тільки тоді, коли ${\displaystyle x\in L}$ . Таким чином, вирішивши підключення в ${\displaystyle [G_{x}^{M}]}$, ми можемо прийняти рішення про членство ${\displaystyle x}$ в ${\displaystyle L}$ . За наведеним вище алгоритмом це можна зробити детерміновано в просторі ${\displaystyle O\left(\left(\log 2^{O\left(f(n)\right)}\right)^{2}\right)=O\left(f\left(n\right)^{2}\right)}$ ; отже ${\displaystyle L}$ є в ${\displaystyle {\mathsf {DSPACE}}\left(f\left(n\right)^{2}\right)}$ .

Оскільки це стосується всіх ${\displaystyle f\in \Omega (\log n)}$ і все ${\displaystyle L\in {\mathsf {NSPACE}}\left(f\left(n\right)\right)}$, отримуємо твердження теореми:

Для всіх функцій ${\displaystyle f\in \Omega (\log n)}$, ${\displaystyle {\mathsf {NSPACE}}\left(f\left(n\right)\right)\subseteq {\mathsf {DSPACE}}\left(f\left(n\right)^{2}\right)}$ .

---

 

Наслідки

Деякі важливі наслідки теореми включають:

• PSPACE = NPSPACE
  • Це прямо випливає з того факту, що квадрат поліноміальної функції все ще є поліноміальною функцією. Вважається, що подібного зв'язку між класами поліноміальної часової складності P і NP не існує, хоча це все ще залишається відкритим питанням .
• ^[en] ⊆ L ²
  • STCON є NL-повним, тому всі мови в NL також належать до класу складності ${\displaystyle {\mathsf {\color {Blue}L}}^{2}={\mathsf {DSPACE}}\left(\left(\log n\right)^{2}\right)}$ .

Див. також

• Теорема Піфагора
• Теорема Коші (теорія груп)
• Клас складності PSPACE

Примітки

1. Arora & Barak (2009) p.86
2. Arora & Barak (2009) p.92

• Річард Дж. Ліптон, Теорема Севіча [ 8 квітня 2009 у Wayback Machine.] . Дає історичний звіт про те, як було виявлено доказ.
• (1993), Section 7.3: The Reachability Method, Computational Complexity (вид. 1st), Addison Wesley, с. 149—150, ISBN 
• ; Barak, Boaz (2009), Computational complexity. A modern approach, Cambridge University Press, ISBN , Zbl 1193.68112
• (1970), Relationships between nondeterministic and deterministic tape complexities, Journal of Computer and System Sciences, 4 (2): 177—192, doi:10.1016/S0022-0000(70)80006-X
• (1997), Section 8.1: Savitch's Theorem, Introduction to the Theory of Computation, PWS Publishing, с. 279–281, ISBN