主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公English
2022年专刊出版计划 微信服务介绍 最新一期:2021年第2期
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
白 硕,卜东波.2-3-SAT问题相变现象剖析及其应用.软件学报,1998,9(11):828-832
2-3-SAT问题相变现象剖析及其应用
Analysis for Phase Transition of the 2-3-SAT Problem
投稿时间:1997-03-11  修订日期:1997-11-10
DOI:
中文关键词:  NP完全问题,合取范式,SAT问题,相变现象,可满足概率,2-3-当量.
英文关键词:SAT problem, 2-3-SAT, phase transition, 2-3-ratio, constraint power.
基金项目:本文研究得到国家863高科技项目基金资助.
作者单位
白 硕 国家智能计算机研究开发中心,北京,100080
北京曙光信息技术产业公司,北京,100080 
卜东波 国家智能计算机研究开发中心,北京,100080
北京曙光信息技术产业公司,北京,100080 
摘要点击次数: 3678
全文下载次数: 3159
中文摘要:
      3-SAT问题有一个非常奇妙的相变现象.对于固定的变量数N,合取范式的可满足概率随着子句个数K的变化而发生剧烈的变化;当K≈4.3*N 时,可满足概率急剧地从1变为0.相变现象决定了问题的难易分布,对于快速求解算法的设计有着非常重要的意义.文章着重讨论了SAT问题的更一般形式,即2-3-SAT问题的相变现象.研究了相变点处的2-子句和3-子句个数的关系,发现了2-子句和3-子句在约束能力意义下的当量关系,并提出了如何有效地利用2-3-SAT的相变现象.
英文摘要:
      There exists a very interesting feature in SAT(satisfiability) problem. With a fixed numbers of variables, the satifactory probability of an SAT instance change sharply from 1 to 0 while the number of clauses increasing, and the phase transition point is estimated to be K≈4.3*N. The phase transitions are of great importance to the efficient algorithms designing to solve the SAT problem. More generally, the phase transition of 2-3-SAT problem was discussed in this paper. The analysis of the location of the phase transition point of 2-3-SAT shows that there is an linear ratio between a 2-clause and a 3-clause in the sense of the constraint power which could help to design a more powerful heuristic for algorithms designing.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器
 

京公网安备 11040202500064号

主办单位:中国科学院软件研究所 中国计算机学会 京ICP备05046678号-4
编辑部电话:+86-10-62562563 E-mail: jos@iscas.ac.cn
Copyright 中国科学院软件研究所《软件学报》版权所有 All Rights Reserved
本刊全文数据库版权所有,未经许可,不得转载,本刊保留追究法律责任的权利