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 ${\lhd}\subseteq\prec$, meaning $a\lhd b\implies a\prec b$. In the most general case, with uncountable $X$, one appeals to Zorn's lemma. For relations on $\mathbb{N}$, however, the linearization process is effective. My question concerns the relative complexity of such linearizations $\prec$ in comparison with the original order $\lhd$. (See also Jirka Hanika's related question on reducing minimal element search for partial orders to that of linear orders in the case of finite orders.)

**Question.** Does every polynomial time decidable partial order
relation $\lhd$ on $\mathbb{N}$ extend to a polynomial time
decidable linear order relation on $\mathbb{N}$?

I expect not. I think there will be a polynomial time decidable partial order relation on $\mathbb{N}$ that does not extend to any polynomial time linear order. The reason I believe so is that the natural method of constructing a linear order extending a given partial order seems to proceed fundamentally in series rather than parallel, in the sense that one gradually linearizes increasing portions of the partial order, but one must keep track of what one did earlier, in order not to conflict with later decisions. But with a polynomial time construction, one cannot afford to inspect the earlier parts of the linearization.

Meanwhile, every computable partial order $\lhd$ on $\mathbb{N}$ does extend to a computable linear order $\prec$ on $\mathbb{N}$, and this is what I meant when I said that linearizaton is effective, by the following procedure: at stage $n$, we know how the numbers up to $n$ relate with respect to $\lhd$ and we have built the desired relation $\prec$ on the numbers below $n$. The new number $n$ divides this linear order into those that are $\lhd$-below $n$, incomparable to $n$, and $\lhd$-above $n$. We may now proceed to linearize $n$ into the order by placing $n$ as high as possible, say, above all the nodes so far to which it is incomparable, if any. This recursive procedure produces a linear order extending $\lhd$.

The point for the question is that this algorithm seems to require an exponential increase in the time complexity, since on a given input one must construct the relation on all nodes up to that node before knowing what to do, and this takes exponential time. Indeed, it isn't even clear whether one should be able to find a linearization in the class NP.

**Question.** Does every polynomial time partial order extend to
an NP linear order?

I expect not, since even a polynomial size certificate seems insufficient in general to track the linearization construction, which has exponential size.

Finally, let me point out that the analogue at the level of c.e. orders attains the negative result.

**Theorem.** There is a c.e. partial order $\lhd$ on
$\mathbb{N}$ that does not extend to any c.e. linear order on
$\mathbb{N}$.

Proof. Part of the point is that every c.e. linear order is actually decidable. Let $A,B\subset\mathbb{N}$ be computable inseparable c.e. sets, meaning that they are disjoint c.e. sets and there is no decidable set containing $A$ and disjoint from $B$. Define the partial order $\lhd$ by placing every element of $A$ below $0$ and $0$ below every element of $B$, but otherwise elements are incomparable. This is a c.e. relation, since given two numbers $a$ and $b$, we can say how they are related once they are enumerated into $A$ or $B$, and otherwise they are unrelated. But if the relation extends to a linear order $\prec$ on $\mathbb{N}$, then the set of $\prec$-predecessors of $0$ will be a computable separation of $A$ and $B$, a contradiction. QED

Can one similarly employ a polytime version of inseparability to answer the main question?

There are similarly many analogues of the main question in terms of other complexity classes. Please answer if you have interesting positive or negative results for any of them.