What is the least [recursive ordinal](http://en.wikipedia.org/wiki/Recursive_ordinal) $\alpha$ such that there is no algorithm in [complexity class $\mathsf{P}$](http://en.wikipedia.org/wiki/P_(complexity)) which implements a well-ordering of $\mathbb{N}$ with [order type](http://en.wikipedia.org/wiki/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?



Ordinals and complexity classes
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. 


