极小不可满足公式的两个多项式时间可判定类  

作　　者：赵希顺[1] 丁德成[1] 

机构地区：[1]南京大学数学系,南京210093

出　　处：《中国科学（A辑）》1999年第3期198-206,共9页Science in China(Series A)

基　　金：国家自然科学基金!(批准号 :197710 45 );国家"八六三"计划资助项目

摘　　要：研究命题公式 (合取范式 )的极小不可满足性 .设公式F含有n +k个子句(n是F中所有变元的个数 ) ,其中包括子句x1∨…∨xn 和┐x1∨…∨┐xn,证明了当k≤ 4时 。

关 键 词：极小不可满足 可满足性检查 算法 多项式时间 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]