Problème NP-complet pour la géométrie euclidienne mais en P pour la géométrie non euclidienne?

13

Y a-t-il des problèmes qui sont NP-complets lors de l'utilisation de la géométrie euclidienne mais qui sont bien définis et résolubles en temps polynomial pour une géométrie non euclidienne?

Sorin Istrail
la source
3
Étant donné les contraintes, par exemple, de la mosaïque dans la géométrie non euclidienne, tt semble probable que certains problèmes qui sont `` durs '' dans l'espace euclidien seraient trivialement responsables (`` non, ils ne tuiles pas '') pour les géométries non euclidiennes ...
Steven Stadnicki
@Artem Kaznatcheev J'ai supprimé "bien défini" car un problème ne peut pas être résolu (laissez-le résolu en temps polynomial) à moins qu'il ne soit bien défini. (Comment pouvez-vous résoudre un problème si vous ne savez même pas quel est le problème?) Ainsi, j'ai supprimé "bien défini" comme redondant.
Tyson Williams
@Tyson Bon point. Je suppose que quelque chose comme «non trivial» aurait plus de sens, car il est naturel d'essayer d'éviter les problèmes (pas NPC, mais juste un exemple) comme: «résoudre si deux lignes sont parallèles; vous devez faire un calcul en géométrie euclidienne et en sphère vous sortez simplement 'non' "
Artem Kaznatcheev
Je considérerais «bien défini» comme une clarification. Oui, résoluble implique une définition bien définie, mais je pense que le questionneur clarifie qu'il cherche d'abord des problèmes qui "ont du sens" dans un espace non euclidien, puis qu'il veut des problèmes qui sont résolubles (en P).
Josephine Moeller
@Sorin: Pouvez-vous clarifier ce que vous entendez par "géométrie non euclidienne"? Parlez-vous d'un collecteur? Un espace métrique? Tous les deux? Autre chose?
Josephine Moeller

Réponses:

7

Réponse partielle:

Le TSP maximum est résolu dans le temps polynomial sous les normes polyédriques, mais NP-dur pour les normes euclidiennes (optimisation ainsi que version de décision). Que ce dernier soit également NP-easy est une question différente. (Vous pourrez peut-être définir une variante quelque peu artificielle qui se trouve dans NP, car les instances créées pour la preuve de dureté NP ne nécessitent qu'une précision limitée.)

A. Barvinok, SP Fekete, DS Johnson, A. Tamir, GJ Woeginger et R. Wodroofe. Le problème géométrique du voyageur de commerce maximum. Journal de l'ACM, 50: 641-664, 2003.

Markus Bläser
la source