Saya mencoba memahami klasifikasi ini dan mengapa ada. Apakah pemahaman saya benar? Jika tidak, apa?

1. P adalah kompleksitas polinomial, atau untuk beberapa bilangan real non-negatif , seperti , dll. Jika masalah milik P, maka ada setidaknya satu algoritma yang dapat menyelesaikannya dari awal dalam waktu polinomial. Sebagai contoh saya selalu dapat mencari tahu apakah beberapa bilangan bulat adalah prima dengan mengulangi dan memeriksa pada setiap langkah jika terbagi .O(nk)kO(1), O(n1/2), O(n2), O(n3)n2 <= k <= sqrt(n)kn

2. NP adalah kompleksitas polinomial non-deterministik. Saya tidak benar-benar tahu apa artinya menjadi non-deterministik. Saya pikir itu berarti mudah untuk memverifikasi dalam waktu polinomial, tetapi mungkin atau tidak mungkin waktu polinomial untuk menyelesaikan dari awal jika kita belum tahu jawabannya. Karena dapat dipecahkan dalam waktu polinomial, semua masalah P juga merupakan masalah NP. Faktorisasi bilangan bulat dikutip sebagai contoh NP, tetapi saya tidak mengerti mengapa itu bukan P, secara pribadi, karena faktorisasi percobaan memerlukan O(sqrt(n))waktu.

3. Lengkap NP Saya tidak mengerti sama sekali, tetapi Traveling Salesman Problem dikutip sebagai contoh dari ini. Tetapi menurut saya masalah TSP mungkin hanya NP, karena butuh sesuatu seperti memverifikasi jika Anda diberi jalan di depan.O(2n n2) time to solve, but O(n)

4. NP-Hard Saya berasumsi hanya penuh dengan yang tidak diketahui. Sulit diverifikasi, sulit dipecahkan.

Anda pada dasarnya benar tentang P dan NP, tetapi bukan tentang NP-hard dan NP-complete.

Sebagai permulaan, berikut adalah definisi yang sangat ringkas dari empat kelas kompleksitas yang dimaksud:

• P adalah kelas masalah keputusan yang dapat diselesaikan dalam waktu polinomial oleh mesin Turing deterministik.

• NP adalah kelas masalah keputusan yang dapat diselesaikan dalam waktu polinomial oleh mesin Turing non-deterministik. Secara ekivalen, itu adalah kelas masalah yang dapat diverifikasi dalam waktu polinomial oleh mesin Turing deterministik.

• NP-hard adalah kelas masalah keputusan yang semua masalah dalam NP dapat direduksi menjadi dalam waktu polinomial oleh mesin Turing deterministik.

• NP-complete adalah persimpangan NP-hard dan NP. Secara ekuivalen, NP-complete adalah kelas masalah keputusan dalam NP yang semua masalah dalam NP dapat direduksi menjadi dalam waktu polinomial oleh mesin Turing deterministik.

Dan inilah diagram Euler dari Wikipedia yang menunjukkan hubungan antara empat kelas ini (dengan asumsi bahwa P tidak sama dengan NP):

Bagian yang saya anggap paling tidak Anda kenal atau bingung adalah gagasan tentang "pengurangan waktu polinomial" dari masalah X ke masalah Y. Pengurangan dari X ke Y hanyalah sebuah algoritma A yang memecahkan X dengan memanfaatkan beberapa algoritma B lainnya yang memecahkan masalah Y. Pengurangan ini disebut "pengurangan waktu polinomial" jika semua bagian dari A selain B memiliki kompleksitas waktu polinomial. Sebagai contoh sepele, masalah menemukan elemen terkecil dalam array adalah waktu konstan yang dapat direduksi menjadi masalah pengurutan, karena Anda dapat mengurutkan array dan kemudian mengembalikan elemen pertama dari array yang diurutkan.

Satu hal yang mudah terlewatkan tentang definisi NP-hard adalah bahwa pengurangan beralih dari masalah NP ke masalah NP-hard, tetapi tidak harus sebaliknya . Ini berarti bahwa masalah NP-hard mungkin dalam NP, atau dalam kelas kompleksitas yang jauh lebih tinggi (seperti yang Anda lihat dari diagram Euler), atau mereka bahkan mungkin bukan masalah yang dapat ditentukan. Itu sebabnya orang sering mengatakan sesuatu seperti "NP-hard berarti setidaknya sekeras NP" ketika mencoba menjelaskan hal-hal ini secara informal.

Masalah penghentian adalah contoh yang baik dari masalah NP-hard yang jelas tidak ada di NP, seperti yang dijelaskan Wikipedia :

Sangat mudah untuk membuktikan bahwa masalah penghentian adalah NP-hard tetapi tidak NP-complete. Sebagai contoh, masalah kepuasan Boolean dapat direduksi menjadi masalah penghentian dengan mentransformasikannya ke deskripsi mesin Turing yang mencoba semua penetapan nilai kebenaran dan ketika ia menemukan salah satu yang memenuhi formula, ia berhenti dan jika tidak maka akan menjadi loop tak terhingga. Juga mudah untuk melihat bahwa masalah penghentian tidak ada dalam NP karena semua masalah dalam NP dapat ditentukan dalam sejumlah operasi yang terbatas, sedangkan masalah penghentian, secara umum, tidak dapat diputuskan.

Faktorisasi bilangan bulat dikutip sebagai contoh NP, tetapi saya tidak mengerti mengapa itu bukan P, secara pribadi, karena faktorisasi percobaan memerlukan waktu O (sqrt (n)).

Untuk keperluan kelas kompleksitas, npanjang input. Jadi jika Anda ingin faktor bilangan bulat k, ntidak ktapi log k, jumlah bit (atau apa pun) yang diperlukan untuk menuliskan nomor. Jadi faktorisasi bilangan bulat adalah O(sqrt(k))seperti yang Anda katakan, tetapi ini adalah yang mana .O(sqrt(2n))O(2(n/2))

NP-Hard Saya berasumsi hanya penuh dengan yang tidak diketahui. Sulit diverifikasi, sulit dipecahkan.

Tidak. NP-Hard hanya tentang seberapa sulit masalah untuk dipecahkan.

Masalah NP-Hard setidaknya sulit sebagai masalah yang paling sulit di NP. Kami tahu mereka setidaknya sekeras itu, karena jika kami memiliki algoritma waktu polinomial untuk masalah NP-Hard, kami dapat mengadaptasi algoritma itu untuk masalah apa pun di NP.

Lengkap NP Saya tidak mengerti sama sekali

NP-Complete berarti bahwa masalahnya adalah NP dan NP-Hard. Ini berarti bahwa kita dapat memverifikasi solusi dengan cepat (NP), tetapi setidaknya sekeras masalah tersulit dalam NP (NP-Hard).

Saya tidak benar-benar tahu apa artinya menjadi non-deterministik.

Non-determinisme adalah definisi alternatif NP. Mesin turing non-deterministik secara efektif dapat menduplikasi dirinya sendiri kapan saja, dan meminta setiap duplikat mengambil jalur eksekusi yang berbeda. Di bawah definisi ini, NP adalah himpunan masalah yang dapat diselesaikan dalam waktu polinomial oleh komputer daripada duplikat itu sendiri. Ternyata ini adalah kumpulan masalah yang persis sama yang dapat diverifikasi dalam waktu polinomial.

Hal pertama yang harus dipahami adalah bahwa P dan NP mengklasifikasikan bahasa , bukan masalah . Untuk memahami apa artinya ini, kita perlu beberapa definisi lain terlebih dahulu.

Sebuah alfabet adalah himpunan berhingga tidak kosong dari simbol-simbol.

{ 0, 1} adalah alfabet seperti set karakter ASCII. {} bukan alfabet karena kosong. N (bilangan bulat) bukan alfabet karena tidak terbatas.

Biarkan Σ menjadi alfabet. Rangkaian terurut dari sejumlah simbol dari Σ disebut kata lebih dari Σ .

String 101adalah kata di atas alfabet { 0, 1}. Kata kosong (sering ditulis sebagai ε ) adalah kata di atas semua alfabet. String penguinadalah kata di atas alfabet yang berisi karakter ASCII. Notasi desimal dari jumlah π bukan kata lebih alfabet { ., 0, 1, 2, 3, 4, 5, 6, 7, 8, 9} karena tidak terbatas.

The panjang dari sebuah kata w , ditulis sebagai | w |, adalah jumlah simbol di dalamnya.

Misalnya, | hello| = 5 dan | ε | = 0. Untuk kata apa saja w , | w | ∈ N dan karenanya terbatas.

Biarkan Σ menjadi alfabet. Set Σ ^＊ berisi semua kata di atas Σ , termasuk ε . Set Σ ⁺ berisi semua kata di atas Σ , tidak termasuk ε . Untuk n ∈ N , Σ ⁿ adalah himpunan kata-kata panjang n .

Untuk setiap alfabet Σ , Σ ^＊ dan Σ ⁺ adalah himpunan yang tak terhingga jumlahnya . Untuk set karakter ASCII Σ _ASCII , ekspresi reguler .*dan masing-masing .+menyatakan Σ _ASCII ^＊ dan Σ _ASCII ⁺ .

{ 0, 1} ⁷ adalah himpunan kode ASCII 7-bit { 0000000, 0000001, ..., 1111111}. { 0, 1} ³² adalah himpunan nilai integer 32 bit.

Biarkan Σ menjadi alfabet dan L ⊆ Σ ^＊ . L disebut bahasa lebih dari Σ .

Untuk alfabet Σ , set kosong dan Σ ^＊ adalah bahasa yang sepele di atas Σ . Yang pertama sering disebut sebagai bahasa kosong . Bahasa kosong {} dan bahasa yang hanya berisi kata kosong { ε } berbeda.

Subset dari { 0, 1} ³² yang sesuai dengan nilai floating point non-NaN IEEE 754 adalah bahasa yang terbatas.

Bahasa dapat memiliki jumlah kata yang tidak terbatas tetapi setiap bahasa dapat dihitung. Set string { 1, 2, ...} yang menunjukkan bilangan bulat dalam notasi desimal adalah bahasa yang tak terbatas selama alfabet { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. Set tak terbatas string { 2, 3, 5, 7, 11, 13, ...} yang menunjukkan bilangan prima dalam notasi desimal adalah bagian yang tepat daripadanya. Bahasa yang mengandung semua kata yang cocok dengan ekspresi reguler [+-]?\d+\.\d*([eE][+-]?\d+)?adalah bahasa di atas set karakter ASCII (menunjukkan subset dari ekspresi floating-point yang valid seperti yang didefinisikan oleh bahasa pemrograman C).

Tidak ada bahasa yang mengandung semua bilangan real (dalam notasi apa pun) karena himpunan bilangan real tidak dapat dihitung.

Biarkan Σ menjadi alfabet dan L ⊆ Σ ^＊ . Sebuah mesin D memutuskan L jika untuk setiap input w ∈ Σ ^＊ menghitung fungsi karakteristik χ _L ( w ) dalam waktu terbatas. Fungsi karakteristik didefinisikan sebagai

χ L : Σ ＊ → {0, 1}
     w   ↦ 1,   w ∈ L 
         0, jika tidak.

Mesin tersebut disebut penentuan untuk L . Kami menulis " D ( w ) = x " untuk "diberikan w , D output x ".

Ada banyak model mesin. Yang paling umum yang dalam penggunaan praktis saat ini adalah model mesin Turing . Mesin Turing memiliki penyimpanan linier tak terbatas yang dikelompokkan ke dalam sel. Setiap sel dapat memegang tepat satu simbol alfabet pada suatu titik waktu. Mesin Turing melakukan komputasi sebagai urutan langkah-langkah perhitungan. Di setiap langkah, ia dapat membaca satu sel, mungkin menimpa nilainya dan memindahkan kepala baca / tulis dengan satu posisi ke sel kiri atau kanan. Tindakan apa yang akan dilakukan mesin dikontrol oleh otomat keadaan terbatas.

Mesin akses acak dengan serangkaian instruksi terbatas dan penyimpanan tidak terbatas adalah model mesin lain yang sekuat model mesin Turing.

Demi diskusi ini, kami tidak akan mengganggu kami dengan model mesin yang tepat kami gunakan tetapi cukup untuk mengatakan bahwa mesin memiliki unit kontrol deterministik yang terbatas, penyimpanan tidak terbatas dan melakukan perhitungan sebagai urutan langkah-langkah yang dapat dihitung.

Karena Anda sudah menggunakannya dalam pertanyaan Anda, saya berasumsi bahwa Anda sudah terbiasa dengan notasi "besar-O" jadi di sini hanya penyegaran cepat.

Biarkan f : N → menjadi fungsi. Himpunan O ( f ) berisi semua fungsi g : N → N yang memiliki konstanta n ₀ ∈ N dan c ∈ N sehingga untuk setiap n ∈ N dengan n > n ₀ memang benar bahwa g ( n ) ≤ c f ( n ).

Sekarang kita siap untuk mendekati pertanyaan sebenarnya.

Kelas P berisi semua bahasa L yang memiliki mesin Turing D yang menentukan L dan konstanta k ∈ N sehingga untuk setiap input w , D berhenti setelah paling banyak langkah T (| w |) untuk fungsi T ∈ O ( n ↦ n ^k ).

Karena O ( n ↦ n ^k ), walaupun secara matematis benar, tidak nyaman untuk menulis dan membaca, kebanyakan orang - jujur, semua orang kecuali saya - biasanya menulis hanya O ( n ^k ).

Perhatikan bahwa terikat tergantung pada panjang w . Oleh karena itu, argumen yang Anda buat untuk bahasa bilangan prima hanya benar untuk angka dalam pengkodean unaray , di mana untuk encoding w dari sejumlah n , panjang pengkodean | w | sebanding dengan n . Tidak seorang pun akan menggunakan pengkodean semacam itu dalam praktiknya. Menggunakan algoritma yang lebih maju daripada sekadar mencoba semua faktor yang mungkin, dapat ditunjukkan, bagaimanapun, bahwa bahasa bilangan prima tetap dalam P jika input dikodekan dalam biner (atau ke pangkalan lain). (Meskipun memiliki minat besar, ini hanya bisa dibuktikan oleh Manindra Agrawal, Neeraj Kayal, dan Nitin Saxena dalam makalah pemenang penghargaan pada tahun 2004 sehingga Anda dapat menebak bahwa algoritma ini tidak terlalu sederhana.)

Bahasa trivial {} dan Σ ^＊ dan bahasa non-trivial { ε } jelas dalam P (untuk alfabet apa saja Σ ). Bisakah Anda menulis fungsi dalam bahasa pemrograman favorit Anda yang mengambil string sebagai input dan mengembalikan boolean yang mengatakan apakah string adalah kata dari bahasa untuk masing-masing dan membuktikan bahwa fungsi Anda memiliki kompleksitas run-time polinomial?

Setiap reguler bahasa (bahasa dijelaskan oleh ekspresi reguler) dalam P .

Biarkan Σ menjadi alfabet dan L ⊆ Σ ^＊ . Sebuah mesin V yang mengambil tuple yang dikodekan dari dua kata w , c ∈ Σ ^＊ dan menghasilkan 0 atau 1 setelah sejumlah langkah terbatas adalah verifier untuk L jika memiliki properti berikut.

• Mengingat ( w , c ), V output 1 hanya jika w ∈ L .
• Untuk setiap w ∈ L , ada c ∈ Σ ^＊ sehingga V ( w , c ) = 1.

Huruf c dalam definisi di atas disebut sebagai saksi (atau sertifikat ).

Sebuah verifier diperbolehkan untuk memberikan negatif palsu karena kesaksian yang salah bahkan jika w sebenarnya di L . Namun, itu tidak diizinkan untuk memberikan positif palsu. Diperlukan juga bahwa untuk setiap kata dalam bahasa, setidaknya ada satu saksi.

Untuk bahasa KOMPOSIT, yang berisi penyandian desimal dari semua bilangan bulat yang tidak prima, saksi bisa menjadi faktorisasi. Sebagai contoh, (659, 709)adalah saksi untuk 467231∈ COMPOSITE. Anda dapat dengan mudah memverifikasi bahwa pada selembar kertas sementara tanpa saksi yang diberikan, membuktikan bahwa 467231 tidak prima akan sulit tanpa menggunakan komputer.

Kami tidak mengatakan apa-apa tentang bagaimana saksi yang tepat dapat ditemukan. Ini adalah bagian non-deterministik.

Kelas NP berisi semua bahasa L yang memiliki mesin Turing V yang memverifikasi L dan konstanta k ∈ N sehingga untuk setiap input ( w , c ), V berhenti setelah paling banyak langkah T (| w |) untuk fungsi. T ∈ O ( n ↦ n ^k ).

Perhatikan bahwa definisi di atas menyiratkan bahwa untuk setiap w ∈ L ada saksi c dengan | c | ≤ T (| w |). (Mesin Turing tidak mungkin melihat lebih banyak simbol saksi.)

NP adalah superset dari P (mengapa?). Hal ini tidak diketahui apakah di sana ada bahasa yang ada di NP tetapi tidak di P .

Faktorisasi bilangan bulat bukan bahasa semata. Namun, kami dapat membuat bahasa yang mewakili masalah keputusan yang terkait dengannya. Yaitu, bahasa yang berisi semua tupel ( n , m ) sedemikian rupa sehingga n memiliki faktor d dengan d ≤ m . Mari kita sebut FAKTOR bahasa ini. Jika Anda memiliki algoritme untuk memutuskan FACTOR, ia dapat digunakan untuk menghitung faktorisasi penuh dengan hanya overhead polinomial dengan melakukan pencarian biner rekursif untuk setiap faktor utama.

Mudah untuk menunjukkan bahwa FACTOR ada di NP . Seorang saksi yang tepat hanya akan menjadi faktor d itu sendiri dan semua verifier harus lakukan adalah memverifikasi bahwa d ≤ m dan n mod d = 0. Semua ini dapat dilakukan dalam waktu polinomial. (Ingat, sekali lagi, bahwa panjang encoding yang diperhitungkan dan yang logaritmik dalam n .)

Jika Anda dapat menunjukkan bahwa FACTOR juga ada di P , Anda pasti bisa mendapatkan banyak penghargaan keren. (Dan Anda telah merusak sebagian besar kriptografi hari ini.)

Untuk setiap bahasa dalam NP , ada algoritma brute-force yang memutuskannya secara deterministik. Ini hanya melakukan pencarian menyeluruh atas semua saksi. (Perhatikan bahwa panjang maksimum saksi dibatasi oleh polinomial.) Jadi, algoritme Anda untuk menentukan PRIMES sebenarnya adalah algoritme brute force untuk memutuskan COMPOSITE.

Untuk menjawab pertanyaan terakhir Anda, kami perlu memperkenalkan reduksi . Pengurangan adalah konsep yang sangat kuat dari ilmu komputer teoritis. Mengurangi satu masalah ke masalah lain pada dasarnya berarti menyelesaikan satu masalah dengan cara memecahkan masalah lain.

Biarkan Σ menjadi alfabet dan A dan B menjadi bahasa lebih dari Σ . A adalah polinomial-waktu banyak-satu dapat direduksi menjadi B jika ada fungsi f : Σ ^＊ → Σ ^＊ dengan properti berikut.

• w ∈ A   ⇔   f ( w ) ∈ B   untuk semua w ∈ Σ ^＊ .
• Fungsi f dapat dihitung dengan mesin Turing untuk setiap input w dalam sejumlah langkah yang dibatasi oleh polinomial dalam | w |.

Dalam hal ini, kita menulis A ≤ _p B .

Sebagai contoh, misalkan A menjadi bahasa yang berisi semua grafik (dikodekan sebagai adjacency matrix) yang berisi segitiga. (Segitiga adalah siklus panjang 3.) Biarkan B menjadi bahasa yang berisi semua matriks dengan jejak tidak nol. (The jejak matriks adalah jumlah dari elemen-elemen diagonal utamanya.) Lalu A adalah polinomial-waktu banyak-satu direduksi menjadi B . Untuk membuktikan ini, kita perlu menemukan fungsi transformasi yang sesuai f . Dalam hal ini, kita dapat mengatur f untuk menghitung 3 ^rd kekuatan matriks adjacency. Ini membutuhkan dua produk matriks-matriks, yang masing-masing memiliki kompleksitas polinomial.

Hal ini sepele benar bahwa L ≤ _p L . (Bisakah Anda membuktikannya secara formal?)

Kami akan menerapkan ini untuk NP sekarang.

Bahasa L adalah NP -Beras jika dan hanya jika L '≤ _p L untuk setiap bahasa L ' ∈ NP .

Sebuah NP bahasa -Hard mungkin atau mungkin tidak dalam NP itu sendiri.

Bahasa L adalah NP -lengkap jika dan hanya jika

• L ∈ NP dan
• L adalah NP -hard.

Bahasa NP- lengkap yang paling terkenal adalah SAT. Ini berisi semua formula boolean yang dapat dipenuhi. Misalnya, ( a ∨ b ) ∧ (¬ a ∨ ¬ b ) ∈ SAT. Saksi yang valid adalah { a = 1, b = 0}. Rumus ( a ∨ b ) ∧ (¬ a ∨ b ) ∧ ¬ b ∉ SAT. (Bagaimana Anda membuktikan itu?)

Tidak sulit untuk menunjukkan bahwa SAT ∈ NP . Untuk menunjukkan NP -Kesulitan SAT adalah beberapa pekerjaan tetapi dilakukan pada tahun 1971 oleh Stephen Cook .

Setelah satu bahasa NP- lengkap diketahui, itu relatif sederhana untuk menunjukkan NP - kelengkapan bahasa lain melalui reduksi. Jika bahasa A dikenal sebagai NP -hard, maka menunjukkan bahwa A ≤ _p B menunjukkan bahwa B juga NP -hard (melalui transitivitas “≤ _p ”). Pada tahun 1972 Richard Karp menerbitkan daftar 21 bahasa yang bisa dia tampilkan adalah NP-lengkap melalui pengurangan (transitif) SAT. (Ini adalah satu-satunya makalah dalam jawaban ini yang saya benar-benar merekomendasikan Anda harus membaca. Berbeda dengan yang lain, tidak sulit untuk memahami dan memberikan ide yang sangat bagus tentang bagaimana membuktikan kelengkapan NP melalui pengurangan bekerja.)

Akhirnya, ringkasan singkat. Kami akan menggunakan simbol NPH dan NPC untuk menunjukkan masing-masing kelas NP-bahasa kasar dan NP- lengkap.

• P ⊆ NP
• NPC ⊂ NP dan NPC ⊂ NPH , sebenarnya NPC = NP ∩ NPH menurut definisi
• ( A ∈ NP ) ∧ ( B ∈ NPH ) ⇒   A ≤ _p B

Perhatikan bahwa inklusi NPC ⊂ NP layak bahkan dalam kasus P = NP . Untuk melihat ini, jelaskan bahwa tidak ada bahasa non-sepele yang dapat direduksi menjadi bahasa sepele dan ada bahasa sepele di P serta bahasa non-sepele di NP . Ini adalah kasus sudut (tidak terlalu menarik).

Tambahan

Sumber utama kebingungan Anda tampaknya adalah Anda memikirkan " n " di " O ( n ↦ f ( n ))" sebagai interpretasi input suatu algoritma ketika sebenarnya mengacu pada panjang input. Ini adalah perbedaan penting karena itu berarti bahwa kompleksitas suatu algoritma asimptotik tergantung pada pengkodean yang digunakan untuk input.

Minggu ini, rekor baru untuk prime Mersenne terbesar yang diketahui tercapai. Angka prima terbesar yang diketahui saat ini adalah 2 ^{74 207 281} - 1. Angka ini sangat besar sehingga membuat saya sakit kepala jadi saya akan menggunakan yang lebih kecil dalam contoh berikut: 2 ³¹ - 1 = 2 147 483 647. Angka ini dapat dikodekan dengan cara yang berbeda.

• oleh eksponen Mersenne-nya sebagai angka desimal: 31(2 byte)
• sebagai angka desimal: 2147483647(10 byte)
• sebagai nomor unary: di 11111…11mana …akan diganti dengan 2 147 483 640 lebih banyak 1(hampir 2 GiB)

Semua string ini menyandikan nomor yang sama dan memberikan salah satu dari ini, kita dapat dengan mudah membangun penyandian lain dari nomor yang sama. (Anda dapat mengganti penyandian desimal dengan biner, oktal atau heksadesimal jika Anda mau. Ini hanya mengubah panjangnya dengan faktor konstan.)

Algoritma naif untuk menguji primality hanya polinomial untuk pengkodean unary. Uji primality AKS bersifat polinomial untuk desimal (atau basis lainnya b ≥ 2). The Lucas-Lehmer tes primality adalah yang terbaik algoritma dikenal Mersenne prima M _p dengan p prima ganjil tetapi masih eksponensial dalam panjang pengkodean biner dari Mersenne eksponen p (polinomial dalam p ).

Jika kita ingin berbicara tentang kompleksitas suatu algoritma, sangat penting bahwa kita sangat jelas representasi apa yang kita gunakan. Secara umum, dapat diasumsikan bahwa pengkodean yang paling efisien digunakan. Yaitu, biner untuk bilangan bulat. (Perhatikan bahwa tidak setiap bilangan prima adalah bilangan prima Mersenne sehingga menggunakan eksponen Mersenne bukanlah skema penyandian umum.)

Dalam kriptografi teoritis, banyak algoritma secara resmi lulus string sama sekali tidak berguna dari k 1 sebagai parameter pertama. Algoritme tidak pernah melihat parameter ini tetapi memungkinkan untuk secara formal menjadi polinomial dalam k , yang merupakan parameter keamanan yang digunakan untuk menyempurnakan keamanan prosedur.

Untuk beberapa masalah yang bahasa keputusannya dalam pengkodean biner adalah NP -complete, bahasa keputusan tidak lagi NP -complete jika pengkodean angka yang disematkan dialihkan ke unary. Bahasa keputusan untuk masalah lain tetap NP- lengkap bahkan saat itu. Yang terakhir disebut sangat NP- lengkap . Contoh paling terkenal adalah kemasan bin .

Ini juga (dan mungkin lebih) menarik untuk melihat bagaimana kompleksitas suatu algoritma berubah jika input dikompresi . Sebagai contoh bilangan prima Mersenne, kita telah melihat tiga pengkodean, yang masing-masing secara logaritma lebih terkompresi daripada pendahulunya.

Pada tahun 1983, Hana Galperin dan Avi Wigderson telah menulis makalah yang menarik tentang kompleksitas algoritma grafik yang umum ketika pengkodean input grafik dikompresi secara logaritmik. Untuk input ini, bahasa grafik yang mengandung segitiga dari atas (di mana itu jelas dalam P ) tiba-tiba menjadi NP -complete.

Dan itu karena kelas bahasa seperti P dan NP didefinisikan untuk bahasa , bukan untuk masalah .

Saya akan mencoba memberi Anda definisi yang kurang informal untuk hal yang sama.

Masalah P: masalah yang bisa diselesaikan dalam waktu polinomial. Berisi masalah yang bisa dipecahkan secara efisien.

Masalah NP: masalah yang dapat diverifikasi dalam waktu polinomial. Misalnya: Travelling salesman, mendesain sirkuit. Masalah NP adalah jenis puzzle seperti (seperti sudoku). Diberikan solusi yang tepat untuk masalah tersebut, kami dapat memeriksa solusi kami dengan sangat cepat, tetapi jika kami benar-benar mencoba menyelesaikannya, itu mungkin akan berlangsung selamanya.

Sekarang, P vs NP benar-benar bertanya apakah masalah yang solusinya dapat dengan cepat diperiksa benar, maka selalu ada cara cepat untuk menyelesaikannya. Jadi menulis dalam istilah matematika: apakah NP bagian dari P atau tidak?

Sekarang kembali ke NP lengkap: ini adalah masalah yang sangat sulit dari masalah NP. Oleh karena itu jika ada cara yang lebih cepat untuk menyelesaikan NP lengkap maka NP selesai menjadi P dan masalah NP runtuh menjadi P.

NP hard: masalah yang bahkan tidak bisa diperiksa dalam waktu polinomial np sulit. Misalnya, memilih langkah terbaik dalam catur adalah salah satunya.

Jika ada sesuatu yang tidak jelas, coba tonton video ini: https://www.youtube.com/watch?v=YX40hbAHx3s

Saya harap ini akan memberikan kontur buram.