3SAT.

3SAT.， 或者布尔可满足问题是一个问题，询问什么是算法在布尔代数（具有未知数量的变量数量）中识别给定的公式是什么是满足的，即，是否存在变量（二进制）值的某些组合将给出1。

例如，公式“A + 1”是满足的，因为A是0或1，结果始终为1（“+”在这里意味着“二进制或”，如常规在布尔代数中）。公式“A * B”也是满意的，因为如果A和B都是1.然而，结果是一个，则，公式“A * 0”是不可满意的，因为，无论a是什么，结果总是零。

有许多快速算法来解决这个问题;然而，它们中的每一个在最坏的情况下以指数时间（相对于公式长度）运行。即使对于最佳算法，“指数时间假设”也是如此。如果这是真的，这意味着p = np是不正确的（并且证明假设会让你成为一个大奖）;但是，即使P = NP不是真的，那并不意味着指数时间假设是真的。

3SAT和Boolean可满足性问题实际上不是完整的同义词。3SAT询问是否有可能解决布尔满足性问题，条件是在布尔公式中的每对括号之间存在最多3个变量。因此，这是一个更简单的问题，但仍然没有算法可以解决既始终正确（不启发式），并且始终在少于指数时间内运行。