NP trees and Carnap's modal logic

ABSTRACT

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 D^p2 .We then consider the class where G is a tree. Our main result states that this class is identical to PNP[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 PNP[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 P^p2 . 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.

REFERENCES

• 1: ~ALLENDER, E., AND WILSON, C. 1990. Width-bounded reducibility and binary search over ~complexity classes. In Proceedings of the 5th Conference on Structure in Complexity Theory. IEEE ~~ Computer Society Press, New York, pp. 122-129.
• 2: Carme Álvarez , José L. Balczar , Birgit Jenner, Functional oracle queries as a measure of parallel time, Proceedings of the 8th annual symposium on Theoretical aspects of computer science, p.422-433, February 1991, Hamburg, Germany
• 3: STACS 91. Lecture Notes in Computer Science, vol. 480, Springer-Verlag, New York, pp. ~422-433.
• 4: Richard Beigel, Bounded queries to SAT and the Boolean hierarchy, Theoretical Computer Science, v.84 n.2, p.199-223, July 29, 1991 [doi>10.1016/0304-3975(91)90160-4]
• 5: Richard P. Brent, The Parallel Evaluation of General Arithmetic Expressions, Journal of the ACM (JACM), v.21 n.2, p.201-206, April 1974 [doi>10.1145/321812.321815]
• 6: ~BRESSAN, A. 1972. A General Interpreted Modal Calculus. Yale University Press, New Haven, ~Conn.buss, S. R., AND HAY, L. 1991. On truth-table reducibdity to SAT. In)''. Cortzput. 91, 86 102.
• 7: Jin-Yi Cai , Thomas Gundermann , Juris Hartmanis , Lane A. Hemachandra , Vivian Sewelson , Klaus Wagner , Gerd Wechsung, The Boolean hierarchy I: structural properties, SIAM Journal on Computing, v.17 n.6, p.1232-1252, Dec. 1988 [doi>10.1137/0217078]
• 8: ~CARNAP, R. 1947. Meaning and Necessity. The University of Chicago Press, Chicago, Ill.
• 9: Jorge Castro , Carlos Seara, Characterizations of Some Complexity Classes Between Theta^p_2 and Delta^p_2, Proceedings of the 9th Annual Symposium on Theoretical Aspects of Computer Science, p.305-317, February 13-15, 1992
• 10: ~CASTRO, J., AND SEARA, C. 1992. The O-operator and the Low Hmrarchy. Report LSI-92-16-R. ~Univ. Polit~cmca de Catalunya, Catalunya, Mexico.
• 11: ~CHELLAS, B. 1980. Modal Logic, ttn Introduetton. Cambridge University Press, Cambndge, ~England.
• 12: ~ONINI, F. M., LENZERINI, M., NARDI, D., Nun', W., AND SCHAERE, A. 1992. Adding epistemic ~operators to concept languages. In Proceedings of the 3rd International Conference on Principles ~o)` Knowledge Representation and Reasoning KR-92. pp. 342-353.
• 13: ~FAGIN, R. 1976. Probabilities on finite models. J. Symb. Logic 41, 1, 50-58.
• 14: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 15: William I. Gasarch , Lane A. Hemachandra , Albrecht Hoene, On checking versus evaluation of multiple queries, Proceedings on Mathematical foundations of computer science 1990, p.261-268, September 1990, Banska´ Bystrica, Czechoslovakia
• 16: ~GLEBSKn, Y. V., KOGAN, D. I., LIOGON*KI1, U. I., AND TALANOV, V.h. 1969. Range and degree ~of realizability of formulas in the restricted predicate calculus (in Russian). Ktbemetika 2, ~17 28. English translation in Cybe;Tzetics 5, 142-154.
• 17: ~GOTTLOB, G. 1992. Complexity results for nonmonotomc logics. J. Logtc Computation 2, 3 ~(June), 397-425.
• 18: ~GoTrhOB, G. 1992/1993. The Power of beliefs: Translating default logic into standard au- ~toepistemic logic. Report CD-TR-92/34, Tech. Univ. W~en, Institut fiir Informationssysteme, ~Wlen, Austria~ short version m Proceedmgs of the 13th btternattonal Joint Conference otz Artificial ~bztelhgence (JCA1 1993). (Chamb&y, France, Aug./Sept.) voI. 1., Morgan-Kaufmann, San ~Mateo, Calif., pp. 570-575.
• 19: ~HALPERN, J. Y., AND KAPRON, B. 1992. Zero-one laws for modal logic. In Proceedings of the 7th ~Annual IEEE Symposn4m on Logic in Conzputer Science. IEEE, New York. Full version: Tech. Rep. RJ 8836 (79218). IBM Research Division, Almaden Research Center, Santa Clara, Calif., pp. 369-380.
• 20: ~HALPERN, J. Y., AND KAPRON, B. 1994. Zero-One Laws for Modal Logic. Updated version: ~Ann. Pure Appl. Logic. 69, 157-193.
• 21: J. Halpern , Y. Moses, Towards a theory of knowledge and ignorance: preliminary report, Logics and models of concurrent systems, Springer-Verlag New York, Inc., New York, NY, 1989
• 22: ~HEMACHANDRA, L. 1989. The strong exponential hierarchy collapses. J. Comput. Svst. Set. 39, ~299-322.
• 23: ~HUGES, G. E., AND CRESSWELL, M.J. 1978. An bltroduction to ModalLogtc. Methuen, London, ~England.
• 24: David S. Johnson, A catalog of complexity classes, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
• 25: ~KaDtN, J. 1989. pNP{O(log,,)l and Sparse Turing-Complete Sets for NP. J. Comput. Syst. Sci. 39, ~282-298.
• 26: ~K6BLER, J., SCHOEN~NG, U., AND WAGNER, K.W. 1987. The difference and the truth-table ~hierarchies for NP. R.A.I.R.O 21, 419-435.
• 27: Mark W. Krentel, The complexity of optimization problems, Journal of Computer and System Sciences, v.36 n.3, p.490-509, June 1988 [doi>10.1016/0022-0000(88)90039-6]
• 28: Mark W. Krentel, Generalizations of Opt P to the polynomial hierarchy, Theoretical Computer Science, v.97 n.2, p.183-198, April 27, 1992 [doi>10.1016/0304-3975(92)90073-O]
• 29: Hector J. Levesque, Foundations of a functional approach to knowledge representation., Artificial Intelligence, v.23 n.2, p.155-212, July 1984 [doi>10.1016/0004-3702(84)90009-2]
• 30: ~MAREK, W. 1989. Stable theories in autoepistemic logic. Fund. Inf. 12, 243-254.
• 31: Wiktor Marek , Mirosław Truszczyński, Autoepistemic logic, Journal of the ACM (JACM), v.38 n.3, p.587-618, July 1991 [doi>10.1145/116825.116836]
• 32: ~MAREK, W., AND TRUSZCZY~SK1, M. 1993. Nonmonotomc Logic. Springer-Verlag, Berlin.
• 33: Robert C. Moore, Semantical considerations on nonmonotonic logic, Artificial Intelligence, v.25 n.1, p.75-94, Jan. 1985 [doi>10.1016/0004-3702(85)90042-6]
• 34: Ilkka Niemelä, Decision Procedure for Autoepistemic Logic, Proceedings of the 9th International Conference on Automated Deduction, p.675-684, May 23-26, 1988
• 35: Ilkka Niemelä, Towards automatic autoepistemic reasoning, Proceedings of the European workshop on Logics in AI, p.428-443, March 1991, Amsterdam, The Netherlands
• 36: Ilkka N. F. Niemelä, On the decidability and complexity of autoepistemic reasoning, Fundamenta Informaticae, v.17 n.1-2, p.117-155, Sept.– Oct. 1992
• 37: Mitsunori Ogiwara, NC^k(NP) = AC^(k-1)(NP), Proceedings of the 11th Annual Symposium on Theoretical Aspects of Computer Science, p.313-324, February 24-26, 1994
• 38: ~PAPADIMITRIOU, C. n., AND YANNAKAKIS, M. 1984. The complexity of facets (and some facets ~of complexity). J. Comput. Syst. Sci. 28, 244-259.
• 39: Christos H. Papadimitriou , Stathis Zachos, Two remarks on the power of counting, Proceedings of the 6th GI-Conference on Theoretical Computer Science, p.269-276, January 05-07, 1983
• 40: ~REITER, R. 1990. On asking what a database knows. In Symposium on Computational Logics, ~J. W. Lloyd, ed. ESPRIT Basic Research Action Series. Springer-Verlag, New York, pp. 90-113.
• 41: Robert Stalnaker, A note on non-monotonic modal logic, Artificial Intelligence, v.64 n.2, p.183-196, Dec. 1993 [doi>10.1016/0004-3702(93)90104-J]
• 42: John E. Savage, The Complexity of Computing, Krieger Publishing Co., Inc., Melbourne, FL, 1987
• 43: Uwe Schöning , Klaus W. Wagner, Collapsing Oracle Hierarchies, Census Functions and Logarithmically Many Queries, Proceedings of the 5th Annual Symposium on Theoretical Aspects of Computer Science, p.91-97, February 11-13, 1988
• 44: Grigori Schwarz , Miroslaw Truszczynski, Nonmonotonic Reasoning is Sometimes Simpler, Proceedings of the Third Kurt Gödel Colloquium on Computational Logic and Proof Theory, p.313-324, August 24-27, 1993
• 45: ~SPIRA, P.M. 1971. On time/hardware complexity tradeoffs for Boolean functions. In Proceed- ~ings of the 4th Hawaii b~ternational Symposium on System Sczenees. pp. 213-224.
• 46: Ian A. Stewart, Using the Hamiltonian path operator to capture NP, Journal of Computer and System Sciences, v.45 n.1, p.127-151, Aug. 1992 [doi>10.1016/0022-0000(92)90043-I]
• 47: ~STEWART, I.A. 1993. Logical characterization of bounded query classes 2: Polynomial-time ~oracle machines. Fund. Inf. 18, 93-105.
• 48: ~STOCKMEYER, L.J. 1977. The polynomial-time hierarchy. Theoret. Comput. Sci., 3, 1-22.
• 49: L. J. Stockmeyer , A. R. Meyer, Word problems requiring exponential time(Preliminary Report), Proceedings of the fifth annual ACM symposium on Theory of computing, p.1-9, April 30-May 02, 1973, Austin, Texas, United States [doi>10.1145/800125.804029]
• 50: K W Wagner, More complicated questions about maxima and minima, and some closures of NP, International Colloquium on Automata, Languages and Programming on Automata, languages and programming, p.434-443, September 1986, Rennes, France
• 51: Klaus W. Wagner, Bounded query classes, SIAM Journal on Computing, v.19 n.5, p.833-846, Oct. 1990 [doi>10.1137/0219058]
• 52: ~WEGENER, I. 1983. Relating monotone formula size and monotone depth of Boolean func- ~tions. Inf. Proc. Lett. 16, 41-42.
• 53: Ingo Wegener, The complexity of Boolean functions, John Wiley & Sons, Inc., New York, NY, 1987
• 54: ~WILSON, C.B. 1987. Relativized NC. Math. Syst. Theory 20, 13-29.
• 55: Christopher B. Wilson, On the decomposability of NC and AC, SIAM Journal on Computing, v.19 n.2, p.384-396, April 1990 [doi>10.1137/0219024]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes
          Subjects: Relations among complexity classes

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Complexity of proof procedures; Computations on discrete structures
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Computational logic

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.3 Deduction and Theorem Proving
          Subjects: Nonmonotonic reasoning and belief revision

General Terms:
Theory

Keywords:
NP, autoepistemic logic, bounded query computation, epistemic logic, modal logic, oracle, trees