¿Problema NP completo para geometría euclidiana pero en P para geometría no euclidiana?

13

¿Hay algún problema que sea NP completo cuando se usa geometría euclidiana pero que está bien definido y puede resolverse en tiempo polinómico para alguna geometría no euclidiana?

reference-request cg.comp-geom Sorin Istrail
fuente
3
Dadas las limitaciones de ejemplo de segmentación en la geometría no euclidiana, tt parece probable que algunos problemas que son 'duros' en el espacio euclidiano serían responsables trivial ( 'no, estos no hacen baldosas') para geometrías no euclidianas ...
Steven Stadnicki
@Artem Kaznatcheev Eliminé "bien definido" ya que un problema no puede resolverse (dejar que se solucione en tiempo polinómico) a menos que esté bien definido. (¿Cómo puede resolver un problema si ni siquiera sabe cuál es el problema?) Por lo tanto, eliminé "definir bien" como redundante.
Tyson Williams
@Tyson Buen punto. Supongo que algo como 'no trivial' tendría más sentido, ya que es natural tratar de evitar problemas (no NPC, sino solo un ejemplo) como: "resolver si dos líneas son paralelas; tienes que hacer algunos cálculos en geometría euclidiana y en forma esférica simplemente
emites
Trataría "bien definido" como una aclaración. Sí, resolver implica una buena definición, pero creo que el interrogador aclara que primero están buscando problemas que "tengan sentido" en un espacio no euclidiano, luego que quieren problemas que puedan resolverse (en P).
Josephine Moeller
@Sorin: ¿Puedes aclarar lo que quieres decir con "geometría no euclidiana"? ¿Estás hablando de una variedad? ¿Un espacio métrico? ¿Ambos? ¿Algo más?
Josephine Moeller

Respuestas:

7

Respuesta parcial:

El TSP máximo es un tiempo polinómico que se puede resolver bajo las normas poliédricas, pero NP-duro para las normas euclidianas (versión de optimización y decisión). Si este último también es NP-easy es una pregunta diferente. (Es posible que pueda definir una variante algo artificial que está en NP, ya que las instancias creadas para la prueba de dureza NP solo requieren precisión limitada).

A. Barvinok, SP Fekete, DS Johnson, A. Tamir, GJ Woeginger y R. Wodroofe. El problema geométrico del vendedor ambulante máximo. Journal of the ACM, 50: 641-664, 2003.

Markus Bläser
fuente