NP-полная задача для евклидовой геометрии, но в P для неевклидовой геометрии?

13

Есть ли проблемы, которые являются NP-полными при использовании евклидовой геометрии, но хорошо определены и разрешимы за полиномиальное время для некоторой неевклидовой геометрии?

reference-request cg.comp-geom Сорин Истраил
источник
3
Учитывая ограничения, например, на мозаику в неевклидовой геометрии, кажется вероятным, что некоторые проблемы, которые являются «трудными» в евклидовом пространстве, будут несложно отвечать («нет, это не мозаика») для неевклидовой геометрии ...
Стивен Стадницки
@Artem Kaznatcheev Я удалил «хорошо определенные», так как проблема не может быть решена (пусть и разрешима за полиномиальное время), если она не является четко определенной. (Как вы можете решить проблему, если вы даже не знаете, в чем проблема?) Таким образом, я удалил «хорошо определенное» как избыточное.
Тайсон Уильямс
@ Тайсон Хороший вопрос. Я предполагаю, что что-то вроде «нетривиально» имело бы больше смысла, так как естественно попытаться избежать проблем (не NPC, а просто пример), таких как: «решить, если две линии параллельны; вы должны сделать некоторые вычисления в евклидовой геометрии а в сферическом вы просто
выводите
Я бы отнесся к «четко определенным» как к разъяснению. Да, разрешимый подразумевает четкую определенность, но я полагаю, что спрашивающий разъясняет, что они сначала ищут проблемы, которые «имеют смысл» в неевклидовом пространстве, а затем хотят, чтобы проблемы были разрешимы (в P).
Жозефина Меллер
@ Сорин: Вы можете уточнить, что вы подразумеваете под "неевклидовой геометрией"? Вы говорите о коллекторе? Метрическое пространство? И то и другое? Что-то другое?
Жозефина Меллер

Ответы:

7

Частичный ответ:

Максимальная TSP полиномиально разрешаема по многогранным нормам, но NP-трудна для евклидовых норм (оптимизация, а также вариант решения). Является ли последний также NP-легким - это другой вопрос. (Возможно, вы сможете определить несколько искусственный вариант, который есть в NP, поскольку экземпляры, созданные для доказательства твердости NP, требуют только ограниченной точности.)

А. Барвинок, С. П. Фекете, Д. С. Джонсон, А. Тамир, Г. Дж. Вёджингер и Р. Водрооф. Задача геометрического максимума коммивояжера. Журнал ACM, 50: 641-664, 2003.

Маркус Блезер
источник