2-3-SAT问题相变现象剖析及其应用

作     者：白硕 卜东波 BAI Shuo;BU Dong-bo

作者机构：国家智能计算机研究开发中心 北京曙光信息技术产业公司 

基　　金：国家863高科技项目基金 

出 版 物：《软件学报》 (Journal of Software)

年 卷 期：1998年第9卷第11期

页      码：828-832页

摘      要：３－ＳＡＴ问题有一个非常奇妙的相变现象．对于固定的变量数Ｎ，合取范式的可满足概率随着子句个数Ｋ的变化而发生剧烈的变化；当Ｋ≈４．３＊Ｎ时，可满足概率急剧地从１变为０．相变现象决定了问题的难易分布，对于快速求解算法的设计有着非常重要的意义．文章着重讨论了ＳＡＴ问题的更一般形式，即２－３－ＳＡＴ问题的相变现象．研究了相变点处的２－子句和３－子句个数的关系，发现了２－子句和３－子句在约束能力意义下的当量关系。

主 题 词：NP完全问题 SAT问题 相变现象 计算机 

学科分类：12[管理学] 1201[管理学-管理科学与工程类] 07[理学] 08[工学] 070105[070105] 0835[0835] 0811[工学-水利类] 0701[理学-数学类] 0812[工学-测绘类] 081202[081202] 

核心收录：

D　O　I：10.13328/j.cnki.jos.1998.11.006

馆 藏 号：203702637...