Thursday, February 7, 2019 4:00 pm
-
4:00 pm
EST (GMT -05:00)
Abolfazl Alam, Shahid Beheshti University
"Model Companion for Bounded Theories and some Related Complexity Questions"
A theory $T$ is called bounded model complete (b.m.c for short) if whenever $ M\subseteq N$ are models of $T$, then $M\subseteq_1^b N$. In the language of bounded arithmetic, a bounded theory $T$ is bounded model complete if and only if $T$ satisfies $\rm NP=coNP $. I describe the notion of bounded model companion and try to find the bounded model companion for some well-known bounded theories in bounded arithmetic such as $\rm S_{2}^{1}$.
MC 5403