Are there any (many) algorithmically undecidable problems in computational (combinatorial/discrete) geometry?

Update: the Wang tiles answer the question with "any". (I have somewhat overlooked to count them when I was browsing the answers to general undecidable problems.) But I still suspect that there are not many examples naturally arising in combinatorial/discrete geometry. And I am of course interested in any such example. I do not count artificial reformulations of problems stated (by the authors) in different settings.

For instance, it was open for quite some time whether STRING graphs (intersection graphs of curves in the plane) are recognizable. However, it turned out that they indeed are. If the answer was opposite, it would be an example of problem I seek for.

(Let me also exclude problems very similar to Wang tiles if there are any.)

  • 5
    $\begingroup$ In principle I agree with Igor. If you are interested in a list of such problems, please say so and use the big-list tag. (In this case you should also turn the question into Community Wiki mode; edit and tick the checkbox). If you are not so much after a list, but rather something else, please elaborate on what it is more precsiely. $\endgroup$ – user9072 Sep 21 '11 at 13:52
  • $\begingroup$ You may find something in the following link: www-math.mit.edu/~poonen/slides/cantrell3.pdf $\endgroup$ – M P Sep 21 '11 at 16:47

The problem to determine whether two 4-manifolds, given as simplicial complexes, are homeomorphic. This was shown to be undecidable by Markov. (Some theories of physics involve a sum over such manifolds, one additive term for each homeomorphism class, and this lead to speculation that physics was noncomputable in some sense [Geroch and Hartle 1986]. I am not sure what the current status of that is.)

  • $\begingroup$ John Stillwell in his book "Classical Topology and Combinatorial Group Theory" 1980, gives an excellent background to this archetypal undecidable geometry problem. He shows the full proof for the case of 5-manifolds, which turns out quite a bit simpler than 4-manifolds, but (apparently) has much of the flavour of the Markov proof. I say apparently because I only understand the one for 5-manifolds $\endgroup$ – WetSavannaAnimal Sep 23 '11 at 10:31

I'm vaguely aware of two examples, but I can't provide any references.

The first is the colored tiling problem. Suppose you're given a finite collection of squares of equal size such that each edge of each square is colored. The collection is said to tile the plane if you can arrange (possibly infinitely many) copies of the squares in the collection in a grid pattern on the plane such that whenever two squares are adjacent along an edge the edge colors match up. It turns out that the problem of determining when a given collection of colored squares tiles the plane contains the halting problem and hence is undecidable.

The second is the problem of determining when two triangulated manifolds are homotopy equivalent. An algorithm for making this determination would necessarily give a solution to the word problem for groups, so it's undecidable.

  • $\begingroup$ Thank you, the second one I am aware of and I rather count it as a topological problem. $\endgroup$ – Martin Tancer Sep 21 '11 at 13:55
  • 3
    $\begingroup$ @Paul: Your first example is known as Wang Tiles: en.wikipedia.org/wiki/Wang_tile . $\endgroup$ – Joseph O'Rourke Sep 21 '11 at 14:36
  • 1
    $\begingroup$ Paul's second example was mentioned by Scott Carnahan in reply to the MO question "What are the most attractive Turing-undecidable problems in mathematics?": mathoverflow.net/questions/11540 . $\endgroup$ – Joseph O'Rourke Sep 21 '11 at 15:28

Yes, there are. If you want to get a more informative answer, you might want to ask a more informative question (like, what circle of problems you actually mean...)

  • $\begingroup$ Well, in this case I have rather asked more general question in hope to get various examples. Yes there are many branches of computational (combinatorial/discrete) geometry, but I am afraid that I am really not able to write down the complete list of all interesting branches: E.g., questions on points-lines-planes-...-hyperplanes-arrangements, Voronoi diagrams and their modifications, minimum enclosing balls, geometric Ramsey type problems, convex sets, convex huls, partitions, etc. $\endgroup$ – Martin Tancer Sep 21 '11 at 14:06
  • 3
    $\begingroup$ The problem is that essentially every problem (and thus every undecidable problem) can be phrased as a geometry problem, so you are basically asking for a list of undecidable problem (which is probably not recursively enumerable...) $\endgroup$ – Igor Rivin Sep 21 '11 at 14:19
  • 2
    $\begingroup$ Yes, with some effort they can be phrased in such a way. However, I still hope that there is a general feeling what is a problem from computational geometry (preferably cobminatorial/discrete). I am, of course, not interested in problems, that can be artificially rephrased into geometric ones, but rather in those that people really phrase as geometric ones. Thus, I am sorry, but I do not agree that the question is wrong because of this issue. (I agree that I originally did some mistake about tagging the question, but I tried to fix this.) $\endgroup$ – Martin Tancer Sep 21 '11 at 15:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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