基于全序划分模型的开放逻辑的计算复杂性  

THE COMPLEXITY OF OPEN LOGIC BASED ON TOTAL-ORDERED PARTITION MODEL

作　　者：王淞昕[1] 刘大有[2] 

机构地区：[1]吉林大学计算机科学与技术学院,长春130012 [2]吉林大学符号计算与知识工程重点实验室,长春130012

出　　处：《计算机研究与发展》2002年第10期1244-1247,共4页Journal of Computer Research and Development

基　　金：国家自然科学基金 ( 6 0 1 730 0 6 );国家"八六三"高技术研究发展计划基金 ( 2 0 0 1 AA1 1 51 6 0 )资助

摘　　要：研究了基于全序划分模型的开放逻辑的计算复杂性 .证明了 :在考虑一般公式的情形下判定一个公式是否被重构所蕴涵是Π p2 完全的 ;如果限制到考虑 Horn公式的情形 ,则为 co-NP完全的 .由此表明 ,从计算复杂性角度来说 ,该判定问题在一般情形下比经典逻辑中的演绎推理问题更难 ,在 Horn公式情形下则和经典逻辑中的演绎推理问题难度相当 .假定 P≠ NP。The complexity of open logic based on total-ordered partition model is studied. It is proved that the complexity of deciding if a sentence is implied by the reconstruction is Πp 2-complete in general case, and becomes co-NP-complete when restricted to Horn formula. This result indicates that the problem is harder than and equivalent to the derivability problem in classic logic and in Horn formula respectively, and that there are no polynomial time algorithms in both cases.

关 键 词：全序划分模型 开放逻辑 计算复杂性 

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