Models of Bounded Arithmetic Theories and Some Related Complexity Questions
Models of Bounded Arithmetic Theories and Some Related Complexity Questions
Author(s): Abolfazl Alam, Morteza MoniriSubject(s): Philosophy, Logic, Philosophy of Science
Published by: Wydawnictwo Uniwersytetu Łódzkiego
Keywords: bounded arithmetic; complexity theory; existentially closed model; model completeness; model companion; quantifier elimination; Stone topology
Summary/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 S1/2(PV) has bounded model companion then NP=coNP. We also study bounded versions of some other related notions such as Stone topology.
Journal: Bulletin of the Section of Logic
- Issue Year: 51/2022
- Issue No: 2
- Page Range: 163-176
- Page Count: 14
- Language: English