Pertanyaan yang diberi tag np

Ada banyak upaya untuk membuktikan atau , dan secara alami banyak orang berpikir tentang pertanyaan itu, memiliki ide untuk membuktikan arah mana pun.P ≠ N PP = N PP=NP\mathsf{P} = \mathsf{NP} P ≠ N PP≠NP\mathsf{P} \neq \mathsf{NP} Saya tahu bahwa ada pendekatan yang terbukti tidak berhasil, dan...

Saya memiliki pemahaman tingkat tinggi tentang masalah dan saya mengerti bahwa jika itu benar-benar "terbukti" benar dengan solusi yang diberikan, itu akan membuka pintu untuk memecahkan berbagai masalah dalam bidang ilmu komputer.P= NPP=NPP=NP Pertanyaan saya adalah, jika seseorang...

Apakah ada masalah NP-lengkap yang telah membuktikan algoritma waktu subeksponensial? Saya meminta input kasus umum, saya tidak berbicara tentang kasus khusus yang dapat ditelusuri di sini. Dengan sub-eksponensial, maksud saya urutan pertumbuhan di atas polinomial, tetapi kurang dari...

Apakah ada masalah yang diketahui di (dan tidak di ) yang bukan Selesai? Pemahaman saya adalah bahwa saat ini tidak ada masalah yang diketahui, tetapi hal itu belum dikesampingkan sebagai suatu kemungkinan. P N PN PNP\mathsf{NP}PP\mathsf{P}N PNP\mathsf{NP} Jika ada masalah yaitu (dan bukan )...

Seorang kolega saya dan saya baru saja menekan beberapa catatan dari salah satu profesor kami. Catatan menyatakan bahwa ada tugas-tugas yang mungkin diselesaikan dalam waktu polinomial (berada dalam kelas PF) tetapi yang TIDAK dapat diverifikasi dalam waktu polinomial (TIDAK dalam kelas...

Ketika saya menjelaskan bukti Baker-Gill-Solovay bahwa ada oracle yang dapat kita miliki, , dan sebuah oracle yang dengannya kita dapat memiliki kepada teman , muncul pertanyaan mengapa teknik seperti itu tidak cocok untuk membuktikan masalah , dan saya tidak bisa memberikan jawaban yang...

Terlintas dalam banyak hal bahwa dalam semua bukti -completeness yang saya baca (yang dapat saya ingat), selalu sepele untuk menunjukkan bahwa masalahnya ada di , dan menunjukkan bahwa itu adalah -hard adalah ... bagian yang sulit. Apa masalah lengkap yang verifier waktu polinomialnya sangat tidak...

Saya ingin memulai pertanyaan dengan mengatakan saya seorang programmer, dan saya tidak memiliki banyak latar belakang dalam teori kompleksitas. Satu hal yang saya perhatikan adalah bahwa sementara banyak masalah adalah NP-lengkap, ketika diperluas ke masalah optimasi, beberapa jauh lebih sulit...

Jadi saya mengerti ide bahwa masalah keputusan didefinisikan sebagai Apakah ada jalur P sehingga biaya lebih rendah dari C? dan Anda dapat dengan mudah memeriksa ini benar dengan memverifikasi jalur yang Anda terima. Namun, bagaimana jika tidak ada jalur yang sesuai dengan kriteria ini?...

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...

Teorema Galois secara efektif mengatakan bahwa seseorang tidak dapat mengekspresikan akar polinomial derajat> = 5 menggunakan fungsi rasional dari koefisien dan radikal - tidak dapatkah ini dibaca dengan mengatakan bahwa dengan polinomial tidak ada algoritma deterministik untuk menemukan akar?...

Apakah ada penelitian tentang kompleksitas bukti dari resolusi untuk masalah P = NP? Jika tidak, mengingat kurangnya kemajuan pada masalah, apakah tidak masuk akal untuk menduga bahwa bukti apa pun yang menyelesaikan masalah P = NP akan memerlukan sejumlah langkah super

Jika sebenarnya sama dengan , bagaimana hal ini akan meningkatkan algoritma kami menjadi faktor integer lebih cepat. Dengan kata lain, wawasan seperti apa yang akan diberikan fakta ini dalam memahami faktorisasi bilangan bulat lebih baik?PP{\sf P}N PNP{\sf

Saya yakin seseorang telah memikirkan hal ini sebelum atau segera menolaknya, tetapi mengapa teori dikotomi Schaefer bersama dengan teorema Mahaney tentang set jarang tidak menyiratkan P = NP? Inilah alasan saya: Buat bahasa yang sama dengan SAT berpotongan dengan set jarang decidable terbatas....

Ini adalah posting pertama saya setelah menjadi pengguna pasif untuk beberapa waktu sekarang. Saya ingin mengajukan beberapa pertanyaan jika saya bisa. Saya bukan ahli matematika tetapi pertanyaan saya berhubungan dengan bidang matematika / ilmu komputer. Secara khusus, masalah P vs NP. Saya sadar...

Dosen saya membuat pernyataan Masalah yang terbatas tidak dapat NP-Lengkap Dia berbicara tentang Sudoku pada saat itu mengatakan sesuatu di sepanjang garis bahwa untuk 8x8 Sudoku ada satu set solusi yang terbatas tetapi saya tidak ingat persis apa yang dia katakan. Saya menulis catatan yang...

Saya melihat dari posting ini di stackoverflow bahwa ada beberapa algoritma yang relatif cepat untuk menyaring suatu interval angka untuk melihat apakah ada prima dalam interval itu. Namun, apakah ini berarti bahwa masalah keputusan keseluruhan: (Apakah ada prima dalam suatu interval?) Ada di P....

Saya memiliki "bukti" yang sangat sederhana ini untuk NP = CoNP dan saya pikir saya melakukan sesuatu yang salah di suatu tempat, tetapi saya tidak dapat menemukan apa yang salah. Adakah yang bisa membantu saya? Biarkan A menjadi beberapa masalah dalam NP, dan biarkan M menjadi penentu untuk A....

Saya sadar bahwa ini tampaknya pertanyaan yang sangat bodoh (atau terlalu jelas untuk dinyatakan). Namun, saya bingung di beberapa titik. Kami dapat menunjukkan bahwa P NP=== jika dan hanya jika kami dapat merancang algoritma yang memecahkan setiap contoh masalah dalam NP dalam waktu...

Ini mungkin pertanyaan bodoh, tapi saya tidak mengerti. Dalam pertanyaan lain mereka datang dengan teorema dikotomi Schaefer . Bagi saya sepertinya ini membuktikan bahwa setiap masalah CSP adalah dalam P atau NP-complete, tetapi tidak di antaranya. Karena setiap masalah NP dapat diubah dalam waktu...