CC（複雑さ）

計算複雑性理論において、CC (比較回路)は、多項式サイズの比較回路によって解決できる決定問題を含む複雑性クラスです。

コンパレータ回路は、各コンパレータ ゲートが方向付けられ、各ワイヤが入力変数、その否定、または定数で初期化され、ワイヤの 1 つが出力ワイヤとして区別される ソート ネットワークです。

CCにとって完全な最も重要な問題は、安定結婚問題の決定変種です。

意味

単一のコンパレータ ゲート。

コンパレータ回路は、配線とゲートのネットワークです。各コンパレータゲートは、2本の配線を接続する有向エッジであり、2つの入力を受け取り、それらをソートされた順序で出力します（大きい方の値がエッジが指している配線に出力されます）。各配線への入力は、変数、その反転、または定数のいずれかです。配線の1つは出力配線として指定されます。回路によって計算される関数は、入力変数に従って配線を初期化し、コンパレータゲートを順番に実行し、出力配線に渡される値を出力することで評価されます。

比較回路値問題（CCVP）は、比較回路の符号化と入力が与えられた場合に、比較回路を評価する問題である。計算量クラスCCは、CCVPに対数空間帰着可能な問題のクラスとして定義される^{[ 1 ]}。同等の定義^{[ 2 ]}は、CCVPにAC ⁰帰着可能な問題のクラスである。

例として、ソート ネットワークを使用して、中央のワイヤを出力ワイヤとして指定することで、多数決を計算することができます。

中央の配線を出力として指定し、各配線に16個の異なる入力変数を付与すると、結果として得られるコンパレータ回路は多数決を計算します。AC 0 で構築できるソーティングネットワークが存在するため、多数決関数は CC にあることが^わかります。

CC完全問題

CCの問題がCC完全であるとは、CCのすべての問題が対数空間帰着を用いてその問題に帰着できる場合を言う。比較回路値問題 (CCVP) はCC完全である。

安定した結婚問題では、男性と女性の数が同数です。各人が異性のメンバー全員を順位付けします。男性と女性の間のマッチングは、現在のパートナーよりもお互いを好む未ペアの男性と女性が存在しない場合に安定します。安定したマッチングは常に存在します。安定したマッチングの中には、各女性がこれまでのどの安定したマッチングでも得られた中で最高の男性を得るものがあります。これは、女性最適な安定マッチングとして知られています。安定したマッチング問題の決定バージョンは、すべての男性と女性の順位が与えられた場合に、特定の男性と特定の女性が女性最適な安定マッチングでマッチングされるかどうかです。古典的な Gale–Shapley アルゴリズムはコンパレータ回路として実装できませんが、 Subramanian ^{[ 3 ]}は問題がCCにあることを示す別のアルゴリズムを考案しました。この問題はまたCC完全です。

CC完全であるもう一つの問題は、辞書式順序優先最大マッチングである。^{[ 3 ]}この問題では、頂点に順序があり、辺が1つある二部グラフが与えられる。辞書式順序優先最大マッチングは、最初の二部グラフの頂点を、2番目の二部グラフの最小頂点に順にマッチングさせることで得られる。この問題は、与えられた辺がこのマッチングに属するかどうかを問うものである。

スコット・アーロンソンは、小石モデルがCC完全であることを示した。^{[ 4 ]}この問題では、（単項でエンコードされた）小石の初期数と、サイズ と の 2 つの山を結合してサイズ の新しい山を得るか、サイズ の山をサイズと の山に分割するかの 2 種類の命令のみを含むプログラムの記述が与えられる。問題は、プログラムを実行した後、特定の山に小石が存在するかどうかを判断することである。彼はこれを使用して、 Digi-Comp II のようなデバイスでボールが指定されたシンク頂点に到達するかどうかを判断する問題もCC完全であることを示した。 ${\displaystyle y}$ ${\displaystyle z}$ ${\displaystyle y+z}$ ${\displaystyle y}$ ${\displaystyle \lceil y/2\rceil }$ ${\displaystyle \lfloor y/2\rfloor }$

封じ込め

コンパレータ回路の評価問題は多項式時間で解けるため、CCはPに含まれる（「回路の普遍性」）。一方、コンパレータ回路は有向到達可能性を解くことができるため^{[ 3 ]}、CCはNLを含む。CCとNCが比較不可能な相対化された世界が存在するため^{[ 2 ]}、両方の包含関係は厳密である。

参考文献

1. EW Mayr; A. Subramanian (1992). 「回路値の複雑性とネットワーク安定性」 . Journal of Computer and System Sciences . 44 (2): 302– 323. doi : 10.1016/0022-0000(92)90024-d .
2. S. A. Cook; Y. Filmus; DTM Le (2012). 「コンパレータ回路値問題の複雑さ」arXiv : 1208.2721 [ cs.CC ].
3. A. Subramanian (1994). 「安定マッチング問題への新しいアプローチ」SIAM Journal on Computing . 23 (4): 671– 700. doi : 10.1137/s0097539789169483 .
4. Aaronson, Scott (2014年7月4日). 「Digi-Comp IIのパワー」 . Shtetl-Optimized . 2014年7月28日閲覧。

外部リンク

• 複雑性動物園： CC