# Problem NP-complete for Euclidean geometry but in P for Non-Euclidean geometry?

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?

• 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... Sep 7, 2011 at 0:25
• @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. Sep 7, 2011 at 1:51
• @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'" Sep 7, 2011 at 1:58
• 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). Sep 7, 2011 at 3:59
• @Sorin: Can you clarify what you mean by "non-Euclidean geometry"? Are you talking about a manifold? A metric space? Both? Something else? Sep 7, 2011 at 4:01