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

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

$𝖭𝖲𝖯𝖠𝖢𝖤\left(f\left(n\right)\right)\subseteq 𝖣𝖲𝖯𝖠𝖢𝖤\left(f{\left(n\right)}^2\right).$

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

Доведення

Доведення спирається на алгоритм для Шаблон:Нп, задачі визначення того, чи існує шлях між двома вершинами в орієнтованому графі, який виконується в

$O((\log n{)}^2)$

пам'яті для

$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((\log n{)}^2)$

. Хоч описана вище програма написана мовою високого рівня, але той самий алгоритм може бути реалізований з тим самим асимптотичним простором, обмеженим на машині Тюрінга .

Щоб зрозуміти, чому цей алгоритм має на увазі теорему, розглянемо наступне. Для будь-якої мови $L\in 𝖭𝖲𝖯𝖠𝖢𝖤(f(n))$, є машина Тюрінга $M$ який вирішує $L$ у просторі $f(n)$ . Припустимо, що Шаблон:Нп алфавіт є двійковим $\{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(f(n))}$ . Отже, індукований підграф $[G_x^M]$ з $G_x^M$ містить (точно) допустимі конфігурації та має $2^{O(f(n))}$ вершин. Для кожного входу $x\in \{0,1{\}}^n$, $[G_x^M]$ має шлях від початкової конфігурації до конфігурації, що приймає, тоді і тільки тоді, коли $x\in L$ . Таким чином, вирішивши підключення в $[G_x^M]$, ми можемо прийняти рішення про членство $x$ в $L$ . За наведеним вище алгоритмом це можна зробити детерміновано в просторі $O\left({(\log 2^{O(f(n))})}^2\right)=O\left(f{\left(n\right)}^2\right)$ ; отже $L$ є в $𝖣𝖲𝖯𝖠𝖢𝖤\left(f{\left(n\right)}^2\right)$ .

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

Для всіх функцій $f\in \mathrm{\Omega }(\log n)$, $𝖭𝖲𝖯𝖠𝖢𝖤\left(f\left(n\right)\right)\subseteq 𝖣𝖲𝖯𝖠𝖢𝖤\left(f{\left(n\right)}^2\right)$ .

---

 

Наслідки

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

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

Див. також

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

Джерела

• Ленс Фортноу, Основи складності, Урок 18: Теорема Севіча Шаблон:Webarchive . Доступ 09/09/09.
• Річард Дж. Ліптон, Теорема Севіча Шаблон:Webarchive . Дає історичний звіт про те, як було виявлено доказ.
• Шаблон:Citation
• Шаблон:Citation
• Шаблон:Citation
• Шаблон:Citation