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?
3
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