The smallest ordinal that is not the order type of a well-ordering of a subset of ℕ which is computable in polynomial time.
-
-
\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.
Thanks. Twitter will use this to make your timeline better. UndoUndo
-
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.