NP TREES AND CARNAPS MODAL LOGIC

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 clas s of problems where G is a general dag and show that this class coinci des with DELTA2P. We then consider the class where G is a tree. Our ma in result states that this class is identical to P(NP)[O(log n)], the class of problems solvable in polynomial time with a logarithmic numbe r of queries to an oracle in NP. This result has interesting applicati ons in the fields of modal logic and artificial intelligence. In parti cular, we show that the following problems are all P(NP)[O(log n)] com plete: validity-checking of formulas in Carnap's modal logic, checking whether a formula is almost surely valid over finite structures in mo dal logics K, T, and S4 (a problem recently considered by Halpern and Kapron [1992]), and checking whether a formula belongs to the stable s et of beliefs generated by a propositional theory. We generalize the c ase of dags to the case where G is a general (possibly cyclic) directe d graph of NP-oracle queries and show that this class corresponds to I I2P. 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.