Apakah ada sudut pandang kompleksitas teorema Galois?

Teorema Galois secara efektif mengatakan bahwa seseorang tidak dapat mengekspresikan akar polinomial derajat> = 5 menggunakan fungsi rasional dari koefisien dan radikal - tidak dapatkah ini dibaca dengan mengatakan bahwa dengan polinomial tidak ada algoritma deterministik untuk menemukan akar?
Sekarang pertimbangkan sebuah pertanyaan keputusan dari formulir, "Diberikan polinomial berakar nyata dan angka k adalah akar ketiga dan keempat tertinggi setidaknya pada jarak k?" $p$ $p$

Sertifikat bukti untuk pertanyaan keputusan ini hanya akan menjadi set akar polinomial ini dan itu adalah sertifikat pendek dan karenanya sepertinya TAPI bukan teorema Galois yang mengatakan bahwa tidak ada algoritma deterministik apa pun untuk menemukan sertifikat untuk keputusan ini pertanyaan? (dan properti ini jika benar mengesampingkan algoritma apa pun untuk memutuskan jawaban atas pertanyaan ini) $NP$

Jadi di kelas kompleksitas apa pertanyaan keputusan ini berada?

Semua pertanyaan NP-lengkap yang saya lihat selalu memiliki algoritma waktu eksponensial sepele yang tersedia untuk menyelesaikannya. Saya tidak tahu apakah ini diharapkan menjadi properti yang harus selalu benar untuk semua pertanyaan NP-complete. Untuk pertanyaan keputusan ini sepertinya tidak benar.

complexity-theory np-complete np polynomials pengguna6818
sumber

Akar adalah sertifikat tetapi tidak jelas bagi saya bahwa itu adalah sertifikat pendek (yaitu, bahwa ada konstanta sehingga, untuk setiap polinomial, Anda dapat menuliskan akarnya dalam bit , di mana adalah jumlah bit yang diperlukan untuk menuliskan polinomial). Tetapi jika ada algoritma NP, ada algoritma eksponensial waktu yang sepele: cukup sebutkan semua sertifikat potensial dan lihat apakah ada yang berfungsi.

k

$k$

O (n^{k})

$O(n^k)$

n

$n$

David Richerby

Beberapa komentar: (1) Akar memiliki nilai absolut . (2) Urutan sturm dapat digunakan untuk mengisolasi akar polinomial. (3) Kita dapat memeriksa apakah ada dua akar pada jarak yang tepat , dan jika demikian, dengan menghitung GCD dan .

\sum_{i = 0}^{n} a_{i} x_{i}

$\sum_{i=0}^n a_i x_i$

max (1, \sum_{i = 0}^{n - 1} | a_{i} | / | a_{n} |)

$\max(1,\sum_{i=0}^{n-1} |a_i|/|a_n|)$

k

$k$

p (x)

$p(x)$

p (x + k)

$p(x+k)$

Yuval Filmus

@YuvalFilmus Dapatkah ide Anda di atas digunakan untuk memutuskan pertanyaan keputusan di atas? Tidak jelas apakah ini dapat digunakan untuk memutuskan pertanyaan ini - dalam waktu polinomial?

user6818

"Teorema Galois secara efektif mengatakan bahwa seseorang tidak dapat mengekspresikan akar polinomial derajat> = 5 menggunakan fungsi rasional dari koefisien dan radikal - tidak dapatkah ini dibaca dengan mengatakan bahwa dengan polinomial tidak ada algoritma deterministik untuk menemukan akar? " Tidak, karena algoritma waktu polinomial lebih kuat daripada fungsi rasional. Sebagai contoh, mereka dapat membagi case, iterate, create arrays dan loop over them dll.

sdcvvc

@ user6818 Teorema ini berkenaan dengan model komputasi spesifik - fungsi rasional radikal. Jika Anda mengubah model, itu tidak berlaku lagi. Misalnya, menurut MathWorld mathworld.wolfram.com/QuinticEquation.html dimungkinkan untuk menyelesaikan persamaan derajat 5 menggunakan fungsi theta Jacobi. Jika Anda baik-baik saja dengan algoritma yang mengembalikan root dalam 0,01 (atau yang diberikan ), teorema Galois tidak akan lagi mendiskualifikasi metode, karena angka apa pun dapat didekati dengan rasional.

ϵ > 0

$\epsilon > 0$

sdcvvc

Jawaban:

Koneksi yang menarik, namun teori Galois menyatakan bahwa tidak ada metode (konsisten) yang ada untuk menemukan akar kuintik menggunakan radikal , daripada mengatakan bahwa masalahnya memiliki solusi (misalnya jalur terpanjang) yang mungkin memerlukan waktu super-polinomial. Jadi saya akan mengatakan itu lebih terkait dengan ketidakpastian daripada kompleksitas.

Secara khusus, dalam teori Galois seseorang secara progresif membangun ekstensi kelompok akar-akar persamaan, dengan cara selangkah demi selangkah (menambahkan satu akar sekaligus). Dan semua kelompok ini harus dipecahkan, dalam arti tidak boleh ada ambiguitas dalam proses membangun ekstensi ini dalam urutan lain. Ada pertanyaan terkait pada MO tentang kompleksitas membangun kelompok Galois dari suatu persamaan .

Referensi lain di sini "TEORI GALOIS KOMPUTASI: INVARIAN DAN KOMPUTASI LEBIH DARI ", CLAUS FIEKER JURGEN KLUNERS $\mathbb{Q}$

Lebih jauh lagi, seseorang dapat secara sistematis mewakili akar dari persamaan polinomial menggunakan radikal (ketika persamaan dapat dipecahkan dengan menggunakan radikal) berdasarkan pada konstruksi kelompok Galois (s) dari persamaan tersebut. Ref: "Representasi Radikal Akar Polinomial", Hirokazu Anai Kazuhiro Yokoyama 2002

Kompleksitas komputasi untuk menentukan apakah polinomial tak tereducikan yang diberikan pada bilangan bulat , dapat larut oleh radikal adalah dalam Ref "Solvabilitas oleh Radikal Berada dalam Waktu Polinomial", S. Landau GL Miller 1984 $\mathbb{Z}$ $\mathbb{P}$

Sebuah survei dari "Teknik Komputasi Galois" baru-baru ini, Alexander Hulpke

Tentu saja jika seseorang mencari algoritma aproksimasi yang baik dan kompleksitasnya (misalnya metode Newton atau Teorema Sturm) ini adalah pertanyaan yang sedikit berbeda dan jawaban yang sudah diposting memberikan informasi lebih banyak ke arah itu.

Nikos M.
sumber

Terima kasih! Sepertinya saya tidak sengaja bertanya pada diri sendiri pertanyaan yang sangat menarik!

user6818

@ user6818, terima kasih jawaban yang diperbarui dengan informasi lebih lanjut dan referensi lebih lanjut

Nikos M.

Saya berasumsi Anda sedang mempertimbangkan polinomial dengan koefisien integer .

Anda telah mengambil titik awal yang salah untuk investigasi Anda; tujuan Anda adalah menemukan perkiraan yang baik untuk akar yang sebenarnya. Mencari formula aljabar sehingga Anda bisa mengevaluasinya dengan cukup presisi adalah sesuatu yang bisa Anda lakukan, tetapi itu bukan hal yang benar untuk dilakukan di sini. (kecuali, tentu saja, " kakar nyata terbesar polinomial" adalah salah satu dari operasi aljabar Anda)

Titik awal yang jauh lebih baik adalah menggunakan teorema Sturm untuk mengisolasi akar polinomial. Anda kemudian dapat menghasilkan perkiraan yang lebih baik dengan pencarian biner, tetapi jika itu terlalu lambat, Anda dapat menggunakan metode Newton untuk dengan cepat menghasilkan perkiraan dengan presisi tinggi.

Tapi itu hanya tentang menemukan sertifikat. Masih ada pertanyaan tentang sertifikat apa yang bisa ada.

Pertama, saya akan tunjukkan bahwa Anda dapat secara langsung menghitung apakah dua akar sama persis dengan unit, misalnya dengan menghitung . Anda juga harus memutuskan apa yang ingin Anda lakukan tentang akar berulang dan berurusan dengan tepat. Saya menganggap Anda akan menangani kasus ini secara khusus. $k$ $\gcd(p(x), p(x-k))$

Jika kita mengetahui dua akar tidak persis unit terpisah, yang berarti bahwa Anda dapat menghasilkan perkiraan ketepatan yang cukup untuk membuktikan bahwa mereka baik besar atau kurang dari unit terpisah. misalnya ada dua jenis sertifikat: $k$ $k$

Jenis pertama (bukti negatif) adalah

bukan root dari $a$ $p$
tidak memiliki akar dalam $p$ $(a-k, a)$
memiliki tiga akar dalam $p$ $(a, \infty)$

Jenis kedua (bukti positif) adalah

bukan root dari $a$ $p$
memiliki setidaknya dua akar dalam $p$ $(a-k,a)$
memiliki dua akar dalam $p$ $(a, \infty)$

Sertifikat dapat diverifikasi dengan menggunakan teorema Sturm. Sekarang, pertanyaan Anda tentang ukuran sertifikat bermuara menemukan berapa banyak bit presisi yang Anda butuhkan untuk mewakili . $a$

Dengan kata lain, apa saja batasan pada nilai yang mungkin dari , di mana adalah akar dari ? $a-b-k$ $a,b$ $f$

Saya tidak yakin dengan pendekatan hebat, tetapi yang harus memberi Anda sesuatu adalah dengan mengamati bahwa semua nilai ini adalah akar dari polinomial:

g (x) = {Res}_{y} (f (y), f (x + y + k))

$g(x) = \mathop{\text{Res}_y}(f(y), f(x + y + k))$

Mengapa? Ingatlah bahwa hasil dari dua polinomial monik adalah produk dari semua perbedaan akarnya, jadi

g (x) = c^{d^{2}} \prod_{a, b} (b - (a - x - k)) = \prod_{a, b} (x - (a - b - k))

$g(x) = c^{d^2} \prod_{a,b}(b - (a - x - k)) = \prod_{a,b} (x - (a-b-k))$

di mana adalah koefisien terkemuka dan adalah derajat . (mungkin saya sudah menulis rumus untuk bukan ; Saya tidak pernah yakin pada tanda itu) $c$ $d$ $f$ $-g(x)$ $g(x)$

Jadi pertanyaannya adalah untuk menemukan perkiraan seberapa besar koefisien dapat, dan setelah Anda tahu itu, temukan perkiraan seberapa dekat akar dengan nol. $g$ $g$

(Atau, alternatifnya, temukan besaran terbesar yang dimiliki oleh akar polinomial terbalik ; akar polinomial terbalik adalah kebalikan dari akar-akar ) $g$ $g$

sumber

Apakah ada masalah tentang representasi data, di sini? NP pada dasarnya adalah tentang mesin Turing dan tidak segera jelas bagaimana hubungannya dengan bilangan real atau jumlah bit yang diperlukan untuk menuliskan rasional dengan presisi yang cukup. (Maaf tidak terlalu konstruktif: Saya tahu cukup untuk mengetahui ini mungkin masalah tetapi tidak cukup untuk mengetahui apakah itu benar-benar masalah atau, jika ya, bagaimana cara memperbaikinya.)

David Richerby

@DavidRicherby: Aku menduga input pada dasarnya hanya koefisien dari polinomial ditulis dalam biner, dan harapan saya adalah bahwa jumlah bit yang Anda butuhkan untuk mewakili

dalam biner akan dibatasi oleh fungsi polinomial dari jumlah bit memasukkan. Jika kita menggunakan dua parameter, jumlah bit input dan tingkat polinomial, maka saya hampir yakin bahwa jumlah bit yang Anda butuhkan untuk

akan polinomial dalam jumlah bit dari input, tapi aku kurang yakin persis bagaimana itu akan tergantung pada derajatnya.

a

$a$

a

$a$

Masukan sebagai daftar koefisien masuk akal. Tetapi asumsi Anda tentang ketelitian yang dibutuhkan untuk mewakili akar pasti perlu diperiksa. Misalnya, alasan bahwa masalah kesepuluh Hilbert (penyelesaian persamaan Diophantine) tidak dapat diputuskan pada dasarnya adalah bahwa Anda tidak dapat mengikat panjang solusi dalam hal panjang input. Itu tidak langsung berlaku di sini, karena kami hanya memiliki satu variabel dan kami tidak mencari solusi integer, tetapi ia mengajukan pertanyaan yang cukup besar tentang asumsi batasan.

David Richerby

@ David: Teori bidang tertutup nyata secara dramatis berbeda dari teori bilangan; intuisi tentang satu tidak benar-benar diterjemahkan dengan baik ke yang lain.

k + 2^{- 2^{2^{n}}}

$k+2^{-2^{2^n}}$

k - 2^{- 2^{2^{n}}}

$k-2^{-2^{2^n}}$

Saya akan menjawab pertanyaan Anda karena sebagian besar sudah berakhir. bukti galois sekarang dikenal sebagai Abel-Ruffini yang menunjukkan ketidakmungkinan solusi polinomial untuk quintic. (berbeda dengan misalnya persamaan kuadratik). jadi itu tidak benar-benar hasil pada kekerasan dari masalah itu sendiri tetapi lebih dari ketidakmungkinan . dalam pengertian ini lebih analog dengan misalnya bukti ketidaktentuan masalah penghentian. teori kompleksitas pada umumnya berkaitan dengan "biaya" solusi komputasi. itulah sudut pandang dua peneliti CS terkemuka di bagian pengantar dari makalah berikut ini ( Komputasi dan Kompleksitas / Kleinberg & Papadimitriou), bagian 1 Quest for the Quintic Formula:

Dilihat dari jarak yang aman dari beberapa abad, cerita ini jelas tentang kom- pasi, dan berisi banyak bahan utama yang muncul dalam upaya selanjutnya untuk memodelkan perhitungan: Kami mengambil proses komputasi yang kami pahami secara intuitif (menyelesaikan persamaan) , dalam kasus ini), merumuskan model yang tepat, dan dari model tersebut memperoleh beberapa konsekuensi yang sangat tidak terduga tentang kekuatan komputasi proses. Justru pendekatan ini yang ingin kami terapkan pada perhitungan secara umum.

$\neq$ $\neq$

ay
sumber

Saya tidak yakin bahwa masalah penghentian adalah analogi yang baik, karena ini lebih seperti "Anda tidak dapat menghitung jawabannya" daripada "tidak ada jawaban sama sekali".

Bukankah teorema Galois hasil ketidakmungkinan komputasi sama seperti masalah Hentikan?

user6818