12
votes
1answer
582 views

Does every feasible partial order relation on the natural numbers extend to a feasible linear order relation?

It is well known that every partial order on a set can be extended to a linear order on that set. That is, for every partial order $\lhd$ on a set $X$, there is a linear order $\prec$ on $X$ such that ...
7
votes
2answers
334 views

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 ...