Problem NP-zupełny dla geometrii euklidesowej, ale w P dla geometrii innej niż euklidesowa?

Czy są jakieś problemy, które są NP-całkowite przy stosowaniu geometrii euklidesowej, ale są dobrze zdefiniowane i możliwe do rozwiązania w czasie wielomianowym dla niektórych geometrii nie-euklidesowych?

reference-request cg.comp-geom Sorin Istrail
źródło

Biorąc pod uwagę ograniczenia np. Kafelkowania w geometrii innej niż euklidesowa, wydaje się prawdopodobne, że niektóre problemy, które są „twarde” w przestrzeni euklidesowej, byłyby trywialnie możliwe („nie, nie kafelkują”) w przypadku geometrii innych niż euklidesowe ...

Steven Stadnicki

@Artem Kaznatcheev Usunąłem „dobrze zdefiniowany”, ponieważ problem nie może być rozwiązany (niech rozwiązany w czasie wielomianowym), chyba że jest dobrze zdefiniowany. (Jak możesz rozwiązać problem, jeśli nawet nie wiesz, na czym polega problem?) Dlatego usunąłem „dobrze zdefiniowane” jako zbędne.

Tyson Williams,

@Tyson Dobry punkt. Myślę, że coś w rodzaju „nietrywialne” miałoby większy sens, ponieważ naturalne jest unikanie problemów (nie NPC, ale tylko przykład), takich jak: „rozwiąż, jeśli dwie linie są równoległe; musisz wykonać obliczenia w geometrii euklidesowej a w kulistym po prostu

wypisujesz

Traktowałbym „dobrze zdefiniowany” jako wyjaśnienie. Tak, rozwiązalny oznacza dobrze zdefiniowany, ale wierzę, że pytający wyjaśnia, że najpierw szukają problemów, które „mają sens” w przestrzeni nie-euklidesowej, a następnie, że chcą problemów, które można rozwiązać (w P).

Josephine Moeller

@Sorin: Czy możesz wyjaśnić, co rozumiesz przez „geometrię nieeuklidesową”? Mówisz o różnorodności? Przestrzeń metryczna? Obie? Coś innego?

Josephine Moeller

Problem NP-zupełny dla geometrii euklidesowej, ale w P dla geometrii innej niż euklidesowa?

Odpowiedzi: