Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

What is the least recursive ordinal $\alpha$ such that there is no algorithm in complexity class $\mathsf{P}$ which implements a well-ordering of $\mathbb{N}$ with order type $\alpha$? (where the size of input is the total number of digits in numbers being compared)

Is it true that no well-ordering of $\mathbb{N}$ with order type $>\alpha$ can be implemented using an algorithm in $\mathsf{P}$?

Has connection between ordinals and complexity classes been studied? Can you recommend any books or papers related to this topic?

share|improve this question

2 Answers 2

up vote 12 down vote accepted

There is no such recursive ordinal, because in fact every computable ordinal is the order type of a polynomial time computable relation on $\mathbb{N}$. In other words, the least ordinal not describable by a polynomial time relation on $\mathbb{N}$ is $\omega_1^{ck}$, the same as the least ordinal not describable by any computable relation on $\mathbb{N}$, of any computable complexity.

To see this, suppose that $\alpha$ is any computable ordinal. This means that it is the order type of a computable relation $\triangle$ on $\mathbb{N}$. We may assume without loss of generality that $\omega^2\leq\alpha$, since the ordinals up to $\omega^2$ are clearly polynomial time describable. Let us now describe a new relation on a subset of $\mathbb{N}\times\mathbb{N}$, by replacing each $n\in\mathbb{N}$ with the pair $(n,k_n)$, where $k_n$ is a number describing in a very concrete way in its representation the complete relation of $\triangle$ on all numbers up to an including $n$ in the usual $\mathbb{N}$ order, plus the computations witnessing those relations. Note that we may easily recognize such pairs $(n,k_n)$ in linear time, since the very representation of $k_n$ reveals whether it is correct or not. We now define $(n,k_n)\lt(m,k_m)$ just in case $n\triangle m$. This is polynomial time computable from the input, because one of the $n$ or $m$ must be larger in the usual order of $\mathbb{N}$, and so the corresponding $k_n$ or $k_m$ exhibits the necessary information about $n\triangle m$. Finally, we extend our new relation to a total ordering of $\mathbb{N}\times\mathbb{N}$ by placing all other pairs $(n,k)$ not of the desired form as an $\omega$-sequence at the bottom of the order. This does not affect the overall order type of the order, since $\omega+\omega^2=\omega^2$ and consequently $\omega+\alpha=\alpha$. So our new relation is a polynomial time decidable relation on $\mathbb{N}\times\mathbb{N}$ of order type $\alpha$.

We may now easily convert the relation on $\mathbb{N}\times\mathbb{N}$ to a relation on $\mathbb{N}$, by means of the standard polynomial pairing function. Thus, we obtain $\alpha$ as a polynomial time describable ordinal, and so the conclusion is that complexity considerations do not affect the class of computable ordinals.

share|improve this answer
4  
In fact, since $\omega_1^{ck}$ is also the least ordinal not describable by any hyperarithmetic relation on $\mathbb{N}$, the situation is essentially that one gets no new ordinals by moving through the vast range from polynomial time decidable relations, up through the computable relations, through the entire arithmetic hierarchy and even the hyperarithmetic hierarchies! Every hyperarithmetic ordinal is in fact polynomial time computable. –  Joel David Hamkins Nov 29 '11 at 5:09
    
Does it mean that every well-order on $\mathbb{N}$ that is describable by an arithmetic formula is order-isomorphic to some recursive ordinal? –  Vladimir Reshetnikov Nov 29 '11 at 18:27
1  
Vladimir, yes, that is right. –  Joel David Hamkins Nov 29 '11 at 19:22
    
That's a really amazing fact! –  Vladimir Reshetnikov Nov 29 '11 at 21:00
2  
The reason is that the set-theoretic structure $L_{\omega_1^{ck}}$ satisfies the Kripke-Platek axioms of set theory and contains all the arithmetically definable sets of natural numbers. So all such well-orderings are isomorphic to ordinals below $\omega_1^{ck}$ –  Joel David Hamkins Nov 30 '11 at 0:42

You may want to check "Dynamic Ordinal Analysis" by Arnold Beckmann which is an attempt to define a finer notion to classical ordinals that can be used ti distinguish between complexity classes.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.