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

研究了基于全序划分模型的开放逻辑的计算复杂性 .证明了 :在考虑一般公式的情形下判定一个公式是否被重构所蕴涵是Π p2 完全的 ;如果限制到考虑 Horn公式的情形 ,则为 co-NP完全的 .由此表明 ,从计算复杂性角度来说 ,该判定问题在一般情形下比经典逻辑中的演绎推理问题更难 ,在 Horn公式情形下则和经典逻辑中的演绎推理问题难度相当 .假定 P≠ NP。