SAT - 国立公園

SAT

boolean satisfiability problem

定義

SATとは充足可能なCNFの集合である

$ \mathrm{SAT} := \{\Phi \in \mathrm{CNF} \ | \ \exists_{\vec{v} \in 2^*} \Phi(\vec{v}) = 1 \}

$ k-SATとは充足可能な$ k-CNFの集合である

$ k\mathrm{SAT} := \{\Phi \in k\mathrm{CNF} \ | \ \exists_{\vec{v} \in 2^*} \Phi(\vec{v}) = 1 \}