Hostname: page-component-78c5997874-t5tsf Total loading time: 0 Render date: 2024-11-02T23:55:37.122Z Has data issue: false hasContentIssue false
  • English
  • Français

Notes on polynomially bounded arithmetic

Published online by Cambridge University Press:  12 March 2014

Domenico Zambella
Domenico Zambella*
Affiliation:
Department of Mathematics and Computer Science, University of Amsterdam, Plantage Muidergracht 24, 1018 TV Amsterdam, The Netherlands, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We characterize the collapse of Buss' bounded arithmetic in terms of the provable collapse of the polynomial time hierarchy. We include also some general model-theoretical investigations on fragments of bounded arithmetic.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 61 , Issue 3 , September 1996 , pp. 942 - 966
Copyright
Copyright © Association for Symbolic Logic 1996

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1]Ajtai, M., -formulas on finite structures, Annals of Pure and Applied Logic, vol. 24 (1983), pp. 1–48.CrossRefGoogle Scholar
[2]Ajtai, M., The complexity of the pigeonhole principle, IEEE (1988), pp. 346–355.Google Scholar
[3]Buss, S. R., Bounded arithmetic, Bibliopolis, Naples, 1986.Google Scholar
[4]Buss, S. R., Axiomatizations and conservations results for fragments of bounded arithmetic, Logic and computation, Contemporary Mathematics, vol. 106, A.M.S., 1990, proceeding of a workshop held at Carnegie-Mellon University, 1987, pp. 57–84.CrossRefGoogle Scholar
[5]Buss, S. R., Relating the bounded arithmetic and polynomial time hierarchies, to appear.Google Scholar
[6]Cobham, A., The intrinsic computational difficulty of functions, Structure in complexity theory (Selman, A. L., editor), Lecture Notes in Computational Science, vol. 221, 1986, pp. 125–146.Google Scholar
[7]Hájek, P. and Pudlák, P., Metamathematics of first-order arithmetic, Springer-Verlag, Berlin, 1993.CrossRefGoogle Scholar
[8]Kadin, J., The polynomial time hierarchy collapses if the Boolean hierarchy collapses, IEEE (1988), pp. 278–292.Google Scholar
[9]Krajícěk, J., Exponentiation and second order bounded arithmetic, Annals of Pure and Applied Logic, vol. 48 (1990), pp. 261–276.CrossRefGoogle Scholar
[10]Krajícěk, J., Pudlák, P., and Takeuti, G., Bounded arithmetic and the polynomial time hierarchy, Annals of Pure and Applied Logic, vol. 52 (1991), pp. 143–153.CrossRefGoogle Scholar
[11]Mints, G. E., Quantifier-free and one-quantifier systems, Zapiski Nauchnykh Seminarov, vol. 20 (1971), pp. 115–133, in Russian. English translation: Journal of Soviet Mathematics, vol. 1 (1973), pp. 211–266.Google Scholar
[12]Paris, J. B. and Kirby, L. A. S., σn-collection schémas in arithmetic, Logic colloquium 77 (Macintyre, A., Pacholski, L., and Paris, J., editors), North-Holland, Amsterdam, 1978, pp. 199–209.CrossRefGoogle Scholar
[13]Parsons, C., On a number theoretic choice schema and its relation to induction, Intuitionism and proof theory (Kino, , Myhill, , and Vesley, , editors), North-Holland, Amsterdam, 1970, pp. 459–473.Google Scholar
[14]Razborov, A., An equivalence between second order bounded domain bounded arithmetic and first order bounded arithmetic, Arithmetic, proof theory and computational complexity (Clote, P. and Krajícěk, J. editors), Oxford University press, Oxford, 1993, pp. 247–277.CrossRefGoogle Scholar
[15]Takeuti, G., RSUV isomorphisms, Arithmetic, proof theory and computational complexity (Clote, P. and Krajícěk, J., editors), Oxford University press, Oxford, 1993, pp. 364–386.CrossRefGoogle Scholar
[16]Wilkie, A. J., Modelès non standard de l'arithmétique et complexité algorithmique, Modelès standard de l'arithmétique et theorie des ensembles (Wilkie, A. J. and Ressayre, J., editors), Publications Mathématique de l'Université Paris VII, Paris, 1983, pp. 1–45.Google Scholar