Journal of the ACM Bibliography

Georg Gottlob. NP trees and Carnap's modal logic. Journal of the ACM, 42(2):421-457, March 1995. [BibTeX entry]

In this paper we consider problems and complexity classes definable by interdependent queries to an oracle in NP. How the queries depend on each other is specified by a directed graph G. We first study the class of problems where G is a general dag and show that this class coincides with \Delta^P_2. We then consider the class where G is a tree. Our main result states that this class is identical to P^{NP} [O(log n)], the class of problems solvable in polynomial time with a logarithmic number of queries to an oracle in NP. This result has interesting applications in the fields of modal logic and artificial intelligence. In particular, we show that the following problems are all P^{NP} [O(log n)] complete: validity-checking of formulas in Carnap's modal logic, checking whether a formula is almost surely valid over finite structures in modal logics K, T, and S4 (a problem recently considered by Halpern and Kapron [1992]), and checking whether a formula belongs to the stable set of beliefs generated by a propositional theory.

We generalize the case of dags to the case where G is a general (possibly cyclic) directed graph of NP-oracle queries and show that this class corresponds to \Pi^P_2. We show that such graphs are easily expressible in autoepistemic logic. Finally, we generalize our complexity results to higher classes of the polynomial-time hierarchy. Copyright 1995 by ACM, Inc.

The abstract is also available as a LaTeX file, a DVI file, or a PostScript file.

Preliminary version

A preliminary version of these results was presented in: Georg Gottlob. NP trees and Carnap's modal logic. In 34th Annual Symposium on Foundations of Computer Science, pages 42-51, Palo Alto, California, 3-5 November 1993. IEEE.

Categories and Subject Descriptors: F.1.2 [Computation by Abstract Devices]: Modes of Computation -- relations among complexity classes; F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems -- Complexity of proof procedures; computations on discrete structures; F.4.1 [Mathematical Logic and Formal Languages]: Mathematical Logic -- Computational logic; I.2.3 [Artificial Intelligence]: Deduction and Theorem Proving -- Nonmonotonic reasoning and belief revision; I.2.4 [Artificial Intelligence]: Knowledge Representation Formalisms and Methods

General Terms: Theory

Additional Key Words and Phrases: Autoepistemic logic, bounded query computation, epistemic logic, modal logic, NP, oracle, trees

Selected papers that cite this one

Selected references


  • Journal of the ACM homepage
  • Bibliography top level
  • Journal of the ACM Author Index
  • Search the HBP database