Daftar nomor masalah teori atau aljabar di berbagai kelas kompleksitas

12

Saya mencari daftar tentang kompleksitas yang diketahui atau tidak diketahui dari berbagai masalah teori / aljabar. Sebagai contoh,

Adleman pernah menerbitkan daftar yang berfokus pada dan tetapi tampaknya sudah ketinggalan zaman. Mumford memiliki makalah tentang apa yang dapat dihitung dalam geometri aljabar tanpa memperhatikan kompleksitas.N PPNP

Adakah yang tahu daftar penemuan (utama) sejak daftar ini diterbitkan?

Apa beberapa masalah dari bilangan teoritik / aljabar rasa yang kelas kompleksitasnya mungkin sudah diketahui (karena daftar di atas diterbitkan), tidak diketahui tetapi dikira, atau tidak dikenal dan tidak dikira?

Beberapa jalan masalah dapat berupa masalah interpolasi (univariat atau multivariat, dalam berbagai bidang), teorema sisa Cina, kompleksitas penghitungan titik di atas kurva, dll.

T ....
sumber
Apakah Anda benar-benar hanya menginginkan masalah yang kompleksitasnya tidak hanya tidak diketahui, tetapi bahkan tidak berspekulasi untuk berada di suatu tempat? Itu tampaknya cukup membatasi, misalnya faktorisasi bilangan bulat tidak akan memuaskan pertanyaan itu karena berspekulasi berada di antara antara P dan ... Tapi saya pikir (dan harapan) maksud Anda pertanyaan yang sedikit lebih permisif. Akan menarik untuk melihat daftar seperti itu. UPcoUP
Joshua Grochow
@ JoshuaGrochow melebar.
T ....
Apakah GCD diketahui berada di logspace?
4
Tidak, ini merupakan masalah terbuka apakah ada di mana saja dalam hierarki NC.
Emil Jeřábek 3.0

Jawaban:

18

Geometri aljabar

  • Noether Normalisasi Lema (NNL) untuk varietas eksplisit saat ini hanya diketahui berada di (seperti NNL umum), tetapi menduga berada di (dan di dengan asumsi bahwa PIT dapat menjadi kotak hitam derandomized). Pembaruan 4/18/18: Baru-baru ini diperlihatkan bahwa untuk variasi ada di atas rasional ( Forbes & Shpilka) dan kemudian melalui bidang yang berubah-ubah ( Guo, Saxena, & Sinhababu ).P P ¯ V P P S P A C EEXPSPACEPPVP¯PSPACE

  • Pengujian apakah serangkaian polinomial tertentu memiliki ketergantungan aljabar. Masalah ini baru-baru ini ditunjukkan berada di oleh Guo, Saxena, & Sinhababu (meningkatkan batas atas sebelumnya dari karena untuk Mittmann, Saxena, & Scheblechner , juga di arXiv ).N P # PAMcoAMNP#P

  • Ada beberapa ( arXiv ) algoritma baru untuk menghitung invarian topologis dari varietas kompleks (dengan berbagai batasan seperti kelancaran, dll.). Saya percaya sebagian besar dari ini batas atas optimal masih terbuka

  • Hilull's Nullstellensatz (HN): diberi polinomial bilangan bulat, memutuskan apakah mereka memiliki solusi kompleks yang sama, ada di dengan asumsi GRH ( Koiran ). Tidak diketahui apakah itu dalam .N PAMNP

  • Algoritma untuk resolusi singularitas varietas aljabar dalam karakteristik nol. Batas waktu terbaik saat ini , karena Bierstone, Grigoriev, Milman, dan Włodarczyk adalah mana adalah dimensi variasi dan adalah Grzegorczyk hierarki fungsi rekursif primitif . Tidak ada batas yang lebih baik (ada?) Pada masalah ini, tetapi untuk masalah yang tampaknya lebih sederhana terkait batas bawah diketahui, yaitu: Ada cita-cita dalam variabel yang dihasilkan dalam derajat paling banyak yang memerlukan d E nn E n + 1Ed+3dEnnEn+1generator seperti itu. Jadi batas atas resolusi singularitas saat ini mungkin tidak jauh dari kebenaran, tetapi sedikit yang benar-benar diketahui.

Masalah isomorfisme

  • Banyak masalah pada kelompok permutasi - seperti persimpangan coset, isomorfisma kelompok permutasi, dll. - ada di , tetapi tidak diketahui apakah mereka berada di , dan diduga mereka tidak ada di . Grafik Isomorfisme mengurangi sebagian besar masalah tersebut, sehingga batas atas yang lebih baik menyiratkan batas atas yang lebih baik pada GI.N Pc o N P PNPcoAMNPcoNPP

  • Secara khusus, untuk isomorfisma kelompok permutasi, batas atas terbaik saat ini adalah, dan ini terbuka jika dapat dilakukan dalam waktu (hanya bergantung pada derajat grup permutasi dan bukan pada urutannya), apalagi waktu kuasi-poli seperti persimpangan GI dan coset .2 O ( n )2O(n)|G|2O(n)

  • Isomorfisme kelompok di mana kelompok diberikan oleh tabel perkalian diketahui berada di , tetapi diduga berada di . Diketahui berada di untuk beberapa kelas dari kelompok (update 4/18/18: dan beberapa ( arXiv ) lebih ( arXiv )), tetapi tidak pada umumnya.P PTIME(nO(logn))PP

Lain

  • Pembaruan 4/18/18: Peringkat tensor di bidang apa pun is -lengkap ( Schaefer & Stefankovic ). Apakah peringkat tensor lebih dari di ? Ia dikenal sebagai -hard ( Håstad ), dan di atas bidang yang terbatas ia berada di .F Q N P N P N PFFQNPNPNP

  • Secara umum, banyak masalah pada tensor lebih dari adalah -barang tetapi tidak diketahui berada di ( Hillar dan Lim , juga di arXiv ).N P N PQNPNP

Tampaknya (agak menyedihkan) bahwa survei Adleman-McCurley, meskipun berusia 21 tahun, cukup mutakhir dalam hal masalah teori angka, dengan pengecualian fakta bahwa kita sekarang tahu bahwa adalah di ...PPRIMESP

Joshua Grochow
sumber
Saya terkejut HN di NP tidak diketahui. Yang harus Anda lakukan adalah memeriksa solusi untuk setiap hak polinomial?
T ....
I Apa kesenjangan dalam resolusi singularitas?
T ....
4
@ Turbo: Untuk HN, polinomial adalah polinomial integer, tetapi solusinya diizinkan menjadi bilangan kompleks yang bahkan tidak perlu diungkapkan dengan jumlah bit terbatas, apalagi jumlah polinomial bit. Juga, untuk mendapatkan AM saya pikir Anda perlu GRH.
Joshua Grochow
2
(Pertama saya mengkonfirmasi bukti bahwa HN di AM bergantung pada GRH.) @ Turbo: Input adalah seperangkat polinomial integer, jadi didefinisikan dengan jumlah bit yang terbatas. Sertifikat yang jelas untuk HN akan menjadi solusi bagi sistem. Tetapi apa yang dikatakan Yosua adalah bahwa deskripsi dari solusi semacam itu tidak harus mewakili dengan jumlah bit yang terbatas. Jadi kita jauh dari memiliki sertifikat ukuran polinomial !
Bruno
3
@ Nikhil: karena PIT tidak memberikan batas atas pada NNL. Set memukul kotak hitam adalah apa yang memberi batas. Masalah dengan penghitungan semua set hitting yang mungkin untuk NNL (algoritma PSPACE untuk PIT) adalah bahwa untuk masing-masing, seseorang harus memverifikasi properti tertentu, dan verifikasi hanya diketahui dalam EXPSPACE. Jika OTOH Anda dapat langsung membuat set pukulan yang dijamin, pada dasarnya Anda tidak perlu memverifikasi. Anda akan melihat ketika Anda membaca koran.
Joshua Grochow
4

Menambahkan beberapa lagi dengan penekanan pada teori Galois dan teori Galois komputasi (lihat pertanyaan terkait pada cs.SE ):

Kompleksitas komputasi untuk menentukan apakah suatu polinomial tak tereducikan yang diberikan atas bilangan bulat , dapat larut oleh radikal dalam Ref "Solvabilitas oleh Radikal Berada dalam Waktu Polinomial", S. Landau GL Miller 1984PZP

Menurut sebuah makalah Batas atas kompleksitas beberapa masalah Teori Galois oleh Arvind dan Kurur di sini , teorema Landau memberikan batas atas eksponensial dalam ukuran polinomial di bawah definisi ukuran tertentu. Lebih tepatnya, teorema nya memberikan ikatan polinomial dalam hal ukuran kelompok Galois dan ukuran polinomial. Tetapi ukuran grup dapat eksponensial dalam ukuran polinomial. Mereka menunjukkan jika kelompok Galois dapat dipecahkan, maka urutannya dapat dihitung dengan algoritma waktu polinomial acak dengan oracle .NP

direproduksi dari pertanyaan terkait di MO

Nikos M.
sumber