Soal NP-lengkap untuk geometri Euclidean tetapi dalam P untuk geometri Non-Euclidean?

13

Apakah ada masalah yang NP-lengkap ketika menggunakan geometri Euclidean tetapi didefinisikan dengan baik dan dipecahkan dalam waktu polinomial untuk beberapa geometri non-euclidean?

reference-request cg.comp-geom Sorin Istrail
sumber
3
Mengingat kendala pada misalnya pengerjaan ubin dalam geometri non-Euclidean, sepertinya kemungkinan bahwa beberapa masalah yang 'sulit' dalam ruang Euclidean akan secara sepele dijawab ('tidak, ini bukan ubin') untuk geometri non-Euclidean ...
Steven Stadnicki
@Artem Kaznatcheev saya menghapus "terdefinisi dengan baik" karena masalah tidak dapat dipecahkan (biarkan dipecahkan dalam waktu polinomial) kecuali itu didefinisikan dengan baik. (Bagaimana Anda bisa menyelesaikan masalah jika Anda bahkan tidak tahu apa masalahnya?) Jadi, saya menghapus "definisi-baik" sebagai berlebihan.
Tyson Williams
@Tyson Poin bagus. Saya kira sesuatu seperti 'non-sepele' akan lebih masuk akal, karena itu wajar untuk mencoba menghindari masalah (bukan NPC, tetapi hanya contoh) seperti: "pecahkan jika dua garis paralel; Anda harus melakukan perhitungan dalam geometri Euclidean dan di bola Anda hanya output 'tidak'"
Artem Kaznatcheev
Saya akan memperlakukan "didefinisikan dengan baik" sebagai klarifikasi. Ya, solvable menyiratkan definisi yang baik, tetapi saya percaya bahwa si penanya mengklarifikasi bahwa mereka pertama-tama mencari masalah yang "masuk akal" dalam ruang non-Euclidean, kemudian mereka menginginkan masalah yang dapat dipecahkan (dalam P).
Josephine Moeller
@ Korin: Bisakah Anda mengklarifikasi apa yang Anda maksud dengan "geometri non-Euclidean"? Apakah Anda berbicara tentang bermacam-macam? Ruang metrik? Kedua? Sesuatu yang lain
Josephine Moeller

Jawaban:

7

Sebagian jawaban:

TSP maksimum adalah waktu polinomial yang dapat dipecahkan di bawah norma polihedral, tetapi NP-hard untuk norma Euclidean (optimisasi serta versi keputusan). Apakah yang terakhir ini juga NP-easy adalah pertanyaan yang berbeda. (Anda mungkin dapat mendefinisikan varian agak artifisial yang ada di NP, karena instance yang dibuat untuk bukti kekerasan NP hanya membutuhkan ketelitian yang terikat.)

A. Barvinok, SP Fekete, DS Johnson, A. Tamir, GJ Woeginger, dan R. Wodroofe. Masalah geometri Traveling Salesman maksimum. Jurnal ACM, 50: 641-664, 2003.

Markus Bläser
sumber