Show simple item record

Models of Bounded Arithmetic Theories and Some Related Complexity Questions

dc.contributor.authorAlam, Abolfazl
dc.contributor.authorMoniri, Morteza
dc.date.accessioned2022-08-25T13:00:35Z
dc.date.available2022-08-25T13:00:35Z
dc.date.issued2022-06-07
dc.identifier.issn0138-0680
dc.identifier.urihttp://hdl.handle.net/11089/42922
dc.description.abstractIn 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.en
dc.language.isoen
dc.publisherWydawnictwo Uniwersytetu Łódzkiegopl
dc.relation.ispartofseriesBulletin of the Section of Logic;2en
dc.rights.urihttps://creativecommons.org/licenses/by-nc-nd/4.0
dc.subjectbounded arithmeticen
dc.subjectcomplexity theoryen
dc.subjectexistentially closed modelen
dc.subjectmodel completenessen
dc.subjectmodel companionen
dc.subjectquantifier eliminationen
dc.subjectStone topologyen
dc.titleModels of Bounded Arithmetic Theories and Some Related Complexity Questionsen
dc.typeOther
dc.page.number163-176
dc.contributor.authorAffiliationAlam, Abolfazl - Shahid Beheshti University Department of Mathematics Faculty of Mathematical Sciences, 1983969411 Tehranen
dc.contributor.authorAffiliationMoniri, Morteza - Shahid Beheshti University Department of Mathematics Faculty of Mathematical Sciences, 1983969411 Tehranen
dc.identifier.eissn2449-836X
dc.referencesS. R. Buss, Bounded Arithmetic, Bibliopolis, Napoli (1986).en
dc.referencesS. R. Buss (ed.), Handbook of Proof Theory, Elsevier, Amsterdam (1998), DOI: https://doi.org/10.1016/s0049-237x(98)x8014-6.en
dc.referencesC. Chang, J. Keisler (eds.), Model theory, North-Holland, Amsterdam (1990).en
dc.referencesS. Cook, A. Urquhart, Functional Interpretations of Feasibly Constructive Arithmetic, STOC ’89, [in:] Proceedings of the Twenty-Firsten
dc.referencesAnnual 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.en
dc.referencesS. 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.en
dc.referencesP. Hájek, P. Pudlák, Metamathematics of First-Order Arithmetic, Perspectives in mathematical logic, Springer (1993).en
dc.referencesW. Hodges, A Shorter Model Theory, Cambridge University Press, Cambridge (1997).en
dc.referencesR. Kaye, Models of Peano arithmetic, vol. 15 of Oxford logic guides, Clarendon Press (1991).en
dc.referencesJ. 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.en
dc.referencesD. Marker, Model Theory: An Introduction, vol. 217 of Graduate Texts in Mathematics, Springer-Verlag, New York (2002), DOI: https://doi.org/10.1007/b98860.en
dc.referencesM. 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.en
dc.contributor.authorEmailAlam, Abolfazl - abolfazlalam1989@gmail.com
dc.contributor.authorEmailMoniri, Morteza - m-moniri@sbu.ac.ir
dc.identifier.doi10.18778/0138-0680.2022.03
dc.relation.volume51


Files in this item

Thumbnail
Name:
163-176_Alam,_Moniri.pdf
Size:
1.747Mb
Format:
PDF
View/Open

This item appears in the following Collection(s)

Show simple item record

https://creativecommons.org/licenses/by-nc-nd/4.0
Except where otherwise noted, this item's license is described as https://creativecommons.org/licenses/by-nc-nd/4.0