Problema NP-completo para geometria euclidiana, mas em P para geometria não-euclidiana?

13

Existem problemas que são NP-completos ao usar a geometria euclidiana, mas são bem definidos e solucionáveis ​​em tempo polinomial para alguma geometria não-euclidiana?

reference-request cg.comp-geom Sorin Istrail
fonte
3
Dadas as restrições de, por exemplo, ladrilhar na geometria não euclidiana, parece provável que alguns problemas "difíceis" no espaço euclidiano sejam trivialmente responsáveis ​​('não, esses não são ladrilhos') para geometrias não euclidianas ...
Steven Stadnicki
@Artem Kaznatcheev Eu removi "bem definido", já que um problema não pode ser solucionado (deixe solucionável em tempo polinomial), a menos que esteja bem definido. (Como você pode resolver um problema se nem sabe qual é o problema?) Assim, removi "definir bem" como redundante.
Tyson Williams
@ Tyson Bom ponto. Eu acho que algo como 'não trivial' faria mais sentido, já que é natural tentar evitar problemas (não o NPC, mas apenas o exemplo) como: "resolva se duas linhas são paralelas; você precisa fazer algum cálculo na geometria euclidiana e em esférico você apenas
produz
Eu trataria "bem definido" como um esclarecimento. Sim, solucionável implica uma definição bem definida, mas acredito que o questionador está esclarecendo que está primeiro procurando problemas que "fazem sentido" em um espaço não euclidiano, depois que deseja problemas solucionáveis ​​(em P).
9788 John Moeller # 1
@Sorin: Você pode esclarecer o que você quer dizer com "geometria não euclidiana"? Você está falando de uma variedade? Um espaço métrico? Ambos? Algo mais?
precisa saber é o seguinte

Respostas:

7

Resposta parcial:

O TSP máximo é passível de solução polinomial no tempo sob as normas poliédricas, mas é NP-difícil para as normas euclidianas (otimização e versão de decisão). Se o último também é NP-easy é uma questão diferente. (Você pode definir uma variante um tanto artificial que esteja no NP, pois as instâncias criadas para a prova de dureza do NP requerem apenas precisão limitada.)

A. Barvinok, SP Fekete, DS Johnson, A. Tamir, GJ Woeginger e R. Wodroofe. O problema geométrico máximo de Vendedor ambulante. Journal of the ACM, 50: 641-664, 2003.

Markus Bläser
fonte