The smallest ordinal that is not the order type of a well-ordering of a subset of ℕ which is computable in polynomial time.
-
-
Apparently Kleene proved that \omega_1^{PR} = \omega_1^{CK}.
-
\omega_1^P = \omega_1^{CK}. In fact, every recursive ordinal is order-type of a wellordering that's computable in linear time and log space.
End of conversation
New conversation -
Loading seems to be taking a while.
Twitter may be over capacity or experiencing a momentary hiccup. Try again or visit Twitter Status for more information.