2-satisfiability

寻找强连通分量的算法可以用来解决2-SAT（英语：2-satisfiability）问题（由带有对于变量对的值的限制的布尔变量构成的系统）：如Aspvall, Plass & Tarjan (1979) harvtxt模板錯誤: 多個指向目標 (2個): CITEREFAspvallPlassTarjan1979

Zecchina, R. Survey propagation: An algorithm for satisfiability. Random Structures & Algorithms. 2005, 27 (2): 201–226. doi:10.1002/rsa.20057.  Pearl, Judea

差分密碼分析已經被IBM和美國國家安全局（NSA）所知曉並被保密。 薩莫爾還對密碼學以外的計算機科學做出貢獻，例如找到第一個2-可滿足性（英语：2-satisfiability）的線性時間算法，並展示PSPACE和IP（英语：IP (complexity)）的複雜性類別的等價性。 薩莫爾獲得許多獎項，包括：

NP。 當一個決定性問題的解能在多項式時間內被驗證時，則稱此問題落在NP 的集合中。 滿足問題 (satisfiability problem，簡稱 SAT)，就是一個NP中的典型問題。 令 x 1，x 2，…，x n 代表布林變數(boolean variables)(其值非真(true)即假(false)的變數)。令-xi

存在几个已知的NL-完全问题，如2SAT（英语：2-satisfiability）。 根据萨维奇定理，我们已知有以下重要性质： N L ⊆ S P A C E ( log 2 ⁡ n )         equivalently,  N L ⊆ L 2 . {\displaystyle \mathrm