Problem NP-vollständig für euklidische Geometrie, aber in P für nicht-euklidische Geometrie?

13

Gibt es Probleme, die NP-vollständig sind, wenn die euklidische Geometrie verwendet wird, aber für einige nicht-euklidische Geometrien in der Polynomzeit gut definiert und lösbar sind?

reference-request cg.comp-geom Sorin Istrail
quelle
3
In Anbetracht der Einschränkungen für das Kacheln in nicht-euklidischer Geometrie scheint es wahrscheinlich, dass einige Probleme, die im euklidischen Raum "schwer" sind, für nicht-euklidische Geometrien trivial zu beantworten sind ("nein, diese kacheln nicht") ...
Steven Stadnicki
@Artem Kaznatcheev Ich habe "wohldefiniert" entfernt, da ein Problem nur dann lösbar ist (wenn es in polynomieller Zeit lösbar ist), wenn es genau definiert ist. (Wie können Sie ein Problem lösen, wenn Sie nicht einmal wissen, woran es liegt?) Daher habe ich "gut definiert" als redundant entfernt.
Tyson Williams
@Tyson Guter Punkt. Ich denke, etwas wie 'nicht-trivial' wäre sinnvoller, da es natürlich ist, Probleme zu vermeiden (nicht NPC, sondern nur ein Beispiel) wie: "lösen, wenn zwei Linien parallel sind, müssen Sie einige Berechnungen in euklidischer Geometrie durchführen und sphärisch
gibst
Ich würde "gut definiert" als Klarstellung behandeln. Ja, lösbar impliziert Klarheit, aber ich glaube, der Fragesteller stellt klar, dass er zuerst nach Problemen sucht, die in einem nichteuklidischen Raum "Sinn machen", und dann nach lösbaren Problemen (in P).
John Moeller
@ Sorin: Können Sie klarstellen, was Sie unter "nichteuklidischer Geometrie" verstehen? Sprechen Sie von einer Mannigfaltigkeit? Ein metrischer Raum? Beide? Etwas anderes?
John Moeller

Antworten:

7

Teilantwort:

Der maximale TSP ist nach polyedrischen Normen polynomiell zeitlösbar, nach euklidischen Normen jedoch NP-hart (Optimierungs- und Entscheidungsversion). Ob letzteres auch NP-easy ist, ist eine andere Frage. (Möglicherweise können Sie eine künstliche Variante in NP definieren, da die für den NP-Härtenachweis erstellten Instanzen nur eine begrenzte Genauigkeit erfordern.)

A. Barvinok, SP Fekete, DS Johnson, A. Tamir, GJ Woeginger und R. Wodroofe. Das geometrische maximale Problem des Handlungsreisenden. Journal of the ACM, 50: 641 & ndash; 664, 2003.

Markus Bläser
quelle