AbstractIn 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 versionA 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
- Grigori Schwarz and Miroslaw Truszczynski. Nonmonotonic reasoning is sometimes simpler! Journal of Logic and Computation, 6(2):295-308, April 1996.
Selected references
- Richard P. Brent. The parallel evaluation of general arithmetic expressions. Journal of the ACM, 21(2):201-206, April 1974.
- Samuel R. Buss and Louise Hay. On truth-table reducibility to SAT. Information and Computation, 91(1):86-102, March 1991.
- Joseph Y. Halpern and Bruce M. Kapron. Zero-one laws for modal logic. In Proceedings, Seventh Annual IEEE Symposium on Logic in Computer Science, pages 369-380, Santa Cruz, California, 22-25 June 1992. IEEE Computer Society Press.
- Wiktor Marek and Miroslaw Truszczynski. Autoepistemic logic. Journal of the ACM, 38(3):588-619, July 1991.
- L. J. Stockmeyer and A. R. Meyer. Word problems requiring exponential time: Preliminary report. In Conference Record of Fifth Annual ACM Symposium on Theory of Computing, pages 1-9, Austin, Texas, 30 April-2 May 1973.