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

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.