NC（複雑性）

コンピュータサイエンスにおける未解決問題

⁠${\displaystyle {\mathsf {NC}}{\overset {?}{=}}{\mathsf {P}}}$⁠

コンピュータサイエンスにおける未解決問題

計算複雑性理論において、クラスNC (「ニックのクラス」の略) は、多項式数のプロセッサを持つ並列コンピュータ上で多対数時間で決定可能な決定問題の集合です。言い換えれば、入力サイズnの問題は、 O ( n ^k )個の並列プロセッサを使用してO ((log n ) ^c )の時間で解ける定数cとkが存在する場合にNCに属します。Stephen Cook ^{[ 1 ] [ 2 ]}は、多対数深さと多項式サイズの回路について広範な研究^{[ 3 ]}を行ったNick Pippengerにちなんで「ニックのクラス」という名前を付けました。 ^{[ 4 ]}回路複雑性理論の場合と同様に、通常、このクラスには回路ファミリーが均一でなければならないという追加の制約があります(下記参照)。

クラスP が扱いやすい問題 (コブハムのテーゼ)とみなせるのと同様に、 NC は並列コンピュータで効率的に解ける問題とみなせる。^{[ 5 ]} NCはPの部分集合である。なぜなら、多項式時間並列計算は多項式時間逐次計算でシミュレートできるからである。NC = Pかどうかは不明だが、ほとんどの研究者はこれが偽であると推測しており、つまり、おそらく「本質的に逐次的」で並列化を使用しても大幅に高速化できない扱いやすい問題がいくつか存在する。クラスNP 完全が「おそらく扱いにくい」とみなせるのと同様に、クラスP 完全は、NC還元を使用する場合、「おそらく並列化できない」または「おそらく本質的に逐次的」とみなせる。

定義における並列コンピュータは、並列ランダムアクセスマシン（PRAM）であると想定できます。これは、中央にメモリプールを持つ並列コンピュータであり、どのプロセッサも任意のメモリビットに一定時間でアクセスできます。NCの定義は、PRAMが複数のプロセッサによる単一ビットへの同時アクセスをどのように処理するかによって影響を受けません。PRAMはCRCW、CREW、またはEREWのいずれかを選択できます。これらのモデルの説明については、 PRAMの項を参照してください。

同様に、NCは、多項式深さと多項式数のゲートを持ち、最大ファンインが2である均一ブール回路（入力の長さから計算可能。NCの場合、nの対数空間でサイズnのブール回路を計算できると仮定する）によって決定可能な決定問題として定義できる。

RNCは、ランダム性へのアクセス権限を持つNCを拡張したクラスです。

Pと同様に、少し言葉の濫用ではあるが、関数問題や探索問題もNCに分類できるかもしれない。NCには、以下のような多くの問題が含まれることが知られている。

• 整数の加算、乗算、除算。
• 行列の乗算、行列式、逆行列、ランク。
• シルベスター行列を用いた線形代数への還元による多項式の最大公約数
• 最大一致を見つける。

多くの場合、これらの問題に対するアルゴリズムは個別に考案する必要があり、よく知られたアルゴリズム（ガウス消去法やユークリッドの互除法など）を単純に適用することはできませんでした。リップルキャリー加算器とキャリー先読み加算器を比較してみるとよいでしょう。

NC ⁱは、最大 2 つの入力と深さO ((log n ) ⁱ )の多項式数のゲートを持つ均一ブール回路によって決定可能な決定問題のクラス、または多項式数のプロセッサを持つ並列コンピュータで時間O ((log n ) ⁱ ) で解ける決定問題のクラスです。明らかに、

$\displaystyle {\mathsf {NC}}^{0}\subseteq {\mathsf {NC}}^{1}\subseteq \cdots \subseteq {\mathsf {NC}}^{i}\subseteq \cdots \subseteq {\mathsf {NC}}}$

これはNC階層を形成する。

最小のクラスであるNC ⁰は、一定の深さと制限されたファンインを持つブール回路によって定義可能な関数のクラスです。

次に小さいクラスであるNC ¹は、多項式サイズの有界ファンイン回路（幅 4 以下）で解けるすべての問題の集合であるBW ₄ ⁰に等しい。これは、均一な場合と非均一な場合の両方に当てはまる（DLOGTIME 均一性で十分）。^{[ 7 ] : 142}

NCクラスは、空間クラスL、 SL、^{[ 7 ] : 137} NL、^{[ 8 ]} LOGCFL、およびAC ^{[ 9 ]}と関連付けることができます。

${\displaystyle {\mathsf {NC}}^{1}\subseteq {\mathsf {L}}={\mathsf {SL}}\subseteq {\mathsf {NL}}\subseteq {\mathsf {LOGCFL}}\subseteq {\mathsf {AC}}^{1}\subseteq {\mathsf {NC}}^{2}.}$

NC クラスは AC クラスと関連しており、同様に定義されますが、ゲートのファンインは無制限です。各iについて、^{[ 5 ] [ 9 ] [ 10 ]}

${\displaystyle {\mathsf {NC}}^{i}\subseteq {\mathsf {AC}}^{i}\subseteq {\mathsf {AC}}^{i}[p]\subseteq {\mathsf {ACC}}^{i}\subseteq {\mathsf {TC}}^{i}\subseteq {\mathsf {NC}}^{i+1}}$

このことから、NC = AC となる。^{[ 11 ]}

また、${\displaystyle {\mathsf {NC}}^{0}\subsetneq {\mathsf {AC}}^{0}\subsetneq {\mathsf {ACC}}^{0}}$[ ^{5 ]​}

同様に、NCは、各ステップで最大 2 つのオプションに制限された交代チューリング マシンで解決可能な問題と同等であり、 O (log n ) の空間と${\displaystyle (\log n)^{O(1)}}$交替。^{[ 12 ]}

大きな未解決問題である$\displaystyle {\mathsf {TC}}^{0}\subsetneq {\mathsf {NC}}^{1}}$（Vollmer 1998 、p. 126）。重要な部分的結果によれば、あるいくつかのものが存在するならば、 ${\displaystyle \epsilon >0}$、そして問題は$\displaystyle {\mathsf {NC}}^{1}}$少なくとも${\displaystyle \Omega (n^{1+\epsilon })}$ゲートイン$\displaystyle {\mathsf {TC}}^{0}}$すると、これはブートストラップして超多項式ゲートを必要とするため、$\displaystyle {\mathsf {TC}}^{0}}$[ ^{13 ]​}

未解決問題：NCは適切か？

コンピュータサイエンスにおける未解決問題

ですか${\displaystyle {\mathsf {NC}}}$階層構造は適切か？

コンピュータサイエンスにおける未解決問題

複雑性理論における主要な未解決問題の一つは、 NC階層におけるすべての包含関係が適切であるかどうかである。パパディミトリウは、あるiについてNC ⁱ = NC ^{i +1}ならば、すべてのj ≥ iについてNC ⁱ = NC ^jとなり、結果としてNC ⁱ = NCとなることを指摘した。この指摘は、包含関係の連鎖における単一の等式であっても、NC階層の崩壊として知られている。  

${\displaystyle {\mathsf {NC}}^{1}\subseteq {\mathsf {NC}}^{2}\subseteq \cdots }$

これは、 NC階層全体がレベルiまで「崩壊」することを意味する。したがって、可能性は2つある。

1. $\displaystyle {\mathsf {NC}}^{1}\subsetneq \cdots \subsetneq {\mathsf {NC}}^{i}\subsetneq \cdots \subsetneq {\mathsf {NC}}^{i+j}\subsetneq \cdots {\mathsf {NC}}}$
2. $\displaystyle {\mathsf {NC}}^{1}\subsetneq \cdots \subsetneq {\mathsf {NC}}^{i}=\cdots ={\mathsf {NC}}^{i+j}=\cdots {\mathsf {NC}}}$

（１）が正しいと広く信じられているが、どちらの主張の真偽についてもまだ証明は見つかっていない。

LOGSPACEまたはNC ¹還元の下でNC完全となる問題が存在する場合、 NC階層は崩壊する。^{[ 7 ]： 136}

幅k、長さmのn 個の変数を持つ分岐プログラムは、 m個の命令のシーケンスで構成されます。各命令はタプル ( i , p , q )であり、 iはチェックする変数のインデックス (1 ≤ i ≤ n )、pとqは {1, 2, ..., k } から {1, 2, ..., k } への関数です。数値 1, 2, ..., kは分岐プログラムの状態と呼ばれます。プログラムは最初に状態 1 から開始し、各命令 ( i , p , q ) は、 i番目の変数が 0 か 1かに応じて、状態をxからp ( x ) またはq ( x )に変更します。入力をプログラムの最終状態にマッピングする関数は、プログラムのyieldと呼ばれます(より正確には、入力に対する yield は、任意の初期状態を対応する最終状態にマッピングする関数です)。プログラムは、一連の値を受け取ります。${\displaystyle A\subseteq 2^{n}}$関数のセットがある場合の変数の値${\displaystyle F\subseteq k^{k}}$可変シーケンス${\displaystyle x\in 2^{n}}$収率がFであるとき、それはまさにAにある。

分岐プログラムのファミリーは、各nに対してn 個の変数を持つ分岐プログラムで構成されます。n 個の変数を持つプログラムが、長さ n の入力に制限された言語を受け入れる場合に、この分岐プログラムは言語を受け入れます。

{0,1} 上の任意の言語Lは、幅 5 で指数関数的な長さの分岐プログラムの族、または指数関数的な幅で線形的な長さの族によって認識できることを容易に示すことができる。

{0,1} 上のすべての正規言語は、一定の幅と線形命令数の分岐プログラムのファミリーによって認識できます (DFA は分岐プログラムに変換できるため)。BWBPは、有界幅と多項式長の分岐プログラムのファミリーによって認識可能な言語のクラスを表します。^{[ 15 ]}

バリントンの定理^{[ 16 ]}によれば、BWBPは厳密に非一様NC1^である。証明には対称群S5の_非可解性を用いる。^{[ 15 ]}

この定理はかなり驚くべきものだ。例えば、多数決関数は一定の幅と多項式サイズの分岐プログラムのファミリーによって計算できることを示唆しているが、直感的には、多項式サイズを実現するには線形数の状態が必要になるように思えるかもしれない。

• Arora, Sanjeev ; Barak, Boaz (2009).計算複雑性：現代的アプローチ. Cambridge University Press . ISBN 978-0-521-42426-4. Zbl 1193.68112 . 
• Clote, Peter; Kranakis, Evangelos (2002).ブール関数と計算モデル. 理論計算機科学テキストシリーズ. EATCSシリーズ. ベルリン: Springer-Verlag . ISBN 3-540-59436-1. Zbl 1016.94046 . 
• グリーンロー、レイモンド、ジェームズ・フーバー、ウォルター・ルッツォ。「並列計算の限界；P完全性理論」。 2013年6月4日にWayback Machineにアーカイブ済み。ISBN 0-19-508591-4
• Kozen, Dexter C. (1992).アルゴリズムの設計と分析。講義28～34および36
• コゼン、デクスター C. (2006)。計算理論。コンピューターサイエンスのテキスト。スプリンガー・フェルラーグ。ISBN 1-84628-297-7. Zbl 1102.68025 . 講義12： NCと時間空間クラスの関係
• パパディミトリウ、クリストス（1993）。「第15.3節：クラスNC」。『計算複雑性』 （第1 版）。アディソン・ウェスリー。375 ～ 381ページ。ISBN  0-201-53082-1。
• ストラウビング、ハワード（1994）。有限オートマトン、形式論理、回路複雑性。理論計算機科学の進歩。バーゼル：ビルクハウザー。ISBN 3-7643-3719-2. Zbl 0816.68086 . 
• Vollmer, Heribert (1998).回路複雑性入門：統一的アプローチ. 理論計算機科学テキストシリーズ. ベルリン：Springer-Verlag . ISBN 3-540-64310-9. Zbl 0931.68055 .