4
$\begingroup$

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.

$\endgroup$
14
  • 1
    $\begingroup$ Could you clarify an issue? Every algorithm deciding a finite structure is polynomial time decidable (simply pick large enough constants), and so I'm not clear on precisely what you mean when you say that T is "constructed to guarantee termination in polynomial time," given that it decides a finite structure. Also, the input to $S$ includes $T$, which may be far larger than $n$, and so if you are considering polynomial time in the input to $S$, does this mean just $n$ or also $T$? $\endgroup$ Feb 26, 2012 at 0:19
  • $\begingroup$ Thank you! 1. "constructed to guarantee poly-time termination" means that it is syntacticably checkable that the machine always terminates in $O(n^k)$ for a specific $k$. A dedicated clock tape, etc. But I only really need the fact of the poly-time bound. (Or not even that, with the right relativization approach; $<^P$ can be supplied using an oracle, and is accessible from both $S$ and $T$ while we are reducing $MIN^P$ to $MIN^L$.) 2. The input to $S$ does not include $T$. $S$ creates any $T$'s it wants to pass to the oracle. I just disambiguated this in the question. $\endgroup$ Feb 26, 2012 at 22:21
  • 1
    $\begingroup$ Čau Jirko! The notion of reduction I’d expect here is as follows. Are there oracle polynomial-time functions $n_L^{<^P}(n_P)$, $m_P^{<^P}(n_P,m_L)$, and $R^{<^P}(n_P,x,y)$ such that: if the oracle $<^P$ is a partial order on $\{0,\dots,n_P-1\}$, then $R^{<^P}(n_P,-,-)$ defines (the characteristic functions of) a linear order $<^L$ on $\{0,\dots,n_L^{<^P}(n_P)-1\}$, and if $m_L$ is the minimal element of $<^L$, then $m_P^{<^P}(n_P,m_L)$ is a minimal element of $<^P$? This is not quite the same as asking $PV(\alpha)$ to prove that the minimization principle for $PV(\alpha)$ linear orders... $\endgroup$ Feb 27, 2012 at 14:16
  • 1
    $\begingroup$ If an algorithm $e'$ immediately rejects (in $k$ steps) all input of size bigger than some $k$, and on smaller than $k$ sized input takes at most $K$ steps, then it would be said to be a constant time algorithm. This is the sense in which my program $e'$ is constant time. It is true that the particular constants depend (exponentially as you mention) on $n$, but for the program $e'$, the number $n$ is constant and does not vary with the input to $e'$. I understand that you want to exclude this unsatisfactory algorithm, but it seems to me that your requirements do not technically exclude it. $\endgroup$ Feb 28, 2012 at 0:55
  • 1
    $\begingroup$ @Jirka: The thing is that AFAICS, Joel is right, so I was trying to figure out a reasonable formulation of the problem that does not trivialize. Now I think that a better (and simpler) way, which preserves the spirit of your question but avoids pitfalls with the running time of Turing machines, is to change the definitions of $MIN^L$ and $MIN^P$ so that their input does not consist of a poly-time Turing machine, but a Boolean circuit. (Then you can omit $n$, as it can be read off from the circuit.) Even better, the output of the search problems should be modified so that it either finds ... $\endgroup$ Feb 28, 2012 at 12:02

1 Answer 1

3
$\begingroup$

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}$?

$\endgroup$
6
  • $\begingroup$ Note this sentence in the question: Machine $T$ ... and is constructed to guarantee termination in polynomial time. By this I intended to say, not only $T$ terminates in some polynomial time bound, but a specific polynomial satisfying this is syntacticably checkable from its code. Even a machine that finishes in $O(n^k)$ but is not constructed in this arbitrary way would be considered an invalid Turing machine code passed to the oracle. In contrast, whether it actually computes a transitive relation is not necessarily checkable in polynomial time. $\endgroup$ Feb 26, 2012 at 11:10
  • $\begingroup$ Your reply doesn't seem to answer my objection. My point is that for the time complexity of $T$, the number $n$ is a constant. So even if $T$ takes time $2^{2^n}$ on all it's input, this is still linear time, indeed, it is constant time, and we can hardwire this bound into the code of $T$. In light of this, could you clarify the question to indicate exactly what you mean? Perhaps it would help if you gave the polynomial function a name and indicated with precision which input is used with it. $\endgroup$ Feb 26, 2012 at 11:34
  • $\begingroup$ I attempted a grammar fix now and I will fix the question further if it is still ambiguous or chaotic (please give it a second chance). $S$ does not take $T$. $S$, like $T$, takes a number (call it $l$) and a code of a (poly-time bounded) machine that provides an instance of $<^P$ (call it $U$). Then it queries the oracle (that represents $MIN^L$) with as many $T$'s as it wishes. Obviously, any $(n,T)$ is of polynomial size in $(l,U)$. $\endgroup$ Feb 26, 2012 at 22:35
  • $\begingroup$ And I really like and think about your "question within answer". It also served me very well to delete a misleading phrase "instances of" from my question. But the two questions are in many ways different: uniform reduction across all poly-time ordering relations in mine; many-one (aka Karp) reduction in yours versus Turing-style (aka Cook) reduction in mine; full linearization versus finding just the minimum. Neither implication is obvious. $\endgroup$ Feb 26, 2012 at 23:00
  • 1
    $\begingroup$ I posted it as an MO question at: mathoverflow.net/questions/89668/… $\endgroup$ Feb 27, 2012 at 14:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.