Are there any problems that are NP-complete when using Euclidean geometry but are well-defined and solvable in polynomial time for some non-euclidean geometry?
$\begingroup$
$\endgroup$
8
-
3$\begingroup$ Given the constraints on e.g. tiling in non-Euclidean geometry, tt seems likely that some problems that are 'hard' in Euclidean space would be trivially answerable ('no, these don't tile') for non-Euclidean geometries... $\endgroup$– Steven StadnickiSep 7, 2011 at 0:25
-
$\begingroup$ @Artem Kaznatcheev I removed "well-defined" since a problem cannot be solvable (let along solvable in polynomial time) unless it is well-defined. (How can you solve a problem if you don't even know what the problem is?) Thus, I removed "well-define" as redundant. $\endgroup$– Tyson WilliamsSep 7, 2011 at 1:51
-
$\begingroup$ @Tyson Good point. I guess something like 'non-trivial' would make more sense, since it is natural to try to avoid problems (not NPC, but just example) like: "solve if two lines are parallel; you have to do some computation in Euclidean geometry and in spherical you just output 'no'" $\endgroup$– Artem Kaznatcheev ♦Sep 7, 2011 at 1:58
-
$\begingroup$ I would treat "well-defined" as a clarification. Yes, solvable implies well-definedness, but I believe that the questioner is clarifying that they are first looking for problems that "make sense" in a non-Euclidean space, then that they want problems that are solvable (in P). $\endgroup$– Josephine MoellerSep 7, 2011 at 3:59
-
$\begingroup$ @Sorin: Can you clarify what you mean by "non-Euclidean geometry"? Are you talking about a manifold? A metric space? Both? Something else? $\endgroup$– Josephine MoellerSep 7, 2011 at 4:01
|
Show 3 more comments
1 Answer
$\begingroup$
$\endgroup$
Partial answer:
Maximum TSP is polynomial time solvable under polyhedral norms, but NP-hard for Euclidean norms (optimization as well as decision version). Whether the latter is also NP-easy is a different question. (You might be able to define a somewhat artifical variant that is in NP, since the instances created for the NP-hardness proof only require bounded precision.)
A. Barvinok, S. P. Fekete, D. S. Johnson, A. Tamir, G. J. Woeginger, and R. Wodroofe. The geometric maximum Traveling Salesman problem. Journal of the ACM, 50:641-664, 2003.
