Search problem $MIN^P$ is, given a polynomial-time computable predicate that is a partial order, to find its minimum (any will do).


Search problem $MIN^L$ is, given a polynomial-time computable predicate that is a linear order, to find its minimum.


Search problems can be interpreted as computational models (complexity classes), namely as polynomial time bounded computations plus an oracle solving instances of the search problem.


More formally, for example for linear orders: Enhance a polynomial time bounded Turing machine $S$ with an oracle. The oracle input always consists of a number $n$ and a code of another Turing machine $T$. Machine $T$ (accepts pairs of integers and) computes an order relation $<^L$ on integers from $0$ to $n$ and is constructed to guarantee termination in polynomial time.
The oracle then outputs a minimum number $m$ (that is, $0 \le m \le n$, and $(\forall x) 0 \le x \le n \implies m <^L x \vee m = x$). In case the machine $T$ supplied to the oracle is invalid (not a Turing machine code, or defining a relation which is not a linear order up to $n$), the oracle is free to output any value. Note that the size of $n$ is by definition polynomial in the size of the input to the Turing machine $S$, but its value may be exponential, and therefore the oracle may add computational power beyond polynomial time computable functions.


My question is: can this computation model (call it, $MIN^L$) solve $MIN^P$?


To further clarify, here is a trivial proof of the converse. $S$ will get some $n$ and a code of a Turing machine. It will simply feed both as $n$ and $T$ to its oracle, and output the oracle answer which is the desired minimum.


This question is bugging me for some time. A negative answer would entail some quite interesting consequences for fragments of bounded arithmetic.



Is $MIN^P$ search problem (partial order) reducible to $MIN^L$ (linear order) search problem?
Because of the issue I mention in my comment, it seems that the question admits an unsatisfactory affirmative answer. 


Namely, as I expect you know, it is a standard fact that every partial order is contained, as a set of relation pairs, within a linear order. In other words, for every partial order on a set there is a linear order on that set such that whenver $a\lt b$ with respect to the partial order, then this is also true for the linear order. In particular, any minimal element in this linear order will also be minimal in the partial order. 


Furthermore, the point is that if we are given a Turing machine program $e$ that computes a partial order on $\{0,1,\ldots,n\}$, then without actually running the program $e$, we may produce another program $e'$ that computes a linear order extending this partial order. The program $e'$, which we will merely write down but not actually run, works by first producing a complete table of the partial order computed by $e$, and then systematically linearizing it using any of the standard methods for doing so. For example, beginning with the partial order, one can systematically add one node at a time to make it linear, being careful to choose the right place to insert the node, and closing under transitivity. 


The point of my answer is that although the program $e'$ would take a long time in comparison with $|n|$ to run, if we were to run it, nevertheless we can write down the program $e'$ fairly quickly from the program $e$. Ultimately, I am proposing to reduce $\text{Min}^P$ to $\text{Min}^L$ by the following procedure: on input $e$, a program for a partial order, I write down the code $e'$ for a linearization of it, and then ask the $\text{Min}^L$ oracle for a minimal element of the relation computed by $e'$, which I then output as also being a minimal element of the relation computed by $e$. 


But this solution is not really satisfactory, because clearly the program $e'$ takes a lot longer to compute its relation than $e$ does. Technically, of course, $e'$ is a polynomial time algorithm, simply because it is computing a finite set (and is trivial on input pairs above $n$), and so it is linear time decidable by using large enough constants).


But it would seem that your mention of polynomial time algorithms suggests that you want to undertake the reduction by producing programs for linear orders that somehow take about the same amount of time as the original partial order to compute. I'm not sure exactly how to modify the question to get at this issue in the right way. 


Perhaps a natural version of the question that gets at this issue simply goes to the infinite relation case:


**Question.** Is every polynomial time decidable partial order relation on all of $\mathbb{N}$ linearized by a polynomial time decidable linear order relation on $\mathbb{N}$? 


