<p>Partial answer:</p>

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

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

CC BY-SA 3.0
2011-09-07T12:09:38.250Z
2011-09-07T12:09:38.250Z
Markus Bläser
<p>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?</p>

CC BY-SA 3.0
2011-09-07T00:25:05.593Z
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...
Steven Stadnicki
CC BY-SA 3.0
2011-09-07T01:51:20.433Z
@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.
Tyson Williams
CC BY-SA 3.0
2011-09-07T01:58:08.617Z
@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'"
Artem Kaznatcheev
CC BY-SA 3.0
2011-09-07T03:59:44.763Z
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).
Josephine Moeller
CC BY-SA 3.0
2011-09-07T04:01:43.943Z
@Sorin: Can you clarify what you mean by "non-Euclidean geometry"? Are you talking about a manifold? A metric space? Both? Something else?
Josephine Moeller
CC BY-SA 3.0
2011-09-07T04:28:36.240Z
I'm guessing anything non-euclidean is "allowed" here.
Suresh Venkat
CC BY-SA 3.0
2011-09-07T13:56:01.863Z
@Artem Kaznatcheev Yes, I like "non-trivial" as well. #John Moeller Do you agree with using "non-trivial" in place of "well-defined"?
Tyson Williams
CC BY-SA 3.0
2011-09-07T15:55:55.260Z
Eh, not ideal in my opinion, but it works.
Josephine Moeller
<reference-request><cg.comp-geom>
Problem NP-complete for Euclidean geometry but in P for Non-Euclidean geometry?
Sorin Istrail
# Problem NP-complete for Euclidean geometry but in P for Non-Euclidean geometry?

(Asked by: username_0 on 2011-09-07)

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?

**Tags:** reference-request, cg.comp-geom
> **Comments:**
> **username_1**: 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...  
> **username_2**: @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.  
> **username_3**: @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'"  
> **username_4**: 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).  
> **username_4**: @Sorin: Can you clarify what you mean by "non-Euclidean geometry"? Are you talking about a manifold? A metric space? Both? Something else?  
> **username_5**: I'm guessing anything non-euclidean is "allowed" here.  
> **username_2**: @Artem Kaznatcheev Yes, I like "non-trivial" as well. #John Moeller Do you agree with using "non-trivial" in place of "well-defined"?  
> **username_4**: Eh, not ideal in my opinion, but it works.  

---

## 1 answers

### Answer by username_6 on 2011-09-07. Score: 7

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.


---

