13
$\begingroup$

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?

$\endgroup$
  • 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 Stadnicki Sep 7 '11 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 Williams Sep 7 '11 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 '11 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$ – John Moeller Sep 7 '11 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$ – John Moeller Sep 7 '11 at 4:01
7
$\begingroup$

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.

$\endgroup$

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.