Banyak yang percaya bahwa . Namun kita hanya tahu bahwa B P P berada pada tingkat kedua hierarki polinomial, yaitu B P P ⊆ Σ P 2 ∩ Π P 2 . Langkah menuju menunjukkan B P P = P adalah untuk pertama membawanya ke tingkat pertama dari hirarki polinomial, yaitu B P P ⊆ N P .BPP=P⊆NPBPP=P⊆NP\mathsf{BPP}...
Apakah ada contoh mainan yang memberikan wawasan 'esensial' untuk memahami tiga hambatan yang diketahui untuk masalah - relativization, bukti alami dan algebrization?P=NPP=NPP =
Telah diketahui dengan baik bahwa bukti apa pun yang menyelesaikan pertanyaan P vs NP harus mengatasi relativization , bukti alami dan hambatan algebrization . Diagram berikut ini membagi "ruang bukti" menjadi beberapa wilayah. Sebagai contoh, sesuai dengan set bukti yang merelatifkan dan...
Baru-baru ini, Ryan Willams membuktikan bahwa Konstruktivitas dalam Bukti Alami tidak dapat dihindari untuk memperoleh pemisahan kelas kompleksitas: dan T C 0 . NEXPNEXP\mathsf{NEXP}TC0TC0\mathsf{TC}^{0} Constructivity di Bukti Alam adalah suatu kondisi bahwa semua bukti kombinatorial di memenuhi...
Ungkapan tepat dari judul adalah karena Anand Kulkarni (yang mengusulkan situs ini dibuat). Pertanyaan ini diajukan sebagai contoh pertanyaan, tetapi saya sangat ingin tahu. Saya tahu sedikit tentang geometri aljabar, dan pada kenyataannya juga hanya memiliki sepintas, pemahaman sarjana tentang...
Kita semua tahu menunjukkan bahwa memiliki penghalang. Kita semua telah mempelajari hambatan ini karena kami percaya P ≠ N P .P≠ NPP≠NPP\ne NPP≠ NPP≠NPP\ne NP Namun anggap dan ada orang bijak yang percaya bahwa kemungkinan ada . Jika ini memang benar maka fakta bahwa kita belum melihat algoritma...
Saya tidak ingat pernah melihat pemisahan kelas yang tidak didasarkan pada hasil diagonalisasi dan relatisasi. Diagonisasi masih dapat digunakan untuk memisahkan kelas yang diketahui yang tersisa, karena argumen non-relativiasi mungkin masih digunakan dalam kesimpulan diagonalisasi, atau dalam...
Ini adalah tindak lanjut dari pertanyaan saya sebelumnya: Kompleksitas waktu deterministik yang diketahui paling baik untuk masalah alami dalam NP Saya merasa bingung bahwa kami belum dapat membuktikan waktu deterministik kuadratik lebih rendah untuk masalah NP yang menarik yang orang pedulikan...
Do Alam Bukti , perelatifan dan Algebrization juga mempengaruhi pemisahan kelas kompleksitas lain seperti dll?L ≠ NL ≠ NP≠ c o NP≠ P.H≠ P.SPA CEL≠NL≠NP≠coNP≠PH≠PSPACEL\neq NL\neq NP\neq coNP \neq PH\neq PSPACE Misalnya bukti alami penghalang harus mempengaruhi bukti karena akan memisahkan P ≠ N P...