CC (複雑さ)

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

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

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

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

比較回路値問題 (CCVP) は、比較回路のエンコードと回路への入力が与えられた場合に比較回路を評価する問題です。複雑度クラスCCは、CCVP に対数空間還元可能な問題のクラスとして定義されます。^[1]同等の定義^{[2]は、CCVP に還元可能な}AC ⁰の問題のクラスです。

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

中央のワイヤが出力として指定され、ワイヤに 16 個の異なる入力変数が注釈されている場合、結果として得られるコンパレータ回路は多数決を計算します。AC 0 で構築できるソート ネットワークがあるため、^多数決関数はCCにあることがわかります。

CCの問題がCC完全であるのは、 CC内のすべての問題が対数空間削減を使用してその問題に削減できる場合です。比較回路値問題 (CCVP) はCC完全です。

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

CC完全な別の問題は、辞書式優先最大マッチングです。^[3]この問題では、頂点に順序があり、辺が1 つある 2 部グラフが与えられます。辞書式優先最大マッチングは、最初の 2 分割の頂点を 2 番目の 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]両方の包含は厳密です。

• 複雑性動物園: CC