Apakah ada hipotesis kompleksitas / kripto yang masuk akal yang mengesampingkan kemungkinan bahwa sirkuit ukuran polinomial memiliki ukuran subeksponensial (yaitu dengan ϵ < 1 ) sirkuit batas-kedalaman ( d = O ( 1 ) )?2O ( nϵ)2HAI(nϵ)2^{O(n^\epsilon)}ϵ <
Termotivasi oleh jawaban Shor terkait dengan berbagai konsep kelengkapan NP, saya mencari masalah yang NP-lengkap di bawah pengurangan P tetapi tidak diketahui NP-lengkap di bawah pengurangan Logspace (lebih disukai untuk waktu yang lama). Juga, Apakah menemukan pengurangan Logspace antara masalah...
Secara umum, query-tape untuk oracle diperhitungkan dalam kompleksitas ruang TM. Namun, tampaknya masuk akal untuk memungkinkan rekaman-saja oracle-tape (seperti yang digunakan dalam pengurangan ruang-L). Apakah konstruksi seperti itu bermanfaat? Apakah itu menghasilkan hasil yang sangat tidak...
Referensi-diri dari masalah P / NP kadang-kadang telah disorot sebagai penghalang untuk penyelesaiannya, lihat, misalnya, makalah Scott Aaronson, apakah P vs. NP independen secara formal ? Salah satu dari banyak resolusi yang dapat dipikirkan untuk P / NP akan menjadi sebuah demonstrasi bahwa...
[Catatan: Saya yakin pertanyaan ini sama sekali tidak bergantung pada benar atau tidaknya makalah Deolalikar.] Di blog Scott Aaronson, Shtetl Optimized , dalam diskusi tentang upaya Deolalikar baru-baru ini pada P vs NP, Leonid Gurvits membuat komentar berikut : Saya mencoba memahami /...
Bahasa daun adalah cara yang indah untuk secara seragam mendefinisikan banyak kelas kompleksitas. Sebagian besar kelas kompleksitas biasanya ditentukan oleh model perhitungan (misalnya, deterministik / acak TM), dan sumber daya terikat (waktu log, ruang poli, dll.). Namun dalam formulasi bahasa...
Membaca beberapa utas baru-baru ini tentang komputasi kuantum (di sini , di sini , dan di sini ), membuat saya ingat pertanyaan menarik tentang kekuatan beberapa jenis mesin pelestarian .ℓhalℓp\ell_p Bagi orang yang bekerja dalam teori kompleksitas menuju kompleksitas kuantum, teks pengantar yang...
Dalam makalah "A Compendium of Problem Complete for P" oleh Greenlaw, Hoover dan Ruzzo (PS) (PDF) , ada daftar masalah dalam P yang tidak diketahui berada di NC dan tidak diketahui juga P-complete. . (Daftar ini merangkum semua masalah terbuka dalam survei yang sangat baik oleh Karp dan...
Lima pertanyaan terkait diajukan, dan satu jawaban terintegrasi diharapkan: T1: Apakah ada bahasa yang dikenali semata-mata oleh mesin-mesin Turing dalam yang runtime eksponennya tidak dapat ditentukan ?LLLPPP T2: Dapatkah contoh mesin Turing ini dibuat secara halus? Q3: Dapatkah mesin...
Dalam kompleksitas yang , . Dugaan bahwa masing-masing wadah adalah tepat.⊆ W [ 2 ] ⊆ … ⊆ W [ P ]F P T ⊆ W [1]FPT⊆W[1]\mathsf{FPT} \subseteq \mathsf{W}[1] ⊆ W [ 2 ]⊆W[2]\subseteq \mathsf{W}[2] ⊆ ... ⊆ W [ P.]⊆…⊆W[P]\subseteq \ldots \subseteq \mathsf{W}[P] Jika maka .P = W [ P ]F P T = W...
Sudah diketahui bahwa palindrom dapat dikenali dalam waktu linier pada mesin Turing pita, tetapi tidak pada mesin Turing pita tunggal (dalam hal ini waktu yang dibutuhkan adalah kuadratik). Algoritma linear-waktu menggunakan salinan input, dan dengan demikian juga menggunakan ruang...
Misalkan kita memiliki masalah yang diparameterisasi dengan p-parameter bernilai riil yang "mudah" untuk dipecahkan ketika dan "hard" ketika untuk beberapa nilai , . p = p 1 p 0 p 1p = p0p=p0p=p_0p = p1p=p1p=p_1hal0p0p_0hal1p1p_1 Salah satu contohnya adalah menghitung konfigurasi putaran pada...
Saya mencari survei yang bagus tentang algoritma dan kompleksitas aljabar linier (operasi seperti pangkat, kebalikan, nilai eigen, ... untuk Boolean, , dan matriks bilangan bulat / rasional) dengan penekanan pada paralel ( hierarki ) dan algoritma polytime. Saya tidak dapat menemukan yang baru....
Grafik garis hypergraph adalah (sederhana) grafik memiliki tepi sebagai simpul dengan dua tepi berdekatan dalam jika mereka memiliki persimpangan nonempty. Hypergraph adalah -hypergraph jika masing-masing ujungnya memiliki paling banyak simpul.GHHHGGGHHHHHHGGGrrrrrr Apa kompleksitas masalah...
Dalam kelas kompleksitas , ada beberapa masalah yang diduga TIDAK berada di kelas , yaitu masalah dengan algoritma paralel deterministik. Masalah Arus Maksimum adalah salah satu contohnya. Dan ada masalah PERCAYA berada di , tetapi bukti belum ditemukan.N C N
Seberapa cepat algoritma nondeterministic untuk menyelesaikan masalah EXPTIME harus menyiratkan P ≠ N PP≠NPP \neq NP ? Sebuah waktu polinomial algoritma nondeterministic akan segera menyiratkan ini karena P ≠ E X P T I M EP≠EXPTIMEP \neq EXPTIME tapi tidak ada yang percaya N P = E X P T I M...
Katakanlah bahasa adalah P -density-close jika ada algoritma waktu polinomial yang memutuskan pada hampir semua input dengan benar.LLLLLLL Dengan kata lain, ada P , sehingga menghilang, yang berarti Ini juga berarti bahwa pada input acak yang seragam, algoritma polytime untuk A akan memberikan...
Judulnya kurang lebih menyebutkan semuanya, tapi saya rasa saya bisa menambahkan sedikit latar belakang dan beberapa contoh spesifik yang saya minati. Para ahli teori kompleksitas deskriptif, seperti Immerman dan Fagin, telah mengkarakterisasi banyak kelas kompleksitas yang paling terkenal...
Negara-negara PCP teorema bahwa tidak ada algoritma waktu polinomial untuk MAX 3SAT untuk menemukan tugas memuaskan klausul formula 3SAT satisfiable kecuali P = N P .7 / 8 + ε7/8+ϵ7/8+ \epsilonP= NPP=NPP = NP Ada sepele polinomial waktu algoritma yang memenuhi dari klausa. Jadi, bisa kita lakukan...
Diskusi : Saya telah menghabiskan waktu pribadi akhir-akhir ini mempelajari berbagai hal dalam kompleksitas komunikasi. Sebagai contoh, saya telah membiasakan diri dengan bab yang relevan di Arora / Barak, mulai membaca beberapa makalah, dan memesan buku oleh Kushilevitz / Nisan. Secara intuitif,...