SAT
SAT
NP完全問題の一つとして命題論理式の充足可能問題（SAT）という問題が知られています。その例として、
「次のような論理式の出力を１とするような入力$ x_1, x_2 \in {0, 1} が存在するか？」という問題を考えます。
$ (x_1∨x_2)∧(x _1∨¬x _2)∧(¬x _1∨¬x _2)
上式の入力を$ x_1= 1, x_2 = 0x_1=1,x_2=0とすることでこの論理式の解は１となり、条件を満たす入力が存在することの判定ができます。
Circuit-SAT
SATの命題論理式を演算回路に変換した問題がCircuit-SATです。
これは「演算回路$ Cが与えられた時、回路の出力を$ 1とする入力が存在するか？」というNP完全性を持つ問題です
イメージとしては、命題論理式から加算や乗算ゲートから成る回路へと変換された充足性問題です。
$ xをステートメント、$ nを証拠とすると関係$ R:= {(x,w)\in \mathbb{F^n} × \mathbb{F^h}}となり
この関係$ Rは演算回路$ Cで検証できるので、$ (x, w) \in \mathcal{R}(x,w)となるとき、$ f(x, w) = 1となる算術関数$ fがあり、入力が関数$ fを満たす場合には演算回路の出力が$ 1、そうでない場合は出力が$ 0となることを意味します。
$ f(x,w)=\Bigg\lbrace\begin{array}{c} 1∀(x,w)∈R\\0∀(x,w)∈R\end{array}