NP完全問題
変数の集合 X = { x 1 , ... , x n } {\displaystyle X=\{x_{1},\ldots ,x_{n}\}} 上のクローズ C 1 , ... , C k {\displaystyle C_{1},\ldots ,C_{k}} の集合が与えられる。これらすべてを充足する変数への真偽割り当ては存在するか?という問題。英語表記の最初の三文字をとってSATともいう。クローズの長さを3に制限した3-SATもNP完全であることが知られている。ある問題がNP完全であることを示そうとするとき、リダクションによく使われる問題である。