Masalah dalam waktu kuasi-polinomial yang bisa jadi ada di P (tanpa menyebabkan runtuh atau melanggar kepercayaan yang dipegang secara luas)

Apa adalah beberapa contoh dari masalah dengan waktu kuasi-polinomial ( ) algoritma yang dibayangkan bisa berada di . Dengan kata lain, mereka berada di tanpa alasan yang jelas selain tidak ada yang menemukan algoritma polinomial-waktu?P Q $QP$$P$$QP$

Pertanyaan ini dimotivasi oleh hasil grafik isomorfisme terbaru (yang merupakan jawaban yang valid untuk pertanyaan ini)

Beberapa non-contoh adalah

• Menemukan klik ukuran dalam grafik$\log^{100} n$
• Menemukan jalur ukuran dalam grafik$\log^{100} n$
• Memecahkan k-sum untuk $k=\log^{100} n$
• Set dominasi minimum dalam turnamen

Salah satu masalah ini berada di akan melanggar hipotesis waktu eksponensial (ETH).$P$

Isomorfisme Kelompok! Meskipun Ricky Demer memberi banyak (walaupun tentu saja tidak semua) detail tentang ini, ada poin penting yang ingin saya soroti, esp. diberikan motivasi yang dinyatakan untuk pertanyaan, yaitu:

Menempatkan Isomorfisme Kelompok ke dalam adalah hambatan utama untuk menempatkan Grafik Isomorfisme ke dalam $\mathsf{P}$$\mathsf{P}$

Isomorfisme Kelompok (bila diberikan oleh tabel perkalian) direduksi menjadi Grafik Isomorfisme, sehingga hal di atas secara teknis selalu benar. Tetapi ketika Grafik Iso naik di sangat jauh dari Kelompok Iso2(logn)2sehingga jelas ada hambatan lain di jalan. Jika Grafik Iso adalah dalam waktu2(logn) O ( 1 ) , Kelompok isomorfisma kemudian hambatan jauh lebih relevan dengan menempatkan Grafik isomorfisma dalamP. Secara khusus, ini menunjukkan bahwa algoritma Babai menangani banyak [1] dari kombinatorik GI, dan masalahnya sekarang adalah aljabar keras. (Bukan berarti tidak ada aljabar keras dalam GI, tetapi GroupIso secaradefinisitentang aljabar.)$2^{\tilde{O}(\sqrt{n})}$$2^{(\log n)^2}$$2^{(\log n)^{O(1)}}$$\mathsf{P}$

[1] Saya tidak akan mengatakan "semua" dari kombinatorik, karena eksponen dalam algoritma Babai kemungkinan besar , yang masih akan meninggalkan celah antara GI dan GroupIso. Juga karena mungkin masih ada beberapa kombinatorik yang duduk di dalam aljabar GroupIso ...$> 2$

Memecahkan masalah clique ditanam membedakan grafik seragam acak dari penyatuan grafik acak dan klik (ukuran menengah antara dan $2\log_2 n$ ), dengan probabilitas keberhasilan dibatasi dari 1/2. Ini berbeda dari contoh pelanggaran ETH Anda dalam menemukan klik seukuran polylog dalam grafik arbitrer, karena ini merupakan masalah rata-rata bukan yang terburuk.$\sqrt n$

Isomorfisme kelompok adalah masalah lain yang diketahui
dengan baik yang diketahui dapat dipecahkan dalam waktu kuasi polinomial. Hasil itu dapat digeneralisasi
ke objek terbatas lainnya yang "memperluas" grup dalam arti yang sesuai -
[ semut komutatif dengan properti produk nol ] dan grupoid komutatif
keduanya tidak cukup dekat, tetapi [ Θ (1) tupel panjang grup dengan label pada beberapa tupel
set elemen grup (yang tidak harus dari grup yang sama)] semuanya berfungsi.
(Itu cukup luas, karena tupel berlabel singlet memungkinkan fungsi enkode,
dan kemudian memiliki tupel grup memungkinkan terpisahskalar dan vektor .)

Untuk jawaban ini, grup diberikan oleh tabel Cayley . Ingatlah bahwa masalah yang akan saya
sebutkan hanyalah "benar-benar" yang diketahui berada di SUBEXP ketika salah satu [grup yang mendasarinya
tidak harus semuanya abelian] atau [mereka dapat memiliki "jumlah yang cukup besar" dari pelabelan yang yang
tidak dicakup oleh [a "kecil" jumlah [[subkelompok dari jumlah langsung dari kelompok-kelompok] dan / atau
[fungsi dari dan ke subkelompok tersebut yang mendistribusikan lebih Selain]]]], karena kalau tidak
semuanya bisa dikompresi secara eksponensial dengan mengungkapkan hal dalam hal menghasilkan set,
dalam hal ini memberikan tabel penuh sebagai gantinya pada dasarnya akan berjumlah padding input.

Untuk input yang terdiri dari [pasangan yang dipesan $\langle \hspace{-0.02 in}$A, B Dari tupel tupel yang panjangnya keduanya L] dan [bilangan bulat non-negatif c sehingga L dan c keduanya dalam O (1)] dan tupel panjang-L dari kemungkinan pembatasan pada injecitvity / surjectivity /zeroness, keberadaan lebih dari c [morfisme dari [objek kiri dari pasangan terurut] ke [objek kanan dari pasangan terurut] yang mana homomorfisma kelompok komponenL memenuhi batasan yang sesuai] dapat ditentukan dalam GC(O (log (maks ( cardinality_of_A's_groups)) ⋅ log (maks (cardinality_of_B's_groups))),logspace) olehhasil Reingold, karena verifiermemiliki akses baca dua arahke bukti yang diduga. $\hspace{-0.02 in}\rangle$



$\cdot$

Selain itu (masih menggunakan Reingold), mesin logspace dapat menghitung morfisme seperti itu yang diberikan
akses 2 arah ke saksi tersebut, dan jika mereka juga memiliki akses 2 arah ke rekaman acak,
maka mereka dapat memberikan [[a] bukti pengetahuan dengan sehubungan dengan ekstraktor yang memiliki akses baca 2 arah
ke apa yang sudah dikeluarkan] dari saksi seperti itu untuk isomorfisma] dengan sifat yang sama
seperti ZK P oK biasa untuk graf isomorfisme] ke verifier logspace dengan akses baca 2 arah ke
keacakan sendiri dan pesan pepatah. Demikian pula, sistem bukti HVSZK untuk grafik
non- isomorfisme pada dasarnya tidak berubah ke objek dari jenis paragraf ini.

$\cdot \hspace{-0.02 in}\lceil \hspace{-0.03 in}$log ₂ (cardinality_of_the_group)$\hspace{-0.02 in}\rceil$

Sebagai akibatnya, seseorang dapat memperoleh hal-hal tersebut mulai dari
"subkelompok-isomorfisme" yang sederhana hingga yang sederhana , hingga "jumlah minimum elemen yang moderat yang dapat
digabungkan dengan subset tertentu dari grup abelian untuk menghasilkan seluruh grup",
dengan sengaja rumit--to-negara
"Mengingat domain yang skalar hanya perlu untuk membentuk r$\hspace{.02 in}$ng dan kode domain dengan
penambahan "vektor" yang tidak harus komutatif, adakah lebih dari 3 homomorfisme aljabar sehingga peta pada skalar bukan nol r$\hspace{.02 in}$ng morfisme dan peta pada "vektor" adalah injeksi? "
semua dalam GC$\hspace{-0.02 in}\big(\hspace{-0.03 in}O\big(\hspace{-0.03 in}$$^2\hspace{-0.03 in}\big)\hspace{-0.03 in}$, ruang log$\hspace{-0.03 in}\big)\hspace{-0.02 in}$, dan dengan demikian secara khusus dapat dipecahkan dalam waktu kuasi polinomial.


Selain dari fakta bahwa [ sejak 2011 , pekerjaan yang signifikan pada masalah ini "hanya" mengurangi separuh eksponen runtime untuk grup umum dan memotong eksponen runtime untuk grup yang dapat dipecahkan ],
saya tidak mengetahui adanya bukti bahwa masalah seperti itu seharusnya tidak ada dalam P.


Bukti bahwa masalah dari jawaban ini adalah "tidak terlalu sulit":

Saya sudah menyebutkan sistem bukti ZKPoK dan HVSZK.
Setiap kali ada "tidak terlalu banyak" objek non-isomorfik, [memberikan verifikasi "tidak terlalu lama" saran string dan membiarkan bukti berisi pointer ke lokasi di dalamnya] sudah cukup untuk
memverifikasi tambahan komplemen dari jenis masalah ini jawabannya sudah ada sebelum kalimat ini.
(Penunjuknya adalah ke tempat string saran memberikan [2 objek referensi yang objek
inputnya isomorfik] dan jawaban untuk mereka.)
Dengan jawaban ini terikat pada jumlah kelompok non-isomorfik (yang saya tidak tahu caranya membuktikan), setiap kali tupel berlabel dicakup oleh kombinasi
$\:\: \big[\hspace{-0.02 in}$
$\big[\hspace{-0.02 in}$$O\big(\hspace{-0.03 in}$$^2\hspace{-0.03 in}\big)\big]\big]\hspace{-0.02 in}$
$n^{O\left((\log(n))^{\hspace{.02 in}2}\hspace{-0.02 in}\right)}$

$O\big(\hspace{-0.03 in}$log ⁶ n$\hspace{-0.03 in}\big)$$O\big(\hspace{-0.03 in}$log ² n$\hspace{-0.03 in}\big)$

$O(\log^3 k)$$O(i^2 k^{1/i})$$n^{O(i)}$

Terkait dengan masalah ini adalah masalah Submodular Orienteering dan kasus khusus. http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=1530718&url=http%3A%2F%2Fieeexplore.ieee.org%2Fxpls%2Fabs_all.jsp%3Farnumber%3D1530718

$\mathcal{H}:=(V,{\cal E}\subseteq 2^V)$${\cal H}$$V$${\cal E}$

${\cal H}$${\cal T}$

${\cal T}$${\cal H}$

Algoritma yang paling terkenal adalah algoritma kuasi-polinomial waktu (yang pertama adalah yang oleh Fredman dan Khachiyan http://dx.doi.org/10.1006/jagm.1996.0062

Masalahnya dikenal sebagai Monotone Boolean Duality atau Hypergraph Duality dan beberapa masalah enumerasi dapat direduksi menjadi masalah ini atau setara dengan itu (misalnya enumerasi set dominasi minimal setara dengan masalah ini). Ini sebenarnya diyakini berada di P.