46
$\begingroup$

The Robertson-Seymour theorem on graph minors leads to some interesting conundrums.

The theorem states that any minor-closed class of graphs can be described by a finite number of excluded minors. As testing for the presence of any given minor can be done in cubic time (albeit with astronomical constants) this implies that there exists a polynomial time algorithm for testing membership in any minor-closed class of graphs. Hence it seems reasonable that problem should be deemed to be in P.

However the RS theory does not give us even the faintest clue as to how to determine the guaranteed-finite set of excluded minors, and until we have these at hand, we may not have any algorithm of any sort. Worse still, there is no known algorithm to actually find the excluded minors and even if you have a big list of them, there is no way that I know to verify that the list is actually complete. In fact, could it perhaps actually be undecidable to find the list of excluded minors?

So, does it make sense to view a problem as being simultaneously polynomial-time and undecidable? It seems a bit odd to me (who is not a particular expert in complexity) but maybe it's quite routine?

$\endgroup$
1
  • 12
    $\begingroup$ Just a tip on asking your question: you really have three questions in your post, and it would have helped the quality of the answers if you had been more intentional about it, in particular by numbering them. Because some posters are answering 1 only, some 2 only, and no-one yet has addressed 3, and it makes it a mess to read when they don't announce at the outset which they're doing. $\endgroup$ Dec 2, 2010 at 13:48

8 Answers 8

71
$\begingroup$

Consider the following simplified example of the same phenomenon, which many students find clarifying.

Let $f(n)=1$, if there are $n$ consecutive $7$s in the decimal expansion of $\pi$, and otherwise $f(n)=0$. Is this function computable?

A naive attempt to compute $f(n)$ would simply proceed to search $\pi$ for $n$ consecutive $7$s. If found, the algorithm outputs $1$, but otherwise....and then the naive algorithm doesn't seem to know when to output $0$, and so students sometimes expect that $f$ is not computable.

But actually, $f$ is a computable function. If it happens that there are arbitrarily long sequences of $7$s in the decimal expansion of $\pi$, an open question, then $f$ is the constant $1$ function, which is certainly computable. Otherwise, there is some longest sequence of $7$s in $\pi$, having length $N$, and so $f$ is the function that is $1$ up to $N$ and then $0$ above $N$. And this function also is computable, for any particular $N$.

So the situation is that we have proved that $f$ is computable by exhibiting several algorithms, and proving that $f$ is definitely computed by one of them, but we don't know which one. (In fact, $f$ is linear time computable.) So we have proved that $f$ is a computable function, but by a pure existence proof that merely shows there is an algorithm computing $f$, without explicitly exhibiting it.

It seems to be the same phenomenon in your case, where you have a computable function, but you don't know which algorithm computes it.


Addition. Let me try to address Thierry Zell's concern about the third question. To my way of thinking, the phenomenon of the question is an instance of the problem of uniformity of algorithms, a pervasively considered issue in computability theory.

To illustrate, consider the question of whether a given program $p$ halts on input $0$ before another program $q$. Let $f_p(q)=1$ if it does and otherwise $f_p(q)=0$. Every such function $f_p$ is computable, for similar reasons to my $\pi$ function $f$ above, since either $p$ doesn't halt at all on input $0$, in which case $f_p$ is identically $0$, or $p$ does halt in $N$ steps, in which case we need only run $q$ for $N$ steps to see if it halts, and give our output for $f_p(q)$ by that time. So each $f_p$ is a computable function. But the joint function $f(p,q)=f_p(q)$, a binary function, is not computable (if it were, then we could solve the halting problem: to decide if $p$ halts on input $0$, design a program $q$ that would take one step extra after a halt, and ask if $p$ halts before $q$).

In other words, the function $f(p,q)$ is computable for any fixed $p$, but not uniformly in $p$. And such uniformity issues are ubiquitous in computability theory.

In the example of the question, each class of graphs is decidable, but not uniformly so, since by Tony's answer there is no uniform algorithm, given a description of the class, to find the collection of excluded minors. But for any such fixed class, the membership question is decidable.

The issue of whether a given algorithm is uniform in a given parameter is a very common concern in computability theory, and occurs throughout the subject.

$\endgroup$
5
  • 6
    $\begingroup$ This is like the ${\sqrt 2}^{\sqrt 2}$ example. $\endgroup$ Dec 2, 2010 at 13:58
  • $\begingroup$ @Frank: doesn't that mean the same thing? $\endgroup$ Dec 2, 2010 at 16:04
  • 2
    $\begingroup$ Frank, I had the interpretation that if you have fifteen consecutive $7$s, then the first eleven of them would count as eleven consecutive $7$s. So the function really would be as I describe it. Otherwise, I suppose, one should speak of *maximal* consecutive sequences of $7$s, and I believe that it is an open question whether the corresponding function is computable. (Although if $\pi$ is normal, then this function also would be identically $1$.) $\endgroup$ Dec 2, 2010 at 17:03
  • 1
    $\begingroup$ This reminds me of a very similar problem on a problem set I once did regarding the definition of decidability of a language. The problem was this: Let L = {0} if there is life in the universe outside our solar system, and L = {1} if the only life in the universe is inside our solar system. Then the question is: is L decidable? $\endgroup$ Dec 3, 2010 at 4:10
  • 1
    $\begingroup$ @Joel, a link to this fine answer has been added to the TCS StackExchange question "Do the undecidable attributes of P pose an obstruction to deciding P versus NP?" ... I wish to thank Alex ten Brink for drawing attention to this answer. $\endgroup$ Jun 28, 2011 at 13:13
28
$\begingroup$

As others have mentioned, the answer to your title question is strictly speaking no. With regards to your other questions, it has been proven that it is undecidable to compute the excluded minors for a minor-closed class $\mathcal{C}$, unless $\mathcal{C}$ is presented to you in a silly way. Of course, there is no paradox, because this does not imply that the related problem of determining if an input graph $G$ is in $\mathcal{C}$ is undecidable. Indeed, as you mention by the Robertson-Seymour theory, this second problem is not only decidable, but is in P.

I guess I should quantify what I mean by non-silly representations of minor-closed families. Fellows and Langston proved that if your minor-closed class $\mathcal{C}$ is given by a Turing machine $M$, then it is undecidable to compute an excluded minor characterization of $\mathcal{C}$. Courcelle, Downey, and Fellows proved that if $\mathcal{C}$ is instead given by a monadic second-order logic formula $\phi$, then it is also undecidable to compute an excluded minor characterization of $\mathcal{C}$.

There are positive results for certain minor-closed families. For example, this paper by Adler, Grohe, and Kreutzer shows that for any fixed $k$, they can compute the excluded minors for the class of graphs of tree-width at most $k$. For the undecidability results that I mentioned above, the references are:

M.R. Fellows and M.A. Langston. On search, decision and the efficiency of polynomial-time algorithms (extended abstract). In Proceedings of the 21st ACM Symposium on Theory of Computing, pages 501–512, 1989.

B. Courcelle, R.G. Downey, and M.R. Fellows. A note on the computability of graph minor obstruction sets for monadic second order ideals. Journal of Universal Computer Science, 3:1194–1198, 1997.

$\endgroup$
1
16
$\begingroup$

Of course, every problem in P is decidable by definition of P. This was mentioned in the previous answers.

But there is another problem here that hasn't been addressed yet:
you apparently are looking for an algorithm that takes as input a class closed under minors and a finite graph and decides whether or not the finite graph is in the class.
Or you are looking for an algorithm that takes a class closed under minors and produces an polynomial time algorithm that decides membership to the class.

Here is the problem: How do you present a class of graphs closed under minors? A priori, it is not clear that every class of graphs that is closed under minors (usually a class containing graphs of infinitely many isomorphism classes) has a reasonable representation as a finite object (that can be treated algorithmically) at all. By finite representation I mean a formula that defines the class in one way or other or something similar.

Now, the graph minor theorem gives us a nice representation of every such class: Just list the finite set of forbidden minors. If this is your representation of the class, then you get your polynomial time algorithm that decides membership for the class.

If you settle on another representation (and you have to come up with some uniform way to describe your class by finite objects to be able to say anything algorithmically at all, I would think), it might not be possible to come up with an algorithm that computes the finitely many forbidden minors from the representation of the class.

$\endgroup$
9
$\begingroup$

Donald Knuth made such a prediction in a poll ( http://www.cs.umd.edu/~gasarch/papers/poll.pdf ) about when P vs NP would be settled:

It will be solved by either 2048 or 4096. I am currently somewhat pessimistic. The outcome will be the truly worst case scenario: namely that someone will prove “P=NP because there are only finitely many obstructions to the opposite hypothesis”; hence there will exists a polynomial time solution to SAT but we will never know its complexity!

$\endgroup$
5
$\begingroup$

It seems to me there are two levels operating here.

For any given minor-closed class of graphs, there is some finite set of excluded minors, and hence there is a polynomial time algorithm for testing membership of that class (we don't need to explicity know what the algorithm is, we simply know it exists.)

However, on the level above, writing out that algorithm explicitly involves finding a finite set of excluded minors explicitly, and that might be hard/undecidable.

$\endgroup$
2
  • 1
    $\begingroup$ More to the point, the 'level above' isn't even well-defined algorithmically - how are you specifying a 'minor-closed class' as input? A fairly general way would be to specify it as a first-order predicate perhaps, and then you are likely to run into undecidability problems. Of course if you make use of R-S results and specify the minor-closed class by a finite set of excluded minors, then the 'level above' becomes rather trivial. $\endgroup$
    – ndkrempel
    Dec 2, 2010 at 9:36
  • $\begingroup$ I can't seem to find the paper now, but I recall reading a proof that the "level above" problem (given, I believe, a first-order predicate for the minor-closed class) is not decidable. $\endgroup$ Dec 2, 2010 at 18:42
3
$\begingroup$

A problem is in P if it is decidable in polynomial time. So if it is undecidable, it is neither in P nor in NP. It is not even recursive. See http://en.wikipedia.org/wiki/Complexity_class.

$\endgroup$
4
  • 1
    $\begingroup$ You just want "recursive" there instead of "recursively enumerable". Plenty of things are undecidable yet r.e. The theorems of PA for instance (and more to the point, any non-recursive r.e. set). $\endgroup$
    – Ed Dean
    Dec 2, 2010 at 9:21
  • $\begingroup$ Indeed ! Should not be confused between "recursive" and "recursively enumerable". Thanks. $\endgroup$
    – Lamine
    Dec 2, 2010 at 9:36
  • 6
    $\begingroup$ This is strictly speaking true, but not really getting at the paradox that's bothering gordon-royle. One reasonable interpretation of Robertson-Seymour is that in some abstract non-constructive sense it proves the existence of a polynomial-time algorithm for a problem. To use the algorithm, you need a finite amount of data, but it's known that there's no algorithm for finding that data (Tony Huynh gives references in his answer). It's a pretty weird situation. $\endgroup$
    – arsmath
    Dec 2, 2010 at 15:04
  • $\begingroup$ Is there some confusion between decision problems and the computation of their solutions ? A (decision) problem on the existence of a solution of length k can be in P but compute this solution can be exponential, nay currently impossible. This is precisely due to non-constructive proof procedure. $\endgroup$
    – Lamine
    Dec 3, 2010 at 8:28
2
$\begingroup$

I think the same phenomenon is easier to understand in the Domino Problem. It is undecidable whether a given set can tile the plane or not. This means that if your input is a set, then no algorithm can output the answer. However, for any fixed set, the answer is either Yes or No, so a trivial algorithm (that has no input) answers it. Just in the case of minors, even for a fixed set, we have another input (the graph) and we need Robertson-Seymour.

$\endgroup$
1
$\begingroup$

If G is a minor of H, that fact can be proven in P-time (by demonstrating the reduction). That means if there is an unknown P-time algorithm ($O(|H|^3)$ in this case) for deciding if a fixed G is a minor of a given H, then unless I'm mistaken, there is also a known concrete algorithm for deciding this, namely Levin's universal search.

$\endgroup$

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.