Есть ли проблемы, которые являются NP-полными при использовании евклидовой геометрии, но хорошо определены и разрешимы за полиномиальное время для некоторой неевклидовой геометрии?
reference-request
cg.comp-geom
Сорин Истраил
источник
источник
Ответы:
Частичный ответ:
Максимальная TSP полиномиально разрешаема по многогранным нормам, но NP-трудна для евклидовых норм (оптимизация, а также вариант решения). Является ли последний также NP-легким - это другой вопрос. (Возможно, вы сможете определить несколько искусственный вариант, который есть в NP, поскольку экземпляры, созданные для доказательства твердости NP, требуют только ограниченной точности.)
А. Барвинок, С. П. Фекете, Д. С. Джонсон, А. Тамир, Г. Дж. Вёджингер и Р. Водрооф. Задача геометрического максимума коммивояжера. Журнал ACM, 50: 641-664, 2003.
источник