2
$\begingroup$

The "big five subsystems of second-order arithmetic" in reverse arithmetic reveal the stratification of the structure of mathematics. What if any is the connection of these strata with complexity classes?

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ Even an NP problem can be solved recursively, so all the complexity of the usual classes is buried in RCA_0. Beyond that, there are obviously many maps from the five subsystems of second-order arithmetic to complexity classes that preserve (non-)inclusion, but I don't know of any that are insightful. $\endgroup$
    – user44143
    Commented Sep 19, 2017 at 5:42

0

Reset to default

You must log in to answer this question.