Top / Circuit SAT

Circuit SAT

目次 †

Circuit SAT †

　Circuit SAT（circuit satisfiability）とは、SAT（論理式の充足可能性問題）の回路版である。出力が1になるような入力が存在するときに、その回路をCircuit SATという。

「C(w)=1」⇒「C∈Circuit SAT」

　与えられた回路がCircuit SATであるかどうかを調べるのは困難である。入力がn個ある場合、総当りで調べるならば2n回調べなければならない。これでは多項式時間内に終わらない。

Circuit SATとNP完全 †

[定理]
Circuit SATはNP完全である。

[考察]直観的にはCircuit SATであるかどうかを調べる効率的な方法はないということ。

[証明]Circuit SATが、NPに多項式還元できることを示す。

　A：NP言語と仮定する。
　Aは多項式時間検証者（poly-time verifier）であるアルゴリズムVを持つ。Vはいくつかのyに対して<x,y>をacceptするときだけ、x∈Aになるという性質を持つ。

　さらに、poly-size circuitであるCはVと等価という事実がある。Cの入力（x,y）はちょうどVの入力に対応している。そして、xとyの長さを与えるpoly time内で、Cは構築できる。

　よって、Circuit SATのインスタンスがNPのインスタンスに変換できた。

[定理]
すべてのNP完全問題はCircuit SATに帰着できる。

[考察]NP完全問題はSATに帰着できる。SATはCircuit SATに帰着できる。

Circuit SATと暗号理論 †

　Circuit SAT問題（NP完全問題）を利用して、次の暗号プロトコルを作ることができる。

• NIZK proof
  • 入力値をwitnessとし、証明者に与えられる。
  • 任意のcircuit CはNANDゲートだけで構成されるので、NANDゲートだけを考えるとよい。
  • NANDゲートの入力2つと出力1つの値をcommitment schemeで隠して、検証者に送る。これによりZK性を満たす。
  • ペアリングを持たせると、commitment情報のまま正しく計算したという証明を検証できる。
• NIZK argument