Dalam [1], Garey et al. mengidentifikasi apa yang kemudian dikenal sebagai Jumlah Masalah Roots Square dalam rangka menyelesaikan NP-Euclidean TSP.
Mengingat bilangan bulat dan , menentukan apakah
Mereka mengamati bahwa bahkan tidak jelas bahwa masalah ini adalah di NP karena tidak jelas apa angka minimal presisi yang diperlukan dalam perhitungan akar kuadrat untuk cukup membandingkan jumlah untuk . Namun, mereka mengutip batas atas paling dikenal di mana adalah "jumlah digit dalam ekspresi simbolik asli". Sayangnya, batas atas ini hanya disebabkan oleh komunikasi pribadi dari AM Odlyzko.
Adakah yang punya referensi yang tepat untuk batas atas ini? Atau, dengan tidak adanya referensi yang dipublikasikan, sketsa bukti atau bukti juga akan sangat membantu.
Catatan: Saya percaya bahwa ikatan ini dapat disimpulkan sebagai konsekuensi dari hasil yang lebih umum oleh Bernikel et. Al. [2] dari sekitar tahun 2000 tentang batasan pemisahan untuk kelas yang lebih besar dari ekspresi aritmatika. Saya sebagian besar tertarik pada referensi yang lebih kontemporer (yaitu: apa yang diketahui sekitar tahun 1976) dan / atau bukti yang khusus untuk kasus jumlah akar kuadrat.
Garey, Michael R., Ronald L. Graham, dan David S. Johnson. " Beberapa masalah geometris NP-lengkap ." Prosiding simposium ACM tahunan kedelapan tentang Teori komputasi. ACM, 1976.
Burnikel, Christoph, et al. " Pemisahan yang kuat dan mudah dikomputasi terikat untuk ekspresi aritmatika yang melibatkan radikal ." Algoritma 27.1 (2000): 87-99.
Jawaban:
Berikut ini adalah sketsa bukti yang agak ceroboh. MisalkanS=∑ni=1δiai−−√ dimanaδi∈{±1} . Ini adalah jumlah aljabar derajat paling banyak2n dan tinggi paling banyakH=(max(ai))n . Sekarang mudah untuk memeriksa apakahS=0 (dapat dilakukan bahkan diTC0 - lihatini). JikaS≠0 maka dibatasi dari0 oleh kuantitas (karena merupakan jumlah aljabar dan karenanya adalah nol non-akar dari polinom satu variabel) yang merupakan fungsi dari tingkat dan tinggi dari polinomial minimal S . Sayangnya, ketergantungan pada tingkat yang eksponensial dalam jumlah akar kuadrat (dan jika ai 's adalah bilangan prima yang berbeda, gelar ini terikat bahkan ketat, meskipun kasus evaluasi tanda mudah untuk menangani). Presisi diperlukan karenanya eksponensial dalam jumlah akar kuadrat, yang merupakan 2n -bits untuk S . Sekarang sudah cukup untuk memotong masing-masing ai−−√ to say210n bits untuk memastikan tandanya dijamin benar. Ini mudah dilakukan melalui banyak langkah dari iterasi Newton secara polinomi). Sekarang tinggal memeriksa apakah jumlahnya positif, yang hanya penjumlahan dan karenanya linear dalam jumlah bit dalam penjumlahan. Perhatikan bahwa perhitungan ini dalam waktu Polinomial pada mesin BSS. Perhatikan juga bahwa kita tidak melakukan perhitungan apa pun secara langsung dengan polinomial minimalS itu sendiri, yang dapat memiliki koefisien besar dan terlihat jelek, kita hanya menggunakannya untuk alasan tentang presisi yang kita perlukan untuk memotong akar kuadrat. Untuk lebih jelasnya, periksakertas Tiwari.
sumber