NP adalah singkatan dari Nondeterministic Polynomial time.
Ini adalah pertanyaan pertama saya di situs ini. Saya mengambil kursus master tentang teori perhitungan. Bagaimana Anda akan menjelaskan masalah P = NP kepada seorang anak berusia 10 tahun dan mengapa ia memiliki imbalan uang seperti itu? Anda menerima? Saya akan memperbarui pertanyaan karena...
Kadang-kadang diklaim bahwa Teori Kompleksitas Geometri Ketan Mulmuley adalah satu-satunya program yang masuk akal untuk menyelesaikan pertanyaan terbuka teori kompleksitas seperti pertanyaan P vs NP. Ada beberapa komentar positif dari ahli teori kompleksitas terkenal tentang program ini. Menurut...
Saya tertarik pada generalisasi alami dari 15-puzzle yang terkenal , di mana Anda harus menggeser blok sampai Anda telah mengurutkan semua angka yang diberikan (biasanya ada celah 1 blok). Sekarang generalisasi akan memperluas ukuran puzzle dari 15 ke , di mana satu bidang gratis. Saya telah...
Banyak ahli percaya bahwa benar dan menggunakannya dalam hasil mereka. Kekhawatiran saya adalah bahwa kompleksitasnya sangat tergantung pada .P≠NPP≠NP\mathsf{P} \neq \mathsf{NP}P≠NPP≠NP\mathsf{P} \neq \mathsf{NP} Jadi pertanyaan saya adalah: Selama tidak terbukti, bisakah / haruskah seseorang...
Diketahui oleh Teorema Ladner bahwa jika , maka ada banyak -intermediate ( ) yang tak terhingga jumlahnya . Ada juga kandidat alami untuk status ini, seperti Grafik Isomorfisme, dan sejumlah lainnya, lihat Masalah Antara P dan NPC . Namun demikian, sebagian besar di antara kerumunan yang dikenal...
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}...
Pertanyaan pada cstheory " Apa itu NP terbatas untuk saksi ukuran linier? " Bertanya tentang kelas NP terbatas pada saksi ukuran linear , tetapiO(n)O(n)O(n) Apakah ada masalah NP-complete alami di mana (ya) contoh ukuran membutuhkan saksi ukuran lebih besar dari ?nnnnnn Jelas kita dapat...
Apakah ada contoh mainan yang memberikan wawasan 'esensial' untuk memahami tiga hambatan yang diketahui untuk masalah - relativization, bukti alami dan algebrization?P=NPP=NPP =
Sunting : Seperti yang ditunjukkan Ravi Boppana dengan benar dalam jawabannya dan Scott Aaronson juga menambahkan contoh lain dalam jawabannya , jawaban untuk pertanyaan ini ternyata "ya" dengan cara yang tidak saya harapkan sama sekali. Pertama saya berpikir bahwa mereka tidak menjawab pertanyaan...
Peter Shor menunjukkan bahwa dua masalah NP-intermediate yang paling penting, anjak piutang dan masalah log diskrit, ada di BQP. Sebaliknya, algoritma kuantum yang paling dikenal untuk SAT (pencarian Grover) hanya menghasilkan peningkatan kuadratik daripada algoritma klasik, mengisyaratkan bahwa...
Pertanyaan ini dimigrasikan dari Computer Science Stack Exchange karena dapat dijawab di Theoretical Computer Science Stack Exchange. Bermigrasi 6 tahun yang lalu . Tampaknya banyak orang percaya bahwa , sebagian karena mereka percaya bahwa anjak piutang tidak dapat
Apakah ada contoh bahasa yang ada dalam , tetapi di mana kita tidak dapat membuktikan fakta ini secara langsung dengan menunjukkan bahwa ada saksi polinomial untuk keanggotaan dalam bahasa ini?NPNPNP Sebaliknya, fakta bahwa bahasa dalam akan dibuktikan dengan mereduksinya ke bahasa lain di , di...
Apakah ada masalah alami dalam yang tidak (diketahui / dianggap) di U P ∩ c o U P ?NP∩coNPNP∩coNPNP \cap coNPUP∩coUPUP∩coUPUP \cap coUP Jelas besar satu semua orang tahu tentang di adalah versi keputusan anjak piutang (tidak n memiliki faktor ukuran paling k), tapi itu sebenarnya di U P ∩ c o U P...
Jawaban ini untuk masalah utama yang belum terpecahkan dalam ilmu komputer teoritis? pertanyaan menyatakan bahwa itu terbuka jika masalah tertentu dalam NP membutuhkan waktu .Ω(n2)Ω(n2)\Omega(n^2) Melihat komentar di bawah jawaban membuat saya bertanya-tanya: Selain dari padding dan trik...
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...
Apakah ada bahasa NP-complete (lebih disukai natural) , sehingga untuk setiap n ≥ 1 | L ∩ { 0 , 1 } n | = 2 n - 1 tahan? Dengan kata lain, L mengandung tepat setengah dari semua instance n- bit.L⊆{0,1}∗L⊆{0,1}∗L\subseteq \{0,1\}^*n≥1n≥1n\geq 1 |L∩{0,1}n|=2n−1|L∩{0,1}n|=2n−1|L\cap...
Hal ini terkait dengan pertanyaan, Apakah Ukuran Keanggotaan Saksi untuk Setiap Bahasa NP Sudah Diketahui? Beberapa masalah NPNP\mathsf{NP} (-complete) alami memiliki saksi panjang linier: tugas yang memuaskan untuk SATSATSAT , urutan simpul untuk HAMPATHHAMPATHHAMPATH , dll. Pertimbangkan kelas...
Akses ke oracle akan memberikan percepatan super-polinomial besar untuk semua yang ada di (dengan asumsi set tidak kosong). Hal ini kurang jelas, bagaimanapun, berapa banyak akan manfaat dari akses oracle ini. Tentu saja, percepatan dalam tidak bisa super polinomial, tetapi masih bisa polinomial....
Ini semacam pertanyaan terbuka - yang sebelumnya saya minta maaf. Apakah ada contoh pernyataan yang (tampaknya) tidak ada hubungannya dengan kompleksitas atau mesin Turing tetapi jawabannya akan menyiratkan ?P≠NPP≠NP\mathbf{P}\neq
Saya membaca " Apakah P Versus NP Secara Independen? " Tetapi saya bingung. Dipercaya secara luas dalam teori kompleksitas bahwa . Pertanyaan saya adalah bagaimana jika ini tidak dapat dibuktikan (katakanlah di ). (Mari kita asumsikan bahwa kita hanya mengetahui bahwa independen dari tetapi tidak...