# 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 ${\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.

• Linearization (“topological sort”) of a finite partial order given by a table can be computed in parallel, in fact in uniform $TC^0$, by the following trivial procedure: put $x\prec y$ iff $|x\down|< |y\down|\lor(|x\down|=|y\down|\land x< y)$, where $x\down=\{z:z\unlhd x\}$, and $<$ is any fixed linear order. It follows that if $x\lhd_ay$ is a parametrized family of partial orders on $\{0,\dots,a\}$, computable in polynomial-time (when given $x,y,a$ in binary), then one can compute a uniform linearization $x\prec_ay$ in PP. However, I don’t know how to make this work for infinite orders. Feb 27 '12 at 15:27
• Hmm, read $\downarrow$ for $\down$. Feb 27 '12 at 15:29
• I have an answer only for some of the higher "analogues" at the moment. Every PSPACE (or EXP) decidable partial order extends into a PSPACE (or EXP) decidable total order. Reason: to decide whether $x\prec y$, one can safely ignore all $z\triangleleft w$ facts where $max(z,w)>max(x,y)$ (by transitivity of $\triangleleft$). It is thus enough to construct partial linearizations starting with $0$, $1$, $\dots$, constantly checking $\triangleleft$ within the set, arbitrarily (but deterministically) ordering still independent pairs and computing transitive closure, until $max(x,y)$ is reached. Feb 28 '12 at 21:58
• OK. Done for EXP. My claim about PSPACE was premature. Feb 29 '12 at 23:22

A tiny step forward can be done by observing that some complexity classes, such as $EXP$, are fortunately closed under exponential slowdown.

Every exponential time decidable partial order relation $\triangleleft$ on $N$ extends to an exponential time decidable linear order relation on $N$.

The proof is directly based on the construction described in the question.

Denote the restriction of $\triangleleft$ to $\{0,1,...,n-1\}$ as $\triangleleft_n$. Construct a corresponding sequence of linear orders $\prec_n$, each also on $\{0,1,...,n-1\}$.

Start from $\prec_0=\triangleleft_0=\emptyset$ and continue recursively so that each $\prec_n$ extends both $\triangleleft_n$ and $\prec_{n-1}$ by defining, for $x<n-1$, $$n-1\;\prec_n\; x\Longleftrightarrow (\exists y< n-1)\ n-1\,\triangleleft\, y\wedge y\prec_{n-1}x$$

(and $x\prec_n\; n - 1$ otherwise). Put $\prec$ to be the union of all $\prec_n$.

Even less formally stated, we are simply proceeding from 0 up and putting each number as high in the constructed linear order as $\triangleleft$ restricted to numbers examined so far allows. (We never encounter conflicting requirements in any step because of transitivity of $\triangleleft$.)

This algorithm can be used for deciding $a\prec b$ which is $a\prec_{max(a+1,b+1)} b$.

The algorithm needs to remember/update just some $\prec_i$ (as input) and $\prec_{i+1}$ (as output) at a time, which are exponential sized structures. To process one such pair it is enough to pass through $i^2$ number pairs (standing for $x$,$y$ above) only and spend only polynomial time at each one plus one query to the exponential time relation $\triangleleft$. Therefore the total time complexity is a product of a few exponential factors (decision of $\triangleleft$, $i$, $x$, $y$) and $\prec$ is thus in $EXP$, too.