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

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

研究了基于全序划分模型的开放逻辑的计算复杂性 .证明了 :在考虑一般公式的情形下判定一个公式是否被重构所蕴涵是Π 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.