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

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?

reference-request cg.comp-geom Sorin Istrail
la source

É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

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

Réponses: