Apa itu Dugaan P≠NP? Penjelasan yang Mudah Dipahami tentang Masalah Tak Terpecahkan dalam Teori Kompleksitas dan Perbedaan antara Kelas P dan NP

Tentang masalah tak terpecahkan terbesar dalam ilmu komputer, 'Dugaan P≠NP', kami menjelaskan gambaran umumnya dengan mudah dipahami dari perspektif mesin Turing deterministik, disertai dengan perbedaan antara 'Kelas P' yang dapat dipecahkan dalam waktu polinomial dan 'Kelas NP' yang validitas solusinya dapat diverifikasi dalam waktu polinomial.

Ringkasan

1
Kelas P adalah kelas masalah yang dapat diputuskan dalam waktu polinomial pada mesin Turing deterministik, dan kelas NP adalah kelas masalah di mana, ketika diberikan bukti bahwa jawabannya adalah Ya (disebut Saksi), kebenaran Saksi tersebut dapat diverifikasi dalam waktu polinomial (ini disebut verifikasi). Karena masalah yang dapat diputuskan dalam waktu polinomial dapat diverifikasi dalam waktu polinomial, jelas bahwa P⊆NP, namun belum jelas apakah P merupakan himpunan bagian sejati dari NP. Walaupun belum ada buktinya, banyak peneliti percaya bahwa P≠NP. Dugaan bahwa kelas P dan kelas NP tidak sama disebut "Dugaan P≠NP".

Situs referensi : https://daigakudenki.com/np-hard/