Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

Fragments of bounded arithmetic and bounded query classes


Author: Jan Krajíček
Journal: Trans. Amer. Math. Soc. 338 (1993), 587-598
MSC: Primary 03F30; Secondary 03D15, 03F05, 03F50, 68Q15
DOI: https://doi.org/10.1090/S0002-9947-1993-1124169-X
MathSciNet review: 1124169
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We characterize functions and predicates $ \Sigma _{i + 1}^b$-definable in $ S_2^i$. In particular, predicates $ \Sigma _{i + 1}^b$-definable in $ S_2^i$ are precisely those in bounded query class $ {P^{\Sigma _i^p}}[O(\log n)]$ (which equals to $ \operatorname{Log}\;{\text{Space}}^{\Sigma _i^p}$ by [B-H, W]). This implies that $ S_2^i \ne T_2^i$ unless $ {P^{\Sigma _i^p}}[O(\log n)] = \Delta _{i + 1}^p$. Further we construct oracle $ A$ such that for all $ i \geq 1$: $ {P^{\Sigma _i^p(A)}}[O(\log n)] \ne \Delta _{i + 1}^p(A)$. It follows that $ S_2^i(\alpha ) \ne T_2^i(\alpha )$ for all $ i \geq 1$. Techniques used come from proof theory and boolean complexity.


References [Enhancements On Off] (What's this?)

  • [B1] S. Buss, Bounded arithmetic, Bibliopolis, Naples, 1986. MR 880863 (89h:03104)
  • [B2] -, Axiomatizations and conservations results for fragments of bounded arithmetic, Contemp. Math., vol. 106, Amer. Math. Soc., Providence, R. I., 1990, pp. 57-84. MR 1057816 (91m:03059)
  • [B-H] S. Buss and L. Hay, On truth-table reducibility to SAT and the difference hierarchy over $ NP$, Proc. Structure in Complexity, June 1988, IEEE, pp. 224-233.
  • [H1] J. Hastad, Computational limitations for small-depth circuits, MIT Press, 1986.
  • [H2] -, Almost optimal lower bounds for small depth circuits, Randomness and Computation (S. Micali, ed.), Ser. Adv. Comp. Res., vol. 5, JAI Press, 1989, pp. 143-170.
  • [H-P] P. Hájek and P. Pudlák, Metamathematics of first-order arithmetic, Perspectives in Mathematical Logic, Springer, New York, 1993. MR 1219738 (94d:03001)
  • [K] J. Krajíček, No counterexample interpretation and interactive computation, Proc. Workshop Logic from Comp. Science, Berkeley, November 1989 (Y. Moschovakis, ed.), Math. Sci. Res. Inst. Publ. 21, Springer-Verlag, 1992, pp. 287-293. MR 1236013 (94k:03079)
  • [K-P] J. Krajíček and P. Pudlák, Quantified propositional calculi and fragments of bounded arithmetic, Z. Math. Logik Grundlag. Math., Bd 36(1), (1990), pp. 29-46. MR 1030537 (91f:03118)
  • [K-P-S] J. Krajíček, P. Pudlák, and J. Sgall, Interactive computations of optimal solutions, Mathematical Foundations Comput. Sci. (B. Rovan, ed.), Lecture Notes in Comp. Sci., vol. 452, Springer-Verlag, 1990, pp. 48-60. MR 1084823 (91m:68061)
  • [K-P-T] J. Krajíček, P. Pudlák, and G. Takeuti, Bounded arithmetic and the polynomial hierarchy, Ann. of Pure Appl. Logic 52 (1991), 143-153. MR 1104058 (92f:03068)
  • [K-T] J. Krajíček and G. Takeuti, On induction-free provability, Ann. Math. and Artificial Intelligence 6 (1992), 107-126. MR 1279421 (95h:03129)
  • [Kre] M. W. Krentel, The complexity of optimizations problems, Proc. 18th Annual ACM Sympos. on Theory of Computing, ACM Press, 1986, pp. 69-76.
  • [Pa] R. Parikh, Existence and feasibility in arithmetic, J. Symbolic Logic 36 (1971), 494-508. MR 0304152 (46:3287)
  • [P] P. Pudlák, Some relations between subsystems of arithmetic and complexity of computations, Proc. Workshop Logic from Comp. Sci., Berkeley, November 1989 (Y. Moschovakis, ed.), Math. Sci. Res. Inst. Publ. 21, Springer-Verlag, 1992, pp. 499-519. MR 1236021 (94g:03113)
  • [S] M. Sipser, Borel sets and circuit complexity, Proc. 15th Annual ACM Sympos. on Theory of Computing, ACM Press, 1983, pp. 61-69.
  • [W] K. W. Wagner, Bounded query classes, SIAM J. Comput. 19(5) (1990), 833-846. MR 1059657 (91m:68063)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 03F30, 03D15, 03F05, 03F50, 68Q15

Retrieve articles in all journals with MSC: 03F30, 03D15, 03F05, 03F50, 68Q15


Additional Information

DOI: https://doi.org/10.1090/S0002-9947-1993-1124169-X
Article copyright: © Copyright 1993 American Mathematical Society

American Mathematical Society