Opis

• Tytuł:
  Models of Bounded Arithmetic Theories and Some Related Complexity Questions
• Twórca:
  Alam, Abolfazl;
  Moniri, Morteza
• Współtwórca:
  Alam, Abolfazl - Shahid Beheshti University Department of Mathematics Faculty of Mathematical Sciences, 1983969411 Tehran;
  Moniri, Morteza - Shahid Beheshti University Department of Mathematics Faculty of Mathematical Sciences, 1983969411 Tehran;
  Alam, Abolfazl - abolfazlalam1989@gmail.com;
  Moniri, Morteza - m-moniri@sbu.ac.ir
• Opis:
  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.
• Dostępność obiektu:
  Dostęp otwarty
• Prawa: https://creativecommons.org/licenses/by-nc-nd/4.0
• Data:
  2022.08.25;
  2022.06.07
• Typ:
  Other
• Język:
  angielski
• Format:
  application/pdf
• Wydawca:
  Wydawnictwo Uniwersytetu Łódzkiego
• Relacja:
  Bulletin of the Section of Logic;2;
  51
• Temat i słowa kluczowe:
  bounded arithmetic;
  complexity theory;
  existentially closed model;
  model completeness;
  model companion;
  quantifier elimination;
  Stone topology
• Identyfikator:
  0138-0680;
  http://hdl.handle.net/11089/42922 ;
  2449-836X;
  10.18778/0138-0680.2022.03
• Dostawca danych:
  Repozytorium Uniwersytetu Łódzkiego
• Czy mogę z tego obiektu skorzystać?:
  sprawdź warunki licencji
• Rodzaj zawartości:
  pozostałe