Models of Bounded Arithmetic Theories and Some Related Complexity Questions

Autor:	Abolfazl Alam, Morteza Moniri
Jazyk:	angličtina
Rok vydání:	2022
Předmět:	bounded arithmetic complexity theory existentially closed model model completeness model companion quantifier elimination stone topology Logic BC1-199
Zdroj:	Bulletin of the Section of Logic, Vol 51, Iss 2, Pp 163-176 (2022)
Druh dokumentu:	article
ISSN:	0138-0680 2449-836X
DOI:	10.18778/0138-0680.2022.03
Popis:	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.
Databáze:	Directory of Open Access Journals
Externí odkaz:	https://doaj.org/article/4dca557a86004aa1b3d4cb446999fef0 Zobrazit plný text záznamu View record in DOAJ Plný text ve formátu PDF