Skip to main content
2 of 2
replaced http://mathoverflow.net/ with https://mathoverflow.net/

If $T_1$ and $T_2$ are theories corresponding to complexity classes $C_1$ and $C_2$ (resp.), then separation of $C_1$ from $C_2$ from $C_2$ implies separation of $T_1$ from $T_2$, but not necessarily vice versa. (This is already mentioned in T. Chow’s answer.) In fact, with details somewhat dependent on the pair of theories, generally separation of $T_1$ from $T_2$ tends to be equivalent to separation of $C_1$ from $C_2$ in some model of the weaker of the two theories, as opposed to separation of $C_1$ from $C_2$ in the standard model $\mathbb N$. Thus, in principle, separation of the theories is a weaker statement than separation of the corresponding complexity classes.

In practice, separation of theories appears essentially as hard as separation of complexity classes.

Most of the known unconditional separation results for theories of bounded arithmetic actually go the opposite way, i.e., they are based on separations of complexity classes: the two typical cases are separations of relativized theories, such as $S^i_2(\alpha)\ne S^{i+1}_2(\alpha)$ (which follow from separation of complexity classes with oracles), and separations of theories corresponding to very small complexity classes, such as $V^0\ne V^0[p]$ (which follows from $\mathrm{AC}^0\ne\mathrm{AC}^0[p]$).

The exceptions are separations of various “pathologically weak” theories. Primarily, this concerns variants of $\Sigma^b_0$ induction, about which you can read more in https://mathoverflow.net/a/228102, including a list of references. Some of these results also apply to “very short” $\Sigma^b_1$ induction (such as $\Sigma^b_1$-LLLIND); for this see [6], and the paper S. Boughattas, J.-P. Ressayre: Bootstrapping, part I, Annals of Pure and Applied Logic 161 (2010), no. 4, pp. 511–533. Now, what makes these unconditional separations work is precisely the fact that these theories do not correspond to reasonable complexity classes, so this does not provide any evidence for the thesis in the question.

Emil Jeřábek
  • 47.2k
  • 4
  • 147
  • 209