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

Доведення спирається на алгоритм для STCON, задачі визначення того, чи існує шлях між двома вершинами в орієнтованому графі, який виконується в ${\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)}$ . Припустимо, що w.l.o.g. алфавіт є двійковим ${\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 не існує, хоча це все ще залишається відкритим питанням .
• NL ⊆ 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

• Ленс Фортноу, Основи складності, Урок 18: Теорема Севіча . Доступ 09/09/09.
• Річард Дж. Ліптон, Теорема Севіча . Дає історичний звіт про те, як було виявлено доказ.
• 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.