証明書（複雑さ）

計算複雑性理論では、証明書(証人とも呼ばれる) は、計算の答えを証明する文字列、または言語内の文字列のメンバーシップを証明する文字列です。証明書は、検証プロセス内の解決パスとしてよく考えられており、問題の答えが「はい」か「いいえ」かを確認するために使用されます。

計算の決定木モデルでは、証明書の複雑さは、ブール関数の値を明確に確立するために値を割り当てる必要がある決定木の入力変数の最小数です。 ${\displaystyle n}$ ${\displaystyle f}$

証明書の概念は半決定可能性を定義するために使用されます。^[1]形式言語が半決定可能であるとは、 が 計算可能であり、すべての に対して となるような2項述語関係が存在する場合です。 ${\displaystyle L}$${\displaystyle R\subseteq \Sigma ^{*}\times \Sigma ^{*}}$${\displaystyle R}$${\displaystyle x\in \Sigma ^{*}}$

   x ∈ L ─ R(x, y)となるyが存在する

証明書は、非決定性チューリングマシンの観点から特徴付けることもできるいくつかの複雑性クラスの定義も提供します。言語がNPに属するのは、多項式と多項式時間制限付きチューリングマシンが存在し、そのすべての単語が言語に含まれるのは、ペアを受け入れるような長さが最大である証明書が存在する場合とまったく同じ場合です。^[2]クラスco-NPにも同様の定義がありますが、言語に 含まれない単語の証明書がある点が異なります。${\displaystyle L}$${\displaystyle p}$ ${\displaystyle M}$${\displaystyle x\in \Sigma ^{*}}$${\displaystyle L}$${\displaystyle c}$${\displaystyle p(|x|)}$${\displaystyle M}$${\displaystyle (x,c)}$

NLクラスには証明書の定義があります。言語の問題には多項式長の証明書があり、これは証明書の各ビットを一度だけ読み取ることができる決定論的対数空間制限付きチューリングマシンによって検証できます。^[3]あるいは、上記のステートメントの決定論的対数空間チューリングマシンは、定数個のランダムビットのみを使用できる制限エラー確率定数空間チューリングマシンに置き換えることができます。^[4]

与えられたグラフと数に対して、グラフにサイズの独立集合が含まれているかどうかを判断する問題はNPに属します。言語でペアが与えられた場合、証明書はペアごとに隣接していない頂点の集合（したがって、サイズ の独立集合）です。^[5]${\displaystyle G}$${\displaystyle k}$${\displaystyle k}$${\displaystyle (G,k)}$${\displaystyle k}$${\displaystyle k}$

より一般的な例として、特定のチューリング マシンが特定の数のステップで入力を受け入れるかどうかを判断する問題は次のとおりです。

L = {<<M>, x, w> | <M> は |w| ステップで x を受け入れますか?}
 L∈NPを示します。
 検証者:
   文字列 c = <M>, x, w を取得し、|c| <= P(|w|) を満たす。
   c が最大 |w| ステップの x 上の M の受理計算であるかどうかをチェックする
   |c| <= O(|w| 3 )
   kステップのTM計算がある場合、計算文字列の合計サイズはk 2である。したがって、<<M>, x, w> ∈ L ≤ c <= a|w| 3
   が存在し、<<M>, x, w, c> ∈ V ∈ P

• 証人（数学）、数学論理における類似の概念

• Buhrman, Harry; de Wolf, Ronald (2002)、複雑性測定と決定木の複雑性:調査。
• 計算の複雑さ: 現代的なアプローチ (サンジーヴ・アローラとボアズ・バラク著)