高级检索
约束满足问题（constraint satisfaction problem, CSP）是计算机科学关注的一类基本的计算问题。例如经典的可满足性判定（SAT）问题——这一人类已知的首个NP完全问题，即是约束满足问题的一个特例。约束满足解空间的几何性质，关系到与约束满足问题相关的诸多计算问题的计算复杂性。在本次讲座中，我们将介绍：作为约束满足问题解的存在性的充分条件“Lovasz局部引理”、约束满足解空间的连通性、以及对约束满足解的快速采样算法之间的联系。
解空间
尹一通