Models of Bounded Arithmetic Theories and Some Related Complexity Questions

Abolfazl Alam; Morteza Moniri

doi:10.18778/0138-0680.2022.03

Authors

Abolfazl Alam Shahid Beheshti University Department of Mathematics Faculty of Mathematical Sciences, 1983969411 Tehran
Morteza Moniri Shahid Beheshti University Department of Mathematics Faculty of Mathematical Sciences, 1983969411 Tehran

DOI:

https://doi.org/10.18778/0138-0680.2022.03

Keywords:

bounded arithmetic, complexity theory, existentially closed model, model completeness, model companion, quantifier elimination, Stone topology

Abstract

In this paper, we study bounded versions of some model-theoretic notions and results. We apply these results to the context of models of bounded arithmetic theories as well as some related complexity questions. As an example, we show that if the theory \(\rm S_2 ^1(PV)\) has bounded model companion then \(\rm NP=coNP\). We also study bounded versions of some other related notions such as Stone topology.

References

S. R. Buss, Bounded Arithmetic, Bibliopolis, Napoli (1986).
Google Scholar

S. R. Buss (ed.), Handbook of Proof Theory, Elsevier, Amsterdam (1998), DOI: https://doi.org/10.1016/s0049-237x(98)x8014-6.
Google Scholar DOI: https://doi.org/10.1016/S0049-237X(98)X8014-6

C. Chang, J. Keisler (eds.), Model theory, North-Holland, Amsterdam (1990).
Google Scholar

S. Cook, A. Urquhart, Functional Interpretations of Feasibly Constructive Arithmetic, STOC ’89, [in:] Proceedings of the Twenty-First
Google Scholar

Annual ACM Symposium on Theory of Computing, Association for Computing Machinery, New York, NY, USA (1989), pp. 107–112, DOI: https://doi.org/10.1145/73007.73017.
Google Scholar DOI: https://doi.org/10.1145/73007.73017

S. A. Cook, Feasibly Constructive Proofs and the Propositional Calculus (Preliminary Version), STOC ’75, [in:] Proceedings of the Seventh Annual ACM Symposium on Theory of Computing, Association for Computing Machinery, New York, NY, USA (1975), pp. 83–97, DOI: https://doi.org/10.1145/800116.803756.
Google Scholar DOI: https://doi.org/10.1145/800116.803756

P. Hájek, P. Pudlák, Metamathematics of First-Order Arithmetic, Perspectives in mathematical logic, Springer (1993).
Google Scholar DOI: https://doi.org/10.1007/978-3-662-22156-3

W. Hodges, A Shorter Model Theory, Cambridge University Press, Cambridge (1997).
Google Scholar

R. Kaye, Models of Peano arithmetic, vol. 15 of Oxford logic guides, Clarendon Press (1991).
Google Scholar

J. Krajicek, Bounded Arithmetic, Propositional Logic and Complexity Theory, Encyclopedia of Mathematics and its Applications, Cambridge University Press (1995), DOI: https://doi.org/10.1017/CBO9780511529948.
Google Scholar DOI: https://doi.org/10.1017/CBO9780511529948

D. Marker, Model Theory: An Introduction, vol. 217 of Graduate Texts in Mathematics, Springer-Verlag, New York (2002), DOI: https://doi.org/10.1007/b98860.
Google Scholar DOI: https://doi.org/10.1007/b98860

M. Moniri, Preservation theorems for bounded formulas, Archive for Mathematical Logic, vol. 46(1) (2007), pp. 9–14, DOI: https://doi.org/10.1007/s00153-006-0016-0.
Google Scholar DOI: https://doi.org/10.1007/s00153-006-0016-0