跳转至

計算理論基礎

本部分將介紹基礎的計算理論的知識。這部分內容在 OI 中作用不大（但還是略有作用：如果你遇到了一個 NP-hard 問題，你可以認為它是不存在多項式複雜度的解法的），可以作為興趣瞭解，或者為以後的學習做準備。

本文中許多結論都是不加證明的，如果有興趣的話可以自行查閲相關證明。

前置知識：時間複雜度。

問題

語言

一個 字母表（alphabet） 是一個非空有限集合，該集合中的元素稱為 符號/字符（symbol）。

令 \(\Sigma^\ast\) 表示非負整數個 \(\Sigma\) 中的字符連接而成的串，字母表 \(\Sigma\) 上的一個 語言（language） 是 \(\Sigma^\ast\) 的一個子集。

需要注意的是，這裏的「語言」是一個抽象的概念，通常意義上的字符串是語言，所有的有向無環圖也可以是一個語言（01 串與有向圖之間可以建立雙射，具體方式無需瞭解）。

由於任何語言都可以轉化成 01 串的形式，所以在下文中不加説明時 \(\Sigma=\{0, 1\}\)。

判定問題

判定問題就是隻能用 YES/NO 回答的問題，本質上是判定一個串是否屬於一個語言，即：\(f:\Sigma^\ast\rightarrow\{0, 1\}, f(x)=1\iff x\in L\) 是一個關於字母表 \(\Sigma\) 和語言 \(L\) 的判定問題。如，「判定一張圖是不是一個有向無環圖」就是一個判定問題。

判定問題由於其簡潔性而常常被作為計算理論研究的對象。本文中不加説明時，「問題」都指「判定問題」，當然，有時一些命題也能簡單地推廣到其它問題上。

一個語言也可以代指「判定一個串是否屬於這個語言」這個判定問題，因此，「語言」和「問題」可以視作同義詞。

功能性問題

功能性問題的回答不止 YES/NO，可以是一個數或是其它。如，「求兩個數的和」就是一個功能性問題。

任何功能性問題都可以轉化為一個判定問題，如，「求兩個數的和」可以轉化為「判定兩個數的和是否等於第三個數」。

判定問題也可以轉化為一個功能性問題：求這個判定問題的指示函數，即上文中判定問題定義裏的 \(f\)。

圖靈機

確定性圖靈機

不加説明時，「圖靈機」往往指「確定性圖靈機」，本文中也是如此。

圖靈機有很多不同的定義，這裏選取其中一種，其它定義下的圖靈機往往與下面這種定義的圖靈機計算能力等價。

圖靈機是一個在一條可雙向無限延伸且被劃分為若干格子的紙帶上進行操作的機器，其有內部狀態，還有一個可以在紙帶上進行修改與移動的磁針。

正式地説，圖靈機是一個七元組 \(M=\langle Q,\Gamma,b,\Sigma,\delta,q_0,F\rangle\)，其中：

  • \(Q\) 是一個有限非空的 狀態集合；
  • \(\Gamma\) 是一個有限非空的 磁帶字母表；
  • \(b\in\Gamma\) 是 空字符，它是唯一一個在計算過程中可以在磁帶上無限頻繁地出現的字符；
  • \(\Sigma\subseteq(\Gamma\setminus\{b\})\) 是 輸入符號集，是可以出現在初始磁帶（即輸入）上的字符；
  • \(q_0\in Q\) 是 初始狀態；
  • \(F\subseteq Q\) 是 接受狀態，如果一個圖靈機在某個接受狀態停機，則稱初始磁帶上的內容被這個圖靈機 接受。
  • \(\delta :(Q\setminus F)\times \Gamma \not \to Q\times \Gamma \times \{L,R\}\) 是一個被稱作 轉移函數 的 partial function（即只對定義域的一個子集有定義的函數）。如果 \(\delta\) 在當前狀態下沒有定義，則圖靈機停機。

圖靈機從初始狀態與紙帶起點起，每次根據當前的內部狀態 \(x\) 和當前磁針指向的紙帶上的單元格中的字符 \(y\) 進行操作：若 \(\delta(x, y)\) 沒有定義則停機，否則若 \(\delta(x, y)=(a, b, c)\)，則將內部狀態修改為 \(a\)，將磁針指向的格子中的字符修改為 \(b\)，若 \(c\) 為 \(L\) 則向左移動一格，為 \(R\) 則向右移動一格。

其實，知道圖靈機的工作細節是不必要的，只需建立直觀理解即可。

圖靈機 \(M\) 在輸入 \(x\) 下的輸出記作 \(M(x)\)（\(M(x)=1\) 當且僅當 \(M\) 接受 \(x\)，\(M(x)=0\) 當且僅當 \(M\) 在輸入 \(x\) 下在有限步驟內停機且 \(M\) 不接受 \(x\)），也可以在括號內包含多個參數，用逗號隔開，具體實現時可以向字母表中添加一個元素表示逗號來隔開各個參數。

圖靈機與馮·諾依曼計算機解決問題的時間複雜度差別在多項式級別內，所以研究複雜度類時可以使用圖靈機作為計算模型。

非確定性圖靈機

非確定型圖靈機是圖靈機的一種，它與確定型圖靈機的不同在於：確定型圖靈機的每一步只能轉移到一個狀態，而非確定型圖靈機可以「同時」轉移到多個狀態，從而在多個「分支」並行計算，一旦這些「分支」中有一個在接受狀態停機，則此非確定性圖靈機接受這個輸入。

事實上，任何確定型圖靈機都可以用類似於迭代加深搜索的方式在指數級時間內模擬一台非確定型圖靈機多項式時間內的行為。

在現實生活中，確定型圖靈機相當於單核處理器，只支持串行處理；而非確定型圖靈機相當於理想的多核處理器，支持無限大小的並行處理。

多帶圖靈機

標準的圖靈機只能在一條紙帶上進行操作，但為了方便，本文中研究多帶圖靈機。對於一個 \(k\) 帶圖靈機，其中一條紙帶是隻讀的輸入帶，而剩下的 \(k-1\) 條紙帶可以進行讀寫，並且這 \(k-1\) 條紙帶中還有一條紙帶用作輸出。

多帶圖靈機的紙帶數必須是有限的。

對於一個多帶圖靈機，它使用的空間是磁頭在除輸入帶外的其它紙帶上所訪問過的單元格數目。

圖靈機的編碼

圖靈機可以被自然數編碼，即存在滿射函數 \(f:\mathbb{N}\to\mathbb{M}\)，使得每個自然數都對應一個圖靈機，而每個圖靈機都有無數個編碼。因此，由若干圖靈機構成的集合可以是一個語言。

記由自然數 \(\alpha\) 編碼的圖靈機為 \(M_{\alpha}\)。

通用圖靈機

存在一台圖靈機 \(\mathcal U\) 滿足：

  1. 若 \(M_{\alpha}\) 在輸入 \(x\) 下在有限時間內停機，則 \(\mathcal{U}(x, \alpha)=M_{\alpha}(x)\)，否則 \(\mathcal{U}(x, \alpha)\) 不會在有限時間內停機；
  2. 如果對於任意 \(x\in\{0, 1\}^\ast\)，\(M_\alpha\) 在輸入 \(x\) 下在 \(T(|x|)\) 時間內停機，則對於任意 \(x\in\{0, 1\}^\ast\)，\(\mathcal{U}(x, \alpha)\) 在 \(O(T(|x|)\log T(|x|))\) 時間內停機。

即：存在一台通用圖靈機，它能模擬任何一台圖靈機，且花費的時間只會比這台被模擬的圖靈機慢其運行時間的對數。

可計算性

不可計算問題

對於一個判定問題，若存在一個總是在有限步內停機且能夠正確進行判定的圖靈機，則這個問題是一個 圖靈可計算 的問題，否則這個問題是一個 圖靈不可計算 的問題。

由於圖靈機可以被自然數編碼，所以圖靈機的個數是可數無窮，而語言（即二進制串的集合）的個數是不可數無窮，而每個圖靈機最多判定一個語言，所以一定存在圖靈不可計算的問題。

停機問題

停機問題是一個經典的圖靈不可計算問題：給定 \(\alpha\) 和 \(x\)，判定 \(M_{\alpha}\) 在輸入為 \(x\) 時是否會在有限步內停機。

停機問題是圖靈不可計算的證明

定義函數 \(\mathsf{UC}:\{0,1\}^\ast\to\{0,1\}\) 為：

\[ \mathsf{UC}(\alpha)=\begin{cases}0&M_\alpha(\alpha)=1\\1&\text{otherwise}\end{cases} \]

我們先證明 \(\mathsf{UC}\) 函數是圖靈不可計算的：

假設存在一台圖靈機 \(M_{\beta}\) 能夠計算 \(\mathsf{UC}\)，那麼根據 \(\mathsf{UC}\) 的定義可以得到 \(\mathsf{UC}(\beta)=1\iff M_\beta(\beta)\neq 1\)，而根據 \(M_{\beta}\) 能夠計算 \(\mathsf{UC}\) 可以得到 \(M_{\beta}(\beta)=\mathsf{UC}(\beta)\)，產生了矛盾，所以假設不成立，不存在可以計算 \(\mathsf{UC}\) 的圖靈機。

令 \(M_{\mathsf{HALT}}\) 是一個可以解決停機問題的圖靈機，\(M_{\mathsf{HALT}}(x,\alpha)\) 的值是判定問題 \(M_\alpha\) 在輸入為 \(x\) 時是否會在有限步內停機的解，那麼我們可以構造出一台能夠計算 \(\mathsf{UC}\) 函數的圖靈機 \(M_{\mathsf{UC}}\)：

\(M_\mathsf{UC}\) 首先調用 \(M_\mathsf{HALT}(α,α)\), 如果它輸出 \(0\), 則 \(M_\mathsf{UC}(α)=1\)；否則，\(M_\mathsf{UC}\) 使用通用圖靈機模擬計算得到答案。

由於 \(\mathsf{UC}\) 函數是圖靈不可計算的，所以 \(M_\mathsf{HALT}\) 不存在，也就是説停機問題是圖靈不可計算的。

丘奇 - 圖靈論題

丘奇 - 圖靈論題稱，若一類問題有一個有效的方法解決，則這類問題可以被某個圖靈機解決。

其中，「有效的方法」需要滿足：

  1. 包含有限條清晰的指令；
  2. 當用其解決這類問題的其中一個時，這個方法需要在有限步驟內結束，且得到正確的答案。

這個論題沒有被證明，但其是計算理論的一條基本公理。

複雜度類

複雜度類有很多，本文只會介紹其中較為常見的一小部分。

R 和 RE

對於語言 \(L\) 和圖靈機 \(M\)，若 \(M\) 在任何輸入下都能在有限步驟內停機，且 \(M(x)=1\iff x\in L\)，則稱 \(M\) 能夠 判定 \(L\)。

對於語言 \(L\) 和圖靈機 \(M\)，若對於任何屬於 \(L\) 的輸入，\(M\) 都在有限步驟內停機，且 \(M(x)=1\iff x\in L\)，則稱 \(M\) 能夠 識別 \(L\)。

複雜度類 \(\mathsf R\) 表示那些可以被某台圖靈機判定的語言的集合，即所有圖靈可計算的語言。

複雜度類 \(\mathsf{RE}\) 表示那些可以被某台圖靈機識別的語言的集合。\(\mathsf{RE}\) 也被稱作遞歸可枚舉語言。

由定義可以得到 \(\mathsf{R}\subseteq\mathsf{RE}\)。

DTIME

如果存在一台確定性圖靈機能夠判定一個語言，且對於任何輸入 \(x\)，這台圖靈機可以在 \(O(f(|x|))\) 的時間內停機，那麼這個語言屬於 \(\mathsf{DTIME}(f(n))\) 類。

P

複雜度類 \(\mathsf P\) 表示可以由確定性圖靈機在多項式時間內解決的判定問題，即：

\[ \mathsf{P}=\bigcup\limits_{k\in\mathbb{N}}\mathsf{DTIME}(n^k) \]

線性規劃、計算最大公約數、求圖的最大匹配的判定版本都是 \(\mathsf P\) 類問題。

EXPTIME

複雜度類 \(\mathsf{EXPTIME}\) 表示可以由確定性圖靈機在指數級時間內解決的判定問題，即：

\[ \mathsf{EXPTIME}=\bigcup\limits_{k\in\mathbb{N}}\mathsf{DTIME}(2^{n^k}) \]

停機問題的弱化版——給定一個圖靈機的編碼以及一個正整數 \(k\)，判定這個圖靈機是否在 \(k\) 步內停機，是一個 \(\mathsf{EXPTIME}\) 類的問題。因為這個問題的解法需要 \(O(k)\) 的時間，而數字 \(k\) 可以被編碼為長度為 \(O(\log k)\) 的二進制串。

NTIME

如果存在一台非確定性圖靈機能夠判定一個語言，且對於任何輸入 \(x\)，這台圖靈機可以在 \(O(f(|x|))\) 的時間內停機，那麼這個語言屬於 \(\mathsf{NTIME}(f(n))\) 類。

NP

複雜度類 \(\mathsf{NP}\) 表示可以由非確定性圖靈機在多項式時間內解決的判定問題，即：

\[ \mathsf{NP}=\bigcup\limits_{k\in\mathbb{N}}\mathsf{NTIME}(n^k) \]

所有 \(\mathsf P\) 類問題都是 \(\mathsf{NP}\) 類問題。更多 \(\mathsf{NP}\) 類問題請參見下文中的 NPC 問題以及 NP-intermediate 問題。

NP-hard

如果所有 \(\mathsf{NP}\) 類問題都可以在多項式時間內規約到問題 \(H\)，那麼問題 \(H\) 是 NP-hard 的。

換句話説，如果可以在一單位的時間內解決 NP-hard 的問題 \(H\)，那麼所有 \(\mathsf{NP}\) 類問題都可以在多項式單位的時間內解決。

NP-complete

如果一個問題既是 \(\mathsf{NP}\) 類問題又是 NP-hard 的，那麼這個問題是 NP 完全 (NP-complete) 的，或者説這是一個 NPC 問題。

一些經典的 NPC 問題：旅行商問題的判定版本、最大獨立集問題的判定版本、最小點覆蓋問題的判定版本、最長路問題的判定版本、0-1 整數規劃問題的判定版本、集合覆蓋問題、圖着色問題、揹包問題、三維匹配問題、最大割問題的判定版本。

NPC 問題的功能性版本往往是 NP-hard 的，例如：「判定一張圖中是否存在大小為 \(k\) 的團」既是一個 \(\mathsf{NP}\) 類問題又是 NP-hard 的，從而它是一個 NPC 問題，而它的功能性版本「求一張圖的最大團」不是 NPC 問題，但這個功能性版本依然是 NP-hard 的。

類似地，其它複雜度類也會有「XX-complete」，如所有 \(\mathsf{EXPTIME}\) 類的問題都能在多項式時間內規約到 EXPTIME-complete 的問題。

co-NP

一個問題是 \(\mathsf{co-NP}\) 類問題，當且僅當它的補集是 \(\mathsf{NP}\) 類問題。如果將「問題」理解為「語言」，而「語言」是 \(\Sigma^\ast\) 的子集，就能理解「補集」了。

例如：「給定 \(n\) 個子集，判斷是否能夠從中選取 \(k\) 個，覆蓋整個集合」是一個 NPC 問題，而其補集「給定 \(n\) 個子集，判斷是否從中任取 \(k\) 個都不能覆蓋整個集合」是一個 \(\mathsf{co-NP}\) 類問題。如果第一個問題的答案是「是」，那麼相當於找到了第二個問題的一組反例，從而第二個問題的答案是「否」。

NP-intermediate

如果一個問題是 \(\mathsf{NP}\) 類問題，但它既不是 \(\mathsf{P}\) 類問題也不是 NPC 問題，則稱其為 NP-intermediate 問題。

就人們目前的瞭解，圖同構問題、離散對數問題和因數分解問題可能是 NP-intermediate 的。

Ladner 定理指出，如果 \(\mathsf{P}\ne\mathsf{NP}\)，則一定存在問題是 NP-intermediate 的。

NEXPTIME

複雜度類 \(\mathsf{NEXPTIME}\) 表示可以由非確定性圖靈機在指數級時間內解決的判定問題，即：

\[ \mathsf{NEXPTIME}=\bigcup\limits_{k\in\mathbb{N}}\mathsf{NTIME}(2^{n^k}) \]

#P

\(\mathsf{\#P}\) 類問題不是判定問題，而是關於 \(\mathsf{NP}\) 類問題的計數問題：數一個 \(\mathsf{NP}\) 類問題的解的個數是一個 \(\mathsf{\#P}\) 類的問題。換句話説，數一個串在一個總是在多項式時間內停機的非確定性圖靈機的多少個分支處被接受是一個 \(\mathsf{\#P}\) 類的問題。

求一張普通圖或二分圖的匹配或完美匹配個數都是 #P 完全的，對應的判定問題為「判定一張圖是否存在（完美）匹配」。

DSPACE

如果存在一台確定性圖靈機能夠在輸入為 \(x\) 時在 \(O(f(|x|))\) 的空間內判定一個語言，那麼這個語言屬於 \(\mathsf{DSPACE}(f(n))\) 類。

  • \(\mathsf{REG}=\mathsf{DSPACE}(O(1))\)，即正則語言，也就是自動機能夠判定的語言。

  • \(\mathsf{L}=\mathsf{DSPACE}(O(\log n))\)，需要注意的是圖靈機使用的空間不包括輸入佔用的空間。

  • \(\mathsf{PSPACE}=\bigcup\limits_{k\in\mathbb N}\mathsf{DSPACE}(n^k)\)

  • \(\mathsf{EXPSPACE}=\bigcup\limits_{k\in\mathbb N}\mathsf{DSPACE}(2^{n^k})\)

NSPACE

如果存在一台非確定性圖靈機能夠在輸入為 \(x\) 時在 \(O(f(|x|))\) 的空間內判定一個語言，那麼這個語言屬於 \(\mathsf{NSPACE}(f(n))\) 類。

  • \(\mathsf{REG}=\mathsf{DSPACE}(O(1))=\mathsf{NSPACE}(O(1))\)

  • \(\mathsf{NL}=\mathsf{NSPACE}(O(\log n))\)

  • \(\mathsf{CSL}=\mathsf{NSPACE}(O(n))\)，即上下文相關語言。

  • \(\mathsf{PSPACE}=\mathsf{NPSPACE}=\bigcup\limits_{k\in\mathbb N}\mathsf{NSPACE}(n^k)\)

  • \(\mathsf{EXPSPACE}=\mathsf{NEXPSPACE}=\bigcup\limits_{k\in\mathbb N}\mathsf{NSPACE}(2^{n^k})\)

多項式時間

簡單來説，如果存在正數 \(k\) 使得一個算法的時間複雜度為 \(O(n^k)\)（注意，不是 \(\Theta(n^k)\)），其中 \(n\) 為問題規模（輸入的長度），則稱這個算法是 多項式時間 的。如果一個問題有（確定性圖靈機上的）多項式時間的算法來解決，則這個問題屬於複雜度類 \(\mathsf{P}\)。

多項式時間可分為強多項式時間和弱多項式時間，除此之外還有偽多項式時間。

Strongly polynomial time 強多項式時間

我們先定義一個計算模型，稱作算術模型。在算術模型中，數字之間的算術運算（加減乘除、比較大小）可以在單位時間內完成（即 \(O(1)\) 時間內完成，與數字大小無關）。

如果一個算法在算術模型下的操作數是輸入中的數字個數的多項式，並且空間複雜度是輸入規模（而非數字個數）的多項式，則這個算法是 強多項式時間 的。由於算術操作在一般的計算模型下可以在輸入規模（即數字大小的對數）的多項式時間內完成，強多項式時間的算法一定是多項式時間的。

一般來説，強多項式時間的算法的時間複雜度與值域無關。

Weakly polynomial time 弱多項式時間

如果一個算法是多項式時間的但不是強多項式時間的，則它是 弱多項式時間 的。

例如，計算最大公約數的歐幾里得算法，時間複雜度為 \(O(\log a + \log b)\)（\(a\) 和 \(b\) 為輸入的數的大小），是弱多項式時間的。

Pseudo-polynomial time 偽多項式時間

如果一個算法的用時是值域的多項式，則稱它是 偽多項式時間 的。偽多項式時間的算法可能是多項式時間的也可能不是，可能不是多項式時間是因為表示一個大小為 \(n\) 的正整數一般只需要 \(O(\log n)\) 個二進制位，所以關於值域多項式時間的算法往往關於輸入長度是指數級時間的。雖然從定義上來説偽多項式時間也可能是多項式時間，但當我們説一個算法是偽多項式時間的，一般都是説這個算法不是多項式時間的。

例如，揹包問題是 NP-hard 問題，但它有基於動態規劃的偽多項式時間的解法。

如果一個 NPC/NP-hard 問題有偽多項式時間的解法，則稱這個問題是 弱 NPC/弱 NP-hard 問題。如果一個 NPC/NP-hard 問題在 \(\mathsf{P} \ne \mathsf{NP}\) 的前提下沒有偽多項式時間的解法，則稱這個問題是 強 NPC/強 NP-hard 問題。

可構造函數

時間可構造函數

有時，我們想讓圖靈機知道自己用了多長的時間，例如，強制圖靈機在進行 \(T(n)\) 步計算後停機。但如果計算 \(T(n)\) 的用時就超過了 \(T(n)\)，這便是不可做到的。為此，定義了時間可構造函數，來避免這樣的麻煩。

如果存在圖靈機 \(M\)，使得輸入為 \(1^n\)(\(n\) 個 1) 時 \(M\) 能在 \(O(f(n))\) 的時間內停機並且輸出 \(f(n)\) 的二進制表示（注意，這裏的圖靈機的輸出不是接受/不接受，而是一個串，輸出可以在紙帶上進行），則 \(f(n)\) 是一個 時間可構造函數。

由於讀入需要 \(O(n)\) 的時間，\(o(n)\) 的非常值函數都不是時間可構造函數。

空間可構造函數

類似地可以定義空間可構造函數。

如果存在圖靈機 \(M\)，使得輸入為 \(1^n\)(\(n\) 個 1) 時 \(M\) 能在 \(O(f(n))\) 的空間內停機並且輸出 \(f(n)\) 的二進制表示，則 \(f(n)\) 是一個 空間可構造函數。

複雜度類之間的關係

時間譜系定理

確定性時間譜系定理

若 \(f(n)\) 是一個時間可構造函數，則：

\[ \mathsf {DTIME}\left(o\left({\frac {f(n)}{\log f(n)}}\right)\right)\subsetneq \mathsf {DTIME}(f(n)) \]

由確定性時間譜系定理可以得到 \(\mathsf{P}\subsetneq\mathsf{EXPTIME}\)。

確定性時間譜系定理的證明

定義語言 \(L=\{(x, y)|\mathcal{U}((x, y), x)\text{ 在 }f(|x|+|y|)\text{ 時間內停機並拒絕}\}\)，由於 \(f(n)\) 是一個時間可構造函數，可以根據定義進行計算來判定 \(L\)，用時為 \(O(f(|x|+|y|))\)，所以 \(L\in\mathsf{DTIME}(f(n))\)。

現在假設 \(L\in\mathsf{DTIME}(o\left({\dfrac {f(n)}{\log f(n)}}\right))\)，設 \(M_z\) 就是那台在 \(o\left({\dfrac {f(n)}{\log f(n)}}\right)\) 的時間內判定 \(L\) 的圖靈機。

令通用圖靈機 \(\mathcal{U}(x, z)\) 關於 \(x\) 的用時為 \(g(|x|)\)，由上文關於通用圖靈機的介紹可以得到 \(g(n)=o(f(n))\)，所以，當 \(y\) 足夠大時，\(g(|z|+|y|)<f(|z|+|y|)\)。

令 \(y'\) 是一個足夠大的 \(y\)，那麼 \(\mathcal{U}((z, y'), z)\) 一定能在 \(f(|z|+|y'|)\) 時間內停機，從而 \(M_z(z, y')\ne M_z(z, y')\)，產生矛盾，所以假設不成立，確定性時間譜系定理證畢。

非確定性時間譜系定理

若 \(g(n)\) 是一個時間可構造函數，並且 \(f(n+1)=o(g(n))\)，則 \(\mathsf{NTIME}(f(n))\subsetneq\mathsf{NTIME}(g(n))\)。

由非確定性時間譜系定理可以得到 \(\mathsf{NP}\subsetneq\mathsf{NEXPTIME}\)。

空間譜系定理

若 \(f(n)\) 是一個空間可構造函數且 \(f(n)=\Omega(\log n)\)，則 \(\mathsf{SPACE}(o(f(n)))\subsetneq\mathsf{SPACE}(f(n))\)。

其中 \(\mathsf{SPACE}\) 可以代指 \(\mathsf{DSPACE}\) 或 \(\mathsf{NSPACE}\)。

由空間譜系定理可以得到 \(\mathsf{PSPACE}\subsetneq\mathsf{EXPSPACE}\)。

薩維奇定理

一台確定性圖靈機可以在一台非確定性圖靈機所消耗空間的平方內模擬它（儘管消耗的時間可能多很多），即：

若 \(f(n)=\Omega(\log n)\)，則：

\[ \mathsf{NSPACE}\left(f\left(n\right)\right)\subseteq \mathsf {DSPACE}\left(\left(f\left(n\right)\right)^2\right) \]

推論：\(\mathsf{PSPACE}=\mathsf{NPSPACE}\)，\(\mathsf{EXPSPACE}=\mathsf{NEXPSPACE}\)。

P?=NP

複雜度類 \(\mathsf{P}\) 與 \(\mathsf{NP}\) 是否相等是計算複雜度理論中一個著名的尚未解決的問題。

若 \(\mathsf{P}=\mathsf{NP}\)，可以得到 \(\mathsf{NP}=\mathsf{co-NP}\)，但反之不行（目前沒有基於 \(\mathsf{NP}=\mathsf{co-NP}\) 證明 \(\mathsf{P}=\mathsf{NP}\) 的方法）。

為什麼 NP?=co-NP 不是顯然的？

由於 \(\mathsf{NP}\) 問題和與其對應的 \(\mathsf{co-NP}\) 問題答案相反，很容易有這種想法：對於一個 \(\mathsf{co-NP}\) 問題，我只要將解決其補集的非確定性圖靈機的輸出反過來，就解決了該 \(\mathsf{co-NP}\) 問題，所以 \(\mathsf{NP}=\mathsf{co-NP}\)。

實際上，上面所説的這種方法確實能夠解決該 \(\mathsf{co-NP}\) 問題，但並沒有找到一個非確定性圖靈機來解決它：如果一個圖靈機所做的事情是將一個非確定性圖靈機的輸出反過來，該圖靈機並不是一個非確定性圖靈機。因為，非確定性圖靈機接受是在某個分支處接受，而拒絕是在所有分支處拒絕；而將其輸出反過來，就變成了接受是在所有分支處，而拒絕是在一個分支處，而這樣就不符合非確定性圖靈機的定義了，所以能用該圖靈機解決這個 \(\mathsf{co-NP}\) 問題並不能使這個 \(\mathsf{co-NP}\) 問題變成一個 \(\mathsf{NP}\) 問題。

若 \(\mathsf{P}=\mathsf{NP}\)，還可以得到 \(\mathsf{EXPTIME}=\mathsf{NEXPTIME}\)。

若 \(\mathsf{P}\ne\mathsf{NP}\)，可以得到 NP-intermediate 不為空。

參考資料

  1. 計算複雜性（1）Warming Up: 自動機模型；

  2. 計算複雜性（2）圖靈機計算模型；

  3. Wikipedia 的相關詞條以及這些詞條的參考資料。

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用