憑證 (複雜度)

在計算複雜性理論中，憑證（也稱為見證）是一個字串，它能證實一個計算的答案，或證實某個字串屬於一個語言。憑證通常被視為驗證過程中的一個解法路徑，用來檢查一個問題的答案是「是」還是「否」。

在計算的決策樹模型中，憑證複雜度是指，為了明確確定布林函數 f 的值，決策樹的 n 個輸入變數中，最少需要被賦值的變數數量。

用於定義

憑證的概念被用來定義半可判定性：一個形式語言 L 是半可判定的，若且唯若存在一個二元謂詞關係 R \subseteq \Sigma^* \times \Sigma^*，其中 R 是可計算的，並且對於所有 x \in \Sigma^* 滿足：

   x ∈ L ⇔ 存在 y 使得 R(x, y) 成立

憑證也為一些複雜度類別提供了定義，這些類別也可以用非確定性圖靈機來描述。一個語言 L 屬於 NP，若且唯若存在一個多項式 p 和一個多項式時間有界圖靈機 M，使得對於每個字 x \in \Sigma^*，x 屬於語言 L 的充分必要條件是，存在一個長度最多為 p(|x|) 的憑證 c，使得 M 接受配對 (x, c)。co-NP 類別的定義與此相似，差別在於憑證是用來證明字不屬於該語言。

NL 類別有一個憑證定義：屬於該語言的問題有一個多項式長度的憑證，此憑證可由一個確定性對數空間有界圖靈機驗證，該圖靈機對憑證的每個位元只能讀取一次。或者，上述陳述中的確定性對數空間圖靈機可以被一個有界錯誤機率性常數空間圖靈機取代，該圖靈機只允許使用常數數量的隨機位元。

範例

對於一個給定的圖 G 和數字 k，判斷該圖是否包含一個大小為 k 的獨立集的問題，屬於 NP。對於語言中的一個配對 (G, k)，其憑證是一個由 k 個頂點組成的集合，這些頂點兩兩不相鄰（因此構成一個大小為 k 的獨立集）。

一個更普遍的例子是判斷一台給定的圖靈機是否在特定步數內接受一個輸入，如下所示：

 L = {<<M>, x, w> | <M> 是否在 |w| 步內接受 x？}
 證明 L ∈ NP。
 驗證者：
   取得字串 c = <M>, x, w，使得 |c| <= P(|w|)
   檢查 c 是否為 M 在 x 上，於最多 |w| 步內的一個接受計算

   如果我們有一個圖靈機的 k 步計算，其計算字串的總大小為 k2
   因此，<<M>, x, w> ∈ L ⇔ 存在 c <= a|w|3 使得 <<M>, x, w, c> ∈ V ∈ P

參見

• 見證 (數學)，數理邏輯中的一個類似概念

外部連結

• .
• 《計算複雜性：現代方法》，作者 Sanjeev Arora 與 Boaz Barak

Category:計算複雜性理論