Saya pikir saya akan membagikan pertanyaan ini karena mungkin menarik bagi pengguna lain di sini. Asumsikan bahwa fungsi yang berada dalam kelas yang seragam (seperti ) juga berada dalam kelas kecil yang tidak seragam (seperti A C 0 / p o l y , yaitu tidak seragam A C 0 ), apakah ini menyiratkan...
NP⊈P/polyNP⊈P/poly\mathsf{NP} \nsubseteq \mathsf{P}/\text{poly}P ≠ N P N P I : = N P ∖ ( N P C ∪ P ) ≠ ∅ P / poli N P I ⊂ P / poli N P ⊂ N P C ∪ P / poliPH=Σ2PH=Σ2\mathsf{PH} = \Sigma_2P≠NPP≠NP\mathsf{P} \ne \mathsf{NP}NPI:=NP∖(NPC∪P)≠∅NPI:=NP∖(NPC∪P)≠∅\mathsf{NPI} := \mathsf{NP}...
Saya ingin tahu apakah ketidakseragaman membantu fungsi komputasi dalam praktik. Mudah untuk menunjukkan bahwa ada fungsi dalam , mengambil fungsi yang tidak dapat dihitung dan mempertimbangkan bahasa { }, yang jelas memiliki sirkuit sederhana yang tidak seragam , tetapi tidak dapat dihitung secara...
The Karp – Lipton Theoem menyatakan bahwa jika , maka runtuh menjadi . Oleh karena itu, dengan asumsi pemisahan antara dan , no - masalah lengkap akan menjadi milik .P H Σ P 2 Σ P 2 Σ P 3 N P P / p o l yN P ⊂ P / p o l yNP⊂P/poly\mathsf{NP} \subset \mathsf{P/poly}P
Sebuah bahasa dalam L/polyL./halHailyL/poly jika ada mesin Turing logspace yang memutuskan bahasa dengan jumlah saran polinomial. Lihat di sini untuk info lebih lanjut: https://en.wikipedia.org/wiki/L/poly Pertanyaan Apa konsekuensi dari ?P⊆L/polyP⊆L./halHailyP \subseteq...
Dengan diberikannya algoritma yang berjalan dalam waktu , kita dapat mengubahnya menjadi rangkaian keluarga seragam "sepele" untuk masalah ukuran yang sama paling banyak ≈ t ( n ) log t ( n ) .t(n)t(n)t(n)≈t(n)logt(n)≈t(n)logt(n)\approx t(n)\log t(n) Di sisi lain, mungkin kita memiliki sirkuit...
P/poly=NP/polyP/poly=NP/polyP/poly = NP/poly menyiratkanNP⊆P/polyNP⊆P/polyNP \subseteq P/poly , yang pada gilirannya memiliki konsekuensi yang menarik seperti runtuhnya hierarki polinomial. Apakah ada implikasi yang menarik untuk P/poly≠NP/polyP/poly≠NP/polyP/poly \neq NP/poly...
Asisten mengajar mata kuliah telah berhasil menulis sebuah program yang (secara deterministik) menghasilkan pertanyaan-pertanyaan ujian yang sulit. Sekarang, dia ingin menulis sebuah program yang menghasilkan jawaban yang sesuai. Masalah Penguji menanyakan apakah ini selalu mungkin; yang Pemeriksa...
Pertanyaan Umum Apakah teorema hierarki ruang menggeneralisasi ke perhitungan yang tidak seragam? Berikut beberapa pertanyaan spesifik: Apakah ?L/poly⊊PSPACE/polyL/poly⊊PSPACE/polyL/poly \subsetneq PSPACE/poly Untuk semua fungsi pembangun ruang f(n)f(n)f(n) , apakah
Dengan BPP / linear saya merujuk ke mesin BPP dengan saran linier, yang memenuhi janji ketika diberi saran "benar", dan derandomisasi harus memberi kita, katakanlah, algoritma P / linear atau (SUBEXP / linear). Jika kita menggunakan asumsi yang tidak seragam, saya pikir hasil klasik akan berhasil,...
Pertanyaan ini muncul dalam konteks kriptografi, tetapi di bawah ini saya akan menyajikannya dalam hal teori kompleksitas, karena orang-orang di sini lebih mengenal yang terakhir. Pertanyaan ini terkait dengan Masalah dalam NP tetapi tidak dalam Average-P / poly dan Beating Nonuniformity oleh...
Saya telah memikirkan pertanyaan berikut pada berbagai waktu sejak saya melihat pertanyaan tentang Kriptografi ini . Pertanyaan Biarkan menjadi hubungan TFNP . Dapatkah oracle acak membantu P / poli untuk memecahkan R dengan probabilitas yang tidak dapat diabaikan? Lebih
Saya ingin tahu tentang cara di mana Anda telah melihat ketidakseragaman berguna dalam perhitungan. Salah satu caranya adalah keacakan, seperti dalam , dan yang lainnya adalah tabel pencarian yang digunakan untuk menunjukkan bahwa semua bahasa memiliki sirkuit yang tidak seragam.B PP⊆ P./...