Pertanyaan yang diberi tag «complexity-classes»

Pertanyaan tentang hubungan antara kelas kompleksitas.


Mengapa kami percaya bahwa PSPACE ≠ EXPTIME?
Saya mengalami kesulitan memahami mengapa PSPACE secara umum diyakini berbeda dari EXPTIME. Jika PSPACE adalah serangkaian masalah yang dapat dipecahkan dalam polinomial ruang dalam ukuran input , lalu bagaimana mungkin ada kelas masalah yang mengalami ledakan waktu eksponensial yang lebih besar dan tidak menggunakan ruang eksponensial?f(n)f(n)f(n) Jawaban Yuval Filmus sudah …




Apakah
Apakah mungkin dan kardinalitas dari sama dengan kardinalitas dari ? Atau apakah berarti bahwa dan harus memiliki kardinalitas yang berbeda?P N P P ≠ N P P N PP ≠ N PP≠NP\mathsf{P} \not = \mathsf{NP}PP\mathsf{P}N PNP\mathsf{NP}P ≠ N PP≠NP\mathsf{P} \not = \mathsf{NP}PP\mathsf{P}N PNP\mathsf{NP}



Bukti teorema Karp-Lipton
Saya mencoba memahami bukti teorema Karp-Lipton sebagaimana dinyatakan dalam buku "Kompleksitas Komputasi: Suatu pendekatan modern" (2009). Secara khusus, buku ini menyatakan sebagai berikut: Teorema Karp-Lipton Jika NP , maka PH .P ∖ p o l y⊆⊆\subseteq P∖ p o l yP∖halHailyP_{\backslash poly} =Σp2=Σ2hal= \Sigma^p_2 Bukti: Dengan Teorema 5.4, untuk menunjukkan …

Apakah ada kelas kompleksitas yang ditetapkan dengan bilangan real?
Seorang siswa baru-baru ini meminta saya untuk memeriksa bukti kekerasan NP untuk mereka. Mereka melakukan pengurangan sepanjang garis: Saya mengurangi masalah ini P′P′P' yang dikenal sebagai NP-lengkap untuk masalah saya PPP (dengan banyak-satu pengurangan poli-waktu), jadi PPP adalah NP-keras. Jawaban saya pada dasarnya: Karena PPP memiliki instance dengan nilai-nilai dari …




Apakah ada masalah AM-complete yang diketahui / apakah AM-complete didefinisikan dengan baik?
Saya ingin tahu apakah ada masalah lengkap di kelas kompleksitas Arthur-Merlin. Grafik Non-Isomorfisme (GNI) tampaknya menjadi contoh kanonik dari suatu masalah di AM, tapi itu mungkin bukan yang lengkap. Saya kira saya juga bertanya-tanya apakah masalah "lengkap" didefinisikan dengan baik untuk AM. Karena AM = BP.NP, tampaknya pergi ke "reduksi" …

Apa itu kelas kompleksitas
Apa yang dimaksud dengan kelas kompleksitas ? Saya tahu bahwa adalah kelas kompleksitas yang berisi bahasa yang ada polinomial waktu nondeterministik mesin Turing sedemikian sehingga jika jumlah keadaan penerimaan mesin pada input aneh.⊕P⊕P⊕P⊕P\oplus P^{\oplus P}⊕P⊕P\oplus PAAAMMMx∈Ax∈Ax \in AMMMxxx Tapi apa artinya ? Saya tidak bisa mengikuti apa yang sebenarnya :)⊕P⊕P⊕P⊕P\oplus …

Dengan menggunakan situs kami, Anda mengakui telah membaca dan memahami Kebijakan Cookie dan Kebijakan Privasi kami.
Licensed under cc by-sa 3.0 with attribution required.