The smallest ordinal that is not the order type of a well-ordering of a subset of ℕ which is computable in polynomial time.
-
-
Replying to @ModelOfTheory
Analogs of the Church-Kleene ordinal for arbitrary complexity classes of decision problems.pic.twitter.com/pfQwv7pspq
1 reply 2 retweets 1 like -
Replying to @ModelOfTheory
Apparently Kleene proved that \omega_1^{PR} = \omega_1^{CK}.
1 reply 1 retweet 0 likes
\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.
0 replies
1 retweet
1 like
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.