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.

9more comments