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