most recent 30 from http://mathoverflow.net 2013-05-22T04:41:14Z http://mathoverflow.net/feeds/question/76056 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/76056/undecidable-problems-in-geometry Martin Tancer 2011-09-21T12:56:35Z 2011-09-22T20:52:02Z

<p>Are there any (many) algorithmically undecidable problems in computational (combinatorial/discrete) geometry?</p> <p>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.</p> <p>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.</p> <p>(Let me also exclude problems very similar to Wang tiles if there are any.)</p>

http://mathoverflow.net/questions/76056/undecidable-problems-in-geometry/76057#76057 Igor Rivin 2011-09-21T13:13:07Z 2011-09-21T13:13:07Z

<p>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...)</p>

http://mathoverflow.net/questions/76056/undecidable-problems-in-geometry/76059#76059 Paul Siegel 2011-09-21T13:26:32Z 2011-09-21T13:26:32Z

<p>I'm vaguely aware of two examples, but I can't provide any references.</p> <p>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. </p> <p>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. </p>

http://mathoverflow.net/questions/76056/undecidable-problems-in-geometry/76162#76162 Bjørn Kjos-Hanssen 2011-09-22T20:52:02Z 2011-09-22T20:52:02Z

<p>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.)</p>