Euclidean TSP dalam NP dan kompleksitas akar kuadrat

Dalam catatan kuliah ini oleh Ola Svensson: http://theory.epfl.ch/osven/courses/Approx13/Notes/lecture4-5.pdf , dikatakan bahwa kita tidak tahu apakah Euclidean TSP ada di NP:

Alasannya adalah karena kita tidak tahu bagaimana cara menghitung akar kuadrat secara efisien.

Di sisi lain ada makalah ini oleh Papadimitriou: http://www.sciencedirect.com/science/article/pii/0304397577900123 mengatakan itu adalah NP-lengkap, yang juga berarti itu dalam NP. Meskipun dia tidak membuktikannya di koran, saya pikir dia menganggap keanggotaan dalam NP sepele, seperti biasanya dengan masalah seperti itu.

Saya bingung dengan ini. Jujur, klaim bahwa kita tidak tahu apakah Euclidian TSP di NP mengejutkan saya, karena saya hanya menganggap itu sepele - mengambil tur TSP sebagai sertifikat, kita dapat dengan mudah memeriksa apakah itu tur yang valid. Tetapi masalahnya adalah bahwa mungkin ada beberapa akar kuadrat. Jadi catatan kuliah pada dasarnya mengklaim bahwa kita tidak bisa dalam waktu polinomial menyelesaikan masalah berikut:

Mengingat bilangan rasional , memutuskan apakah .$q_1,\ldots,q_n,A\in\mathbb{Q}$$\sqrt{q_1}+\cdots+\sqrt{q_n}\leq A$

Pertanyaan 1: Apa yang kita ketahui tentang masalah ini?

Ini memohon penyederhanaan berikut, yang tidak dapat saya temukan:

Pertanyaan 2: Apakah ini dapat direduksi ke kasus khusus ketika ? Apakah kasus khusus polinomial-waktu ini dapat dipecahkan?$n=1$

Memikirkannya sebentar, saya sampai pada hal ini. Kami ingin kompleksitas waktu polinomial sehubungan dengan jumlah bit input, yaitu, bukan ukuran angka itu sendiri. Kita dapat dengan mudah menghitung penjumlahan ke angka polinomial angka desimal. Untuk mendapatkan kasus yang buruk, kita memerlukan turunan dari untuk sedemikian rupa untuk setiap polinomial , ada bilangan bulat sedemikian sehingga dan menyetujui pertama dari ekspansi desimal. k = 1 , 2 , ... p k $q_{1,k},\ldots,q_{n,k},A_k\in\mathbb{Q}$$k=1,2,\ldots$$p$$k$ AkP(masukan-size$\sqrt{q_{1,k}}+\cdots+\sqrt{q_{n,k}}$$A_k$$p(\text{input-size})$

Pertanyaan 3: Apakah ada contoh nomor rasional seperti itu?

Tapi apa itu ? Ini tergantung pada cara angka-angka rasional diwakili! Sekarang saya ingin tahu tentang ini:$\text{input-size}$

Pertanyaan 4: Apakah secara algoritmik penting jika bilangan rasional diberikan sebagai rasio dua bilangan bulat (seperti ) atau dalam ekspansi desimal (seperti )? Dengan kata lain, adakah keluarga bilangan rasional sedemikian sehingga ukuran ekspansi desimal tidak dibatasi secara polinomi dalam ukuran representasi rasio atau sebaliknya?2,5334 ¯ $24/13$$2.5334\overline{567}$

Q1. Ini adalah masalah terbuka yang terkenal. Itu diketahui berada di tingkat keempat hierarki penghitungan , karena [ABKM] . Tidak diketahui menggunakan NP. Masalahnya tidak benar-benar dalam menghitung akar kuadrat seperti yang diklaim dalam catatan kuliah: bit akar kuadrat dari bilangan bulat dapat dihitung dalam polinomial waktu dalam dan bitsize bilangan bulat. Masalahnya adalah, seberapa tepatnya, seberapa dekat jumlah akar kuadrat dari bilangan bulat dapat mencapai bilangan bulat, tanpa benar-benar menjadi integral.$n$$n$

Q2. Kasus tentu saja mudah. Ini sama dengan , yang berada dalam waktu polinomial, karena kuadrat angka rasional adalah dalam waktu polinomial.q ≤ A $n=1$$q \le A^2$

Q3. Menurut halaman ini , yang paling dikenal adalah bahwa ada bilangan bulat , semuanya antara dan , sehingga . Ini adalah batas bawah dari pada jumlah bit yang perlu dihitung untuk masalah yang berpotensi lebih sulit yang memungkinkan koefisien negatif. Batas atas terbaik pada jumlah bit adalah eksponensial dalam . 1 n | ∑ k i = 1$a_1, \ldots, a_k, b_1, \ldots, b_k$$1$$n$Ω(2klogn)$| \sum_{i = 1}^k \sqrt{a_i} - \sum_{i = 1}^k \sqrt{b_i}| = O(n^{-2k + 3/2})$$\Omega(2k\log n)$$k$

Q4. Saya pikir representasi desimal bisa sangat tidak efisien. Panjang periode adalah urutan multiplikatif dari 10 modulo penyebut, yang bisa eksponensial dalam jumlah bit penyebut.

Kau menulis:

Di sisi lain ada makalah ini oleh Papadimitriou: http://www.sciencedirect.com/science/article/pii/0304397577900123 mengatakan itu adalah NP-lengkap, yang juga berarti itu dalam NP. Meskipun dia tidak membuktikannya di koran, saya pikir dia menganggap keanggotaan dalam NP sepele, seperti biasanya dengan masalah seperti itu.

Mengapa Anda tidak membaca koran saja, alih-alih memposting klaim omong kosong seperti itu? Di halaman 239, Papadimitriou dengan hati-hati membahas masalah-masalah ini dan mendefinisikan varian mendasar dari metrik Euclidean sebagai buktinya.