Logic in Computer Science (LICS 1997)

Paper: Complexity of Power Default Reasoning (at LICS 1997)

Authors: Guo-Qiang Zhang William C. Rounds

Abstract

This paper derives a new and surprisingly low complexity result for inference in a new form of Reiter's propositional default logic. The problem studied here is the "default inference problem" whose fundamental importance was pointed out by Kraus, Lehmann, and Magidor. We prove that ``normal'' default inference, in propositional logic, is a problem complete for co-NP(3), the third level of the so-called Boolean hierarchy. Our result (by changing the underlying semantics) contrasts favorably with a similar result of Gottlob, who proves that standard default inference is complete for the second level of the polynomial hierarchy. Our inference relation also obeys all of the laws for preferential consequence relations set forth by Kraus, Lehmann, and Magidor. In particular, we get the property of being able to reason by cases and the law of cautious monotony. Both of these laws fail for standard propositional default logic.The key technique for our results is the use of Scott's domain theory to integrate defaults into partial model theory of the logic, instead of keeping defaults as quasi-proof rules in the syntax. In particular, reasoning disjunctively entails using the Smyth powerdomain.

BibTeX

  @InProceedings{ZhangRounds-ComplexityofPowerDe,
    author = 	 {Guo-Qiang Zhang and William C. Rounds},
    title = 	 {Complexity of Power Default Reasoning},
    booktitle =  {Proceedings of the Twelfth Annual IEEE Symp. on Logic in Computer Science, {LICS} 1997},
    year =	 1997,
    editor =	 {Glynn Winskel},
    month =	 {June}, 
    pages =      {328--339},
    location =   {Warsaw, Poland}, 
    publisher =	 {IEEE Computer Society Press}
  }