可滿足性問題相變研究綜述

摘要： 約束滿足問題（CSP）是理論計算機科學領域的組合優(yōu)化問題，可滿足性問題（SAT問題）作為CSP中的一種特殊情形，是理論計算機科學、數(shù)理邏輯和人工智能等領域十分關注的熱點問題。相變是SAT問題中存在的一種現(xiàn)象，而研究SAT問題的相變現(xiàn)象和相變機制對深入認識SAT問題的難解本質和一般數(shù)學現(xiàn)象以及設計更高效的算法求解SAT問題有重要的指導意義。因此，根據(jù)近年來國內(nèi)外學者針對SAT問題... （共10頁）