2 – 适定性问题 2 Satisfiability

「OI」2-SAT

$\texttt{SAT}$ 是适定性(Satisfiability)问题的简称。一般形式为 $\texttt{k}$ – 适定性问题,简称 $\texttt{k-SAT}$。而当 $\texttt{k}>2$ 时该问题为 NP 完全的。所以我们只研究 $\texttt{k}=2$ 的情况。

Continue reading…