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

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