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

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

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

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

Доведення

Доведення спирається на алгоритм для STCON, задачі визначення того, чи існує шлях між двома вершинами в орієнтованому графі, який виконується в $O\left((\log n)^{2}\right)$ пам'яті для $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

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

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

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

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

---

 

Наслідки

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

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

Див. також

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

Джерела

• Ленс Фортноу, Основи складності, Урок 18: Теорема Севіча [Архівовано 18 травня 2009 у Wayback Machine.] . Доступ 09/09/09.
• Річард Дж. Ліптон, Теорема Севіча [Архівовано 8 квітня 2009 у Wayback Machine.] . Дає історичний звіт про те, як було виявлено доказ.
• Papadimitriou, Christos (1993), Section 7.3: The Reachability Method, Computational Complexity (вид. 1st), Addison Wesley, с. 149—150, ISBN 0-201-53082-1
• Arora, Sanjeev; Barak, Boaz (2009), Computational complexity. A modern approach, Cambridge University Press, ISBN 978-0-521-42426-4, Zbl 1193.68112
• Savitch, Walter J. (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
• Sipser, Michael (1997), Section 8.1: Savitch's Theorem, Introduction to the Theory of Computation, PWS Publishing, с. 279–281, ISBN 0-534-94728-X