Masalah besar yang belum terpecahkan dalam ilmu komputer teoretis?

218

Wikipedia hanya mencantumkan dua masalah di bawah "masalah yang tidak terpecahkan dalam ilmu komputer" :

Apa masalah besar lainnya yang harus ditambahkan ke daftar ini?

Aturan:

  1. Hanya satu masalah per jawaban
  2. Berikan deskripsi singkat dan tautan apa pun yang relevan
Shane
sumber
1
Karena Anda meminta daftar dan tidak ada jawaban tunggal, ini mungkin lebih baik ditandai sebagai wiki komunitas.
Daniel Apon
2
Satu masalah yang belum terselesaikan per jawaban, tolong; maka kita dapat dengan mudah memberi peringkat jawaban dengan memilih naik / turun!
Jukka Suomela
15
Mengapa hanya kompleksitas yang dihasilkan? Ada lebih banyak TCS daripada kompleksitas! Tidak ada masalah terbuka dalam teori tipe? bahasa pemrograman?
Jacques Carette
3
tambahkan mereka, Jacques :).
Suresh Venkat
8
Saya pikir kita harus membedakan antara masalah terbuka utama yang dipandang sebagai masalah mendasar , seperti , dan masalah terbuka utama yang akan menjadi terobosan teknis, jika dipecahkan, tetapi tidak harus sebagai hal mendasar, misalnya, batas bawah eksponensial pada A Sirkuit C 0 ( 6 ) (yaitu, gerbang ). Jadi kita mungkin harus membuka wiki komunitas baru yang berjudul "masalah terbuka di perbatasan TCS", atau sejenisnya. PNPAC0(6)AC0+mod6
Iddo Tzameret

Jawaban:

137

Dapat perkalian dari oleh matriks dilakukan di operasi?nnO(n2)

Eksponen dari batas atas yang paling dikenal bahkan memiliki simbol khusus, . Saat ini kira-kira 2.376, oleh algoritma Coppersmith-Winograd . Tinjauan bagus tentang keadaan seni adalah Sara Robinson, Menuju Algoritma Optimal untuk Penggandaan Matriks , SIAM News, 38 (9), 2005.ωω

Pembaruan: Andrew Stothers (dalam tesis 2010- nya ) menunjukkan bahwa , yang ditingkatkan oleh Virginia Vassilevska Williams (dalam cetakan Juli 2014 ) ke . Batas-batas ini diperoleh dengan analisis yang cermat terhadap teknik dasar Coppersmith-Winograd.ω<2.3737ω<2.372873

Pembaruan Lebih Lanjut (30 Jan 2014): François Le Gall telah membuktikan bahwa dalam makalah yang diterbitkan dalam ISSAC 2014 ( arXiv preprint ).ω<2.3728639

András Salamon
sumber
Bagaimana dengan tujuan sederhana dan realistis dari atau fungsi lain antara dan ? Setelah semua itu diharapkan bahwa perkalian integer memiliki batas bawah . O(n2logn)n2+ϵn2O(nlogn)
Mitch
Saya tidak yakin pergi dari bahkan ke dianggap sebagai "tujuan sederhana dan realistis", apalagi kemudian di bawah . Tapi akan bagus untuk melihat beberapa kemajuan, jadi cobalah! 2+0.3762+ϵ2+ϵ
András Salamon
13
Eksponen perkalian matriks didefinisikan sebagai bilangan real terkecil sehingga operasi aritmatika cukup untuk semua . Mungkin faktor seperti harus diharapkan. O ( n ω + ϵ ) ϵ > 0 log nωO(nω+ϵ)ϵ>0logn
Zeyu
2
Hanya menambahkan demi kelengkapan wrt pengetahuan saat ini bahwa ikatan CW lebih baik beberapa hari yang lalu oleh Virginia Williams. Dan seperti yang dicatat oleh banyak orang lain di komunitas, Andrew Stothers telah mendapatkan ikatan mengalahkan CW sekitar satu tahun sebelum Virginia. Rekor saat ini adalah O(n2.373)
Akash Kumar
Saya hanya akan membiarkan ini di sini research.microsoft.com/en-us/um/people/kannan/papers/…
raven
123

Apakah Grafik Isomorfisme dalam P?

Kompleksitas Graph Isomorphism (GI) telah menjadi pertanyaan terbuka selama beberapa dekade. Stephen Cook menyebutkannya dalam makalahnya tahun 1971 tentang NP-kelengkapan SAT .

Menentukan apakah dua grafik isomorfik biasanya dapat dilakukan dengan cepat, misalnya dengan perangkat lunak seperti nautydan saucy. Di sisi lain, Miyazaki membangun kelas instance yang nautyterbukti membutuhkan waktu eksponensial.

Read dan Corneil mengulas banyak upaya untuk mengatasi kompleksitas GI hingga saat itu: The Graph Isomorphism Disease , Journal of Graph Theory 1 , 339-363, 1977.

GI tidak diketahui berada dalam co-NP, tetapi ada protokol acak sederhana untuk Graph Non-Isomorphism (GNI). Jadi GI (= co-GNI) karena itu diyakini "dekat dengan" NP NP bersama.

Di sisi lain, jika GI adalah NP-lengkap, maka Hirarki Polinomial runtuh. Jadi GI tidak mungkin lengkap NP. (Boppana, Håstad, Zachos, Apakah co-NP Memiliki Bukti Interaktif Singkat?, IPL 25 , 127–132, 1987)

Shiva Kintali memiliki diskusi yang bagus tentang kompleksitas GI di blog-nya.

Laszlo Babai membuktikan bahwa Graph Isomorphism berada dalam waktu sub-responsif .

András Salamon
sumber
Silakan lihat entri ini juga.
MS Dousti
Saya memutar batas bawah yang tepat untuk deteksi automorfisme brute force generik. oeis.org/A186202 Jauh lebih sedikit daripada tapi masih eksponensial. Berharap McKay akan memasangkannya ke Schrier-Sims untuk inkarnasi NAUTY terbarunya untuk membuatnya berjalan pada perangkat keras paralel. n!
Chad Brewbaker
1
Babai mencabut klaim runtime quasipolynomial . Ternyata ada kesalahan dalam analisis.
Raphael
4
Klaim dikembalikan: people.cs.uchicago.edu/~laci/update.html
niting
91

Kompleksitas anjak piutang

Apakah Anjak di ?P

Kaveh
sumber
Adakah publikasi bagus yang Anda ketahui yang menggambarkan anjak atau kompleksitas pengujian purba dalam hal struktur semigroup penambahan dan multiplikasi transformasi pada Z_n? Misalnya pada [0,1,2] adalah transformasi +0 | x1, [1,2,0] adalah transformasi +1 ...Z3
Chad Brewbaker
72

P = BPP?

Diego de Estrada
sumber
2
Jawaban ini harus dibuat CW sekarang juga ...
Shane
2
dan pertanyaan terkait seperti apakah NP = MA = AM?
Robin Kothari
1
Lihat pertanyaan terkait erat cstheory.stackexchange.com/questions/64/…
András Salamon
66

Apakah ada aturan berputar untuk algoritma simpleks yang menghasilkan waktu berjalan polinomial kasus terburuk? Lebih umum, apakah ada algoritma polinomial yang kuat untuk pemrograman linier?

Jɛ ff E
sumber
11
Saya akan menambahkan ke pertanyaan ini: apakah akan menunjukkan tidak adanya LP yang sangat polinomial menyiratkan hasil pemisahan kelas?
Anand Kulkarni
,,, dan dugaan Hirsch ...
Sariel Har-Peled
7
Pada tahun 2011, Oliver Friedmann menunjukkan batas bawah eksponensial untuk banyak aturan berputar (dia benar-benar mengklaim aturan berputar "dasarnya semua alami", termasuk Random Facet dan Random Edge). Batas ini berlaku saat menyelesaikan program linier yang berasal dari game paritas 2-pemain. Tesis Friedmann, edoc.ub.uni-muenchen.de/13294 mensurvei sejarah secara mendalam (termasuk berbagai bentuk Hirsch Conjecture, dan tahun 2010 berlawanan dengan contoh kuat oleh Francisco Santos).
András Salamon
63

The eksponensial-waktu hipotesis (ETH) menegaskan bahwa pemecahan SAT membutuhkan eksponensial, 2 Ω (n) waktu. ETH menyiratkan banyak hal, misalnya SAT tidak dalam P, jadi ETH menyiratkan P ≠ NP. Lihat Impagliazzo, Paturi, Zane, Masalah Mana Yang Memiliki Kompleksitas Eksponensial Sangat? , JCSS 63, 512-530, 2001.

ETH diyakini secara luas, tetapi kemungkinan sulit untuk dibuktikan, karena menyiratkan banyak pemisahan kelas kompleksitas lainnya.

András Salamon
sumber
4
Serius, saya tidak akan menyebut ETH masalah terbuka utama pada saat ini tepat karena itu menyiratkan P ≠ NP dan dengan demikian setidaknya sama sulitnya untuk dibuktikan.
Holger
17
Tidak? IMHO, argumen Anda menyiratkan bahwa ETH bahkan lebih merupakan masalah terbuka utama daripada PvsNP.
Jeffε
Bisakah Anda menjelaskan mengapa tidak menyiratkan ETH? PNP
Emil
13
Jika , maka P N P , tetapi ETH salah. NP=PTsayaM.E(ncatatann)PNP
Jeffε
3
Ah baiklah. Tapi maksud Anda DTIME ( )? ncatatann
Emil
59

Immerman dan Vardi menunjukkan bahwa logika titik tetap menangkap PTIME di kelas struktur yang dipesan . Salah satu masalah terbuka terbesar dalam teori kompleksitas deskriptif adalah apakah ketergantungan pada pesanan dapat dihilangkan:

Apakah ada logika yang menangkap PTIME?

Sederhananya, logika menangkap PTIME adalah bahasa pemrograman untuk masalah grafik yang bekerja langsung pada struktur grafik dan tidak memiliki akses ke pengkodean simpul dan tepi, sehingga penahanan berikut:

  1. setiap program yang secara sintaksis memodelkan masalah grafik yang dapat dihitung polinomial-waktu dan
  2. masalah grafik komputasi polinomial waktu dapat dimodelkan dengan program yang benar secara sintaksis.

Jika tidak ada logika yang menangkap PTIME, maka sejak NP ditangkap oleh logika orde kedua. Logika yang menangkap PTIME akan memberikan kemungkinan serangan ke P vs NP.PNP

Lihat blog Lipton untuk diskusi informal dan M. Grohe: The Quest for a Logic Capturing PTIME (LICS 2008) untuk survei yang lebih teknis.

Holger
sumber
3
Immerman-Vardi menunjukkan FO (LFP) menangkap logika pada <i> memerintahkan </i> struktur, jadi ini adalah pertanyaan tentang menangkap PTIME pada model terbatas sewenang-wenang, saya ambil. Jika saya memahami Anda dengan benar, bukankah pertanyaan ini merupakan terjemahan untuk menanyakan apakah P! = NP? Mungkin lebih diarahkan untuk menanyakan satu atau lebih masalah terbuka dalam survei yang Anda tautkan. Maaf jika saya tidak tahu apa-apa di sini.
Aaron Sterling
5
Terima kasih, saya mengedit jawaban untuk menyebutkan Immerman-Vardi untuk klarifikasi. Tidak, masalah terbuka ini tidak diketahui setara dengan P vs NP. Masalah terbuka dalam survei adalah kasus khusus dari masalah besar terbuka dan tidak sesuai di utas ini. Mungkin referensi ini juga membantu: rjlipton.wordpress.com/2010/04/05/...
Holger
55

Apakah dugaan game unik itu benar?
Dan: Mengingat bahwa ada algoritma perkiraan waktu sub-eksponensial untuk Game Unik , di mana masalahnya pada akhirnya terletak pada lanskap kompleksitas?

Anand Kulkarni
sumber
Tidakkah akan lebih tepat untuk mengatakan bahwa jika UGC tidak benar (yaitu game unik tidak NP-keras, hanya lebih keras dari P), di mana UGC akan masuk ke dalam lanskap?
András Salamon
Ups. Ya, saya harus menulis ulang ini. Tujuan saya adalah untuk menyoroti perbedaan yang tampak yang dihasilkan dari permainan unik yang memiliki algoritma pendekatan non-trivial dalam waktu sub-eksponensial (tapi tidak terlalu polinomial). Lebih lanjut dari: Apa isinya, jika run time sub-eksponensial optimal untuk game unik?
Daniel Apon
2
Dalam retrospeksi, saya pikir saya harus memasukkan pointer ke pra-cetak ini . Menurut pendapat saya, ini sama besar dengan perkembangan seperti makalah yang saya tautkan dalam jawabannya.
Daniel Apon
1
Perlu dicatat bahwa tidak ada contoh keras dari UCG yang diketahui. Pendekatan terbaik saat ini bekerja secara efisien dalam setiap kasus yang diuji. Kami tidak dapat membuktikan bahwa kami telah menemukan contoh paling patologis.
Stella Biderman
55

Permanen versus Penentu

Pertanyaan permanen versus determinan menarik karena dua fakta. Pertama, permanen dari matriks menghitung jumlah pencocokan sempurna dalam grafik bipartit. Oleh karena itu, permanen dari matriks tersebut adalah # P-Complete. Pada saat yang sama, definisi permanen sangat dekat dengan determinan, akhirnya berbeda hanya karena perubahan tanda yang sederhana. Perhitungan determinan diketahui berada di P. Mempelajari perbedaan antara permanen dan determinan, dan berapa banyak perhitungan determinan diperlukan untuk menghitung pembicaraan permanen tentang P versus # P.

Kaveh
sumber
5
Bagi saya ini tidak memenuhi syarat sebagai "masalah terbuka utama", karena pertanyaan teoritis kompleksitas aktual (apakah mereka memiliki kompleksitas yang berbeda) digolongkan oleh P = NP (karena #P adalah superset dari NP) dan dengan pertanyaan itu dikesampingkan. tidak ada masalah konkret yang ditimbulkan di sini.
David Eppstein
Saya sebenarnya setuju dengan ini.
Ross Snider
10
@ DavidVppstein: Per v. Det lebih dekat dengan GapP v GapL, analog penghitungan NP v NL. Ada kemungkinan bahwa dan karenanya G a p P G a p L . Juga, per v det jauh lebih tua dari Pv NP, pada dasarnya akan kembali ke [Polya 1913], di mana ia menunjukkan bahwa seseorang tidak dapat membubuhkan tanda-tanda ke matriks untuk mengubah permanen ke determinannya (kecuali 2x2). Valiant memperkenalkan varian pada pertanyaan-pertanyaan tersebut (memungkinkan ukuran det menjadi lebih besar dari n) karena signifikansinya dalam kompleksitas, tetapi bahkan karya-karya pra-Valiant memberikan motivasi "karena permanen begitu sulit untuk dihitung ..." (mis. Gibson 1971)NL.P=NPGSebuahhalPGSebuahhalL.
Joshua Grochow
Bagaimana keadaan algoritma sekarang untuk menghitung permanen dari matriks 0-1? yaitu jumlah matriks permutasi hukum yang dapat Anda hasilkan dari himpunan bagian 1's.
Chad Brewbaker
@ChadBrewbaker: lihat Mark Jerrum, Alistair Sinclair, Eric Vigoda, "Algoritma Perkiraan Waktu Polinomial untuk Permanen Matriks dengan Entri Non-Negatif", Jurnal ACM 51/4 (2004), 671, citeseerx.ist. psu.edu/viewdoc/summary?doi=10.1.1.141.116
Zsbán Ambrus
47

Bisakah kita menghitung FFT dalam waktu kurang dari ?HAI(ncatatann)

Dalam nada umum yang sama (sangat), ada banyak pertanyaan untuk meningkatkan run-time dari banyak masalah atau algoritma klasik: misalnya, dapatkah semua jalur berpasangan-terpendek (APSP) diselesaikan dalam waktu waktu ?HAI(n3-ϵ)

Sunting: APSP berjalan dalam waktu "di mana penambahan dan perbandingan real adalah biaya unit (tapi semua operasi lain memiliki biaya logaritmik khas)":http://arxiv.org/pdf/1312.6680v2.pdf(n32Ω(lHaign)1/2)

Alex Andoni
sumber
3
Perkembangan yang menarik pada FFT: "* Algoritma O (k log n) -waktu untuk kasus di mana sinyal input paling banyak memiliki koefisien Fourier non-nol k, dan * O (k log n log (n / k)) Algoritma-waktu untuk sinyal input umum. " sumber: arxiv.org/abs/1201.2501v1
Shadok
45

Algoritma deterministik waktu linier untuk masalah spanning tree minimum .

Suresh Venkat
sumber
44

NP versus ko-NP

Pertanyaan NP versus ko-NP menarik karena NP ≠ co-NP menyiratkan P ≠ NP (karena P ditutup di bawah komplemen). Ini juga berhubungan dengan "dualitas": pemisahan antara menemukan / memverifikasi contoh dan menemukan / memverifikasi contoh tandingan. Faktanya, membuktikan bahwa sebuah pertanyaan ada dalam NP dan co-NP adalah bukti baik pertama kami bahwa masalah yang tampaknya berada di luar P juga kemungkinan tidak NP-Lengkap.

Ross Snider
sumber
7
Ini juga terkait dengan kompleksitas bukti proposisional. Ada polinomial proposisional sistem bukti IFF sama dengan c o N P . NPcoNP
Kaveh
41

Apakah ada masalah yang tidak dapat diselesaikan secara efisien oleh komputer paralel?

Masalah yang P-lengkap tidak diketahui bisa diparalelkan. Masalah P-complete termasuk Horn-SAT dan Linear Programming. Tetapi membuktikan bahwa ini adalah kasus akan memerlukan memisahkan beberapa gagasan masalah yang dapat diparalelkan (seperti NC atau LOGCFL) dari P.

Desain prosesor komputer meningkatkan jumlah unit pemrosesan, dengan harapan bahwa ini akan menghasilkan peningkatan kinerja. Jika algoritma mendasar seperti Linear Programming secara inheren tidak dapat diparalelkan, maka ada konsekuensi yang signifikan.

András Salamon
sumber
16
Saya cukup yakin bahwa algoritma LP, seperti yang ada saat ini, tidak dapat diparalelkan. Saya percaya mereka cocok dengan model RAM-tanpa-bit-operasi Mulmuley. Dalam dx.doi.org/10.1137/S0097539794282930 K. Mulmuley. Batas Bawah dalam Model Paralel tanpa Operasi Bit. SIAM J. Comput. 28 (4), 1460-1509 (1999) ia menunjukkan bahwa dalam model itu, menunjukkan bahwa banyak algoritma alami (biasanya numerik) untuk masalah P -complete tidak dapat diparalelkan. Ini tidak menjawab pertanyaan dalam kasus boolean, tetapi ia menjawabnya untuk kelas besar algoritma alami. PNCP
Joshua Grochow
41

Apakah semua tautologi proposisional memiliki bukti Frege ukuran polinomial?

Bisa dibilang masalah terbuka utama kompleksitas bukti : menunjukkan ukuran super-polinomial batas bawah pada bukti proposisional (disebut juga bukti Frege).

Secara informal, sistem bukti Frege hanyalah sistem bukti proposisional standar untuk membuktikan tautologi proposisional (seseorang belajar dalam kursus logika dasar), memiliki aksioma dan aturan deduksi, di mana garis bukti ditulis sebagai rumus. The ukuran dari bukti Frege adalah jumlah simbol yang diperlukan untuk menuliskan bukti.

Masalahnya kemudian bertanya apakah ada keluarga (Fn)n=1 formula tautologis proposisional yang tidak ada polinomial p sehingga ukuran bukti Frege minimal Fn paling banyak p(|Fn|) , untuk all n=1,2, (di mana |Fn| menunjukkan ukuran rumus Fn ).


Definisi formal dari sistem bukti Frege

Definisi (Aturan Frege) Aturan Frege adalah urutan formula proposisional A0(x¯),...,SEBUAHk(x¯) , untuk k0 , ditulis sebagai SEBUAH1(x¯),...,SEBUAHk(x¯)SEBUAH0(x¯) . Dalam kasusk=0, aturan Frege disebutskema aksioma. Sebuah formulaF0dikatakanditurunkan dengan aturandariF1,...,FkjikaF0,...,Fkadalah semua contoh substitusi dariSEBUAH1,...,SEBUAHk, untuk beberapa tugas kepadax¯variabel ( yaitu, ada rumus B1,...,Bn sedemikian rupa sehinggaFi=Ai(B1/x1,,Bn/xn), untuk semuai=0,,k . Aturan Frege dikatakanbaikjika setiap kali sebuah tugas memenuhi rumus di sisi atas A1,,Ak , maka itu juga memenuhi rumus di sisi bawahA0 .

Definisi (bukti Frege) Diberikan seperangkat aturan Frege, bukti Frege adalah urutan formula sedemikian rupa sehingga setiap baris bukti merupakan aksioma atau diturunkan oleh salah satu aturan Frege yang diberikan dari jalur bukti sebelumnya. Jika urutan berakhir dengan rumus SEBUAH , maka bukti dikatakan bukti SEBUAH . The ukuran dari bukti Frege adalah total ukuran semua rumus dalam bukti.

Sebuah sistem bukti dikatakan implicationally lengkap jika untuk semua himpunan formula T , jika T semantik menyiratkan F , maka ada bukti F menggunakan (mungkin) aksioma dari T . Suatu sistem bukti dikatakan baik jika ia mengakui bukti hanya tautologi (ketika tidak menggunakan aksioma bantu, seperti dalam T atas).

Definisi (sistem bukti Frege) Diberi bahasa proposisional dan seperangkat P aturan Frege yang baik, kami mengatakan bahwa P adalah sistem bukti Frege jika P secara implisit selesai.

Perhatikan bahwa bukti Frege selalu baik karena aturan Frege dianggap baik. Kita tidak perlu bekerja dengan sistem bukti Frege tertentu, karena hasil dasar dalam kompleksitas bukti menyatakan bahwa setiap dua sistem bukti Frege, bahkan lebih dari bahasa yang berbeda, setara secara polinomi [Reckhow, tesis PhD, University of Toronto, 1976].


Menetapkan batas bawah pada bukti Frege dapat dilihat sebagai langkah untuk membuktikan NPcoNP , karena jika ini benar maka tidak ada sistem bukti proposisional (termasuk Frege) yang dapat memiliki bukti ukuran polinom untuk semua tautologi.

Iddo Tzameret
sumber
38

Bisakah kita menghitung jarak edit antara dua string panjang dalam waktu sub-kuadrat, yaitu, dalam waktu O ( n 2 - ϵ ) untuk beberapa ϵ > 0 ?nHAI(n2-ϵ)ϵ>0

Piotr
sumber
8
Apakah Anda punya referensi untuk itu? Saya benar-benar berpikir bahwa proposisi ini keliru sepele meskipun saya tidak bisa memikirkan bukti dari atas kepala saya. (Meskipun saya sadar bahwa runtime dapat dibuat tergantung pada jumlah kesalahan.)
Konrad Rudolph
5
Pembaruan (STOC 2015): Backurs dan Indyk memberikan bukti bahwa waktu yang lebih baik daripada kuadratik tidak dimungkinkan. Lihat rjlipton.wordpress.com/2015/06/01/puzzling-evidence .
Neal Young
38

Apakah ada algoritma waktu subquadratic (artinya untuk beberapa konstanta δ > 0 ) untuk Masalah 3SUM-hard ?O(n2δ)δ>0

Pada tahun 2014, Gronlund dan Pettie dijelaskan algoritma deterministik untuk 3SUM sendiri yang berjalan dalam waktu . Meskipun ini adalah hasil utama, peningkatan lebih dari O ( n 2 ) hanya (sub) logaritmik. Selain itu, tidak ada algoritma subquadratic serupa yang diketahui untuk sebagian besar masalah 3SUM-keras lainnya.O(n2/(logn/loglogn)2/3)O(n2)

Aryabhata
sumber
9
Pertanyaan bagus. Namun, keberadaan algoritma sub-kuadratik untuk masalah 3SUM sangat terbuka bahkan untuk algoritma acak . Tentu saja, algoritma deterministik akan lebih baik lagi ..
Piotr
3
Dalam kasus kuantum, dikenal pencocokan n log (n) batas bawah dan atas untuk 3SUM: Andrej Dubrovsky, Oksana Scegulnaja-Dubrovska Peningkatan Batas Bawah Kuantum untuk Masalah 3-Sum. Prosiding Baltik DB&IS 2004, vol. 2, Riga, Latvia, hal.40-45.
Martin Schwarz
1
Saya mendapat kesan bahwa kita tidak memiliki batas bawah n ^ 2 untuk masalah apa pun di NP.
Sariel Har-Peled
1
Saya memiliki kesan berbeda bahwa jika Anda terbatas pada masalah keputusan (tidak ada argumen keluaran), maka tidak ada yang diketahui. Tetapi Anda harus benar-benar bertanya kepada orang yang rumit.
Sariel Har-Peled
3
Makalah arXiv baru-baru ini mengklaim telah menyelesaikan dugaan ini dengan memberikan algoritma sub-kuadrat untuk 3-SUM.
Mangara
35

BQP = P?

Juga: NP yang terkandung dalam BQP?

Saya tahu ini melanggar aturan dengan memiliki dua pertanyaan dalam jawabannya, tetapi ketika diambil dengan pertanyaan P vs NP, mereka tidak harus pertanyaan independen.

Joe Fitzsimons
sumber
33
  1. Dugaan Isomorfisme. (Apakah semua masalah NP-menyelesaikan masalah "sama"?)
  2. Bisakah kriptografi didasarkan pada masalah NP-complete?

  3. dan, sedikit lebih jauh dari arus utama:

  4. Berapa ukuran NP dalam EXP?

(Secara informal, jika Anda memiliki semua masalah dalam EXP di atas meja, dan Anda mengambilnya secara seragam secara acak, berapakah probabilitas bahwa masalah yang Anda pilih juga dalam NP? Pertanyaan ini telah diformalkan dengan gagasan tentang ukuran terbatas sumber daya Diketahui bahwa P memiliki ukuran nol dalam EXP, yaitu, masalah yang Anda ambil dari tabel hampir pasti tidak dalam P.)

Aaron Sterling
sumber
Apakah ini sama dengan p-ukuran di Kebun Binatang Kompleksitas? Ke mana saya akan pergi untuk membaca lebih lanjut tentang itu?
András Salamon
2
P-ukuran adalah salah satu contoh ukuran yang dibatasi sumber daya: lebih umum, Anda dapat membayangkan mesin yang mencoba memprediksi urutan, dan sumber daya komputasi yang tersedia untuk melakukannya adalah apa yang menyediakan sumber daya-terikat pada ukuran. Saya menggunakan p-ukuran dalam penjelasan informal saya tentang EXP di atas meja. Untuk bacaan lebih lanjut, saya merekomendasikan versi jurnal dari survei berikut oleh Lutz (CZ mengutip versi konferensi survei ini). cs.iastate.edu/~lutz/=PAPERS/qset.ps (dalam postscript, saya harap tidak apa-apa)
Aaron Sterling
Terima kasih. Ini adalah PDF dari makalah itu untuk mereka yang tidak bisa membaca PS: archives.cs.iastate.edu/documents/disk0/00/00/01/28/00000128-01/…
András Salamon
2
Ya untuk pertanyaan pertama Anda. P memiliki ukuran 0 dalam EXP, jadi jika NP tidak, Anda mendapatkan P! = NP segera. Untuk pertanyaan kedua, saya sarankan Anda membaca paragraf terakhir dari halaman 28 dalam survei yang dikaitkan dengan saya dan Andras. (Tidak cukup ruang dalam komentar untuk menempelkannya di sini, maaf.) Pada dasarnya, jika NP memiliki ukuran nol, ada algoritma yang layak yang bisa menebak keanggotaan dalam masalah NP-hard "tidak masuk akal" dengan baik. Jadi nampaknya NP tidak mengukur nol dalam EXP.
Aaron Sterling
1
@ Art: Anda bisa mulai di sini: blog.computationalcomplexity.org/2003/03/…
Aaron Sterling
29

Berapakah perkiraan Metric TSP ? Algoritma Christofides ' dari tahun 1975 adalah algoritma estimasi polinomial-waktu (3/2). Apakah NP-sulit dilakukan lebih baik?

  • Perkiraan Metric TSP ke dalam faktor yang lebih kecil dari 220/219 adalah NP-hard (Papadimitriou dan Vempala, 2006 [PS] ). Setahu saya ini adalah batas bawah yang paling dikenal.

  • Ada beberapa bukti yang menunjukkan bahwa batas sebenarnya mungkin 4/3 (Carr dan Vempala, 2004 [Versi gratis] [Versi bagus] ).

  • 13/9

James King
sumber
1
Metrik TSP baru-baru ini dilakukan oleh 3/2 - e di mana e konstan (dekat 0,002)
Saeed
1
beberapa diskusi tentang metrik TSP pada surat Godel yang hilang
Artem Kaznatcheev
2
@ Saeed, maksud Anda algoritma hanya untuk kasus khusus Metric TSP: untuk Graphic TSP? Kemudian ditingkatkan menjadi 13/9 oleh Mucha. Tampaknya 3/2 adalah batas atas yang paling dikenal untuk Metric TSP.
Alex Golovnev
@AlexGolovnev, Hai Alex, Ya, tapi komentar saya sebelum makalah baru datang;) (Saya melihat kertas Oveis Gharan pada waktu itu).
Saeed
28

Berikan fungsi eksplisit dengan kompleksitas rangkaian eksponensial.

Shannon membuktikan pada tahun 1949 bahwa jika Anda memilih fungsi Boolean secara acak, ia memiliki kompleksitas rangkaian eksponensial dengan probabilitas hampir satu.

f:{0,1}n{0,1}5no(n)

Kaveh
sumber
11
Cara menyatakan masalah ini selalu mengganggu saya, karena Anda harus berhati-hati tentang apa yang Anda maksud dengan "eksplisit". Sangat mudah untuk menuliskan deskripsi fungsi yang memiliki kompleksitas rangkaian eksponensial. Jika "eksplisit" berarti "dapat dihitung dalam waktu eksponensial atau kurang", maka saya setuju, ini adalah masalah terbuka utama.
Ryan Williams
1
Ryan, kamu benar. Ini adalah poin yang sangat penting. Juga mudah untuk menuliskan deskripsi fungsi yang tidak dapat dihitung. Dalam makalah yang saya kutip, batas bawah terbukti untuk fungsi yang konstruktif dalam waktu polinomial deterministik.
Marc
Apakah ada eksposisi yang bagus tentang karya Shannon?
T ....
3
Argumen ini dirinci dalam catatan kuliah berikut: math.tau.ac.il/ ~ zwick
Marc
Ini adalah masalah yang luar biasa dan membawa kembali kenangan indah saat ditugaskan sebagai hasil Shanon tahun kedua saya di universitas.
Stella Biderman
27

ϵ1/ϵ1/ϵ

arnab
sumber
27

Pisahkan NEXP dari BPP. Orang-orang cenderung percaya BPP = P, tetapi tidak ada yang dapat memisahkan NEXP dari BPP.

Bin Fu
sumber
26

Saya tahu OP hanya meminta satu masalah per posting, tetapi konferensi RTA (Teknik Menulis Ulang dan Aplikasi mereka) 1 dan TLCA (Kalkulator Lambda Diketik dan Aplikasi mereka) keduanya mempertahankan daftar masalah terbuka di bidangnya 2 . Daftar-daftar ini cukup berguna, karena mereka juga memasukkan petunjuk ke pekerjaan sebelumnya yang dilakukan pada upaya untuk memecahkan masalah ini.

Dominic Mulligan
sumber
1
Tidak masalah. Adakah yang tahu daftar serupa lainnya dari konferensi lain? Mereka cukup menarik untuk dibaca.
Dominic Mulligan
26

Derandomisasi masalah Pengujian Identitas Polinomial

PP

Masalah ini dapat diselesaikan dalam waktu polinomial acak tetapi tidak diketahui dapat dipecahkan dalam waktu polinomial deterministik.

τPττ(P)P1PZ[x]z(P)

cPZ[x]z(P)(1+τ(P))c

Bruno
sumber
25

Ada banyak masalah terbuka di kalkulus lambda (diketik dan tidak diketik). Lihat daftar masalah terbuka TLCA untuk detailnya; ada juga versi PDF yang bagus tanpa bingkai.

Saya sangat suka masalah # 5:

Fω

Jacques Carette
sumber
3
Terima kasih kepada Dominic Mulligan karena mengarahkan saya ke daftar masalah khusus ini.
Jacques Carette
25

Apakah masalah logaritma diskrit di P?

Gqg,hGgGnNgn=hq

gabg,gagbg,ga,gb,hGgab=h

Jelas DLP sulit jika CDH sulit, dan CDH sulit jika DDH sulit, tetapi tidak ada pengurangan yang diketahui, kecuali untuk beberapa kelompok. Asumsi bahwa DDH sulit adalah kunci untuk keamanan beberapa cryptosystems, seperti ElGamal dan Cramer-Shoup .

Felipe Lacerda
sumber
3
Yah, kita tahu DLP terkandung dalam BQP.
Joe Fitzsimons
G=Fpn×
24

Permainan paritas adalah permainan grafik dua pemain dengan durasi tak terbatas, yang masalah keputusan kodenya adalah dalam NP dan co-NP, dan yang memiliki masalah pencarian alami di PPAD dan PLS.

http://en.wikipedia.org/wiki/Parity_game

Bisakah game paritas diselesaikan dalam waktu polinomial?

(Lebih umum, pertanyaan terbuka utama lama dalam pemrograman matematika adalah apakah P-matrix Linear Complementarity Problem dapat diselesaikan dalam waktu polinomial?)

Rahul Savani
sumber
23

Area dengan kompleksitas parameterisasi memiliki beban masalah terbuka sendiri.

Pertimbangkan masalah keputusan

  • (G,k)kG
  • (F,k)kF ?
  • (G,k)kG
  • dll ...

f(k)ncfcknHAI(k)

Kerangka kerja ini memodelkan kasus-kasus di mana kita mencari struktur kombinatorial kecil dan kita dapat menjalankan waktu berjalan eksponensial sehubungan dengan ukuran solusi / saksi .

Masalah dengan algoritma seperti itu (misalnya penutup vertex) disebut Fixed Parameter Tractable (FPT).

Kompleksitas yang diparameterisasi adalah teori yang matang dan memiliki landasan teori dan daya tarik yang kuat untuk aplikasi praktis. Masalah keputusan yang menarik untuk teori tersebut membentuk hierarki kelas yang sangat terstruktur dengan masalah lengkap alami:

FPTW[1]W[2]...W[saya]W[saya+1]...W[P]

FPT=W[1]ETH

W[1]=FPTk

MassimoLauria
sumber