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