Apa definisi dari P, NP, NP-complete dan NP-hard?


249

Saya dalam kursus tentang komputasi dan kompleksitas , dan saya tidak dapat memahami apa arti istilah-istilah ini.

Yang saya tahu adalah bahwa NP adalah subset dari NP-complete, yang merupakan subset dari NP-hard, tapi saya tidak tahu apa yang sebenarnya mereka maksud. Wikipedia juga tidak banyak membantu, karena penjelasannya masih terlalu tinggi.


6
Ini adalah objek formal dengan definisi formal. Saya telah menemukan sebagian besar penjelasan "sederhana" kurang. Jika Anda memiliki masalah dalam memahami definisi, apa yang Anda lakukan di kelas tentang teori kompleksitas? (Pertanyaan serius.) Ngomong-ngomong, Wikipedia bukanlah referensi yang sangat baik untuk TCS.
Raphael

17
Tidak semua yang Anda tahu benar: NPC (NP selesai) adalah subset dari NP, bukan sebaliknya. Kelengkapan selalu termasuk menjadi elemen kelas yang menjadi masalah. Selain itu NP bukan bagian dari NP-hard, karena tidak setiap masalah dalam NP sulit.
frafl

5
@frafl: "tidak semua masalah di NP sulit" - yang masih harus ditampilkan.
Raphael

3
@ Raphael: Itu sebenarnya tergantung pada jenis pengurangan yang Anda gunakan. Saya memikirkan banyak waktu pengurangan satu polinomial, di mana . ??NPC
frafl

Jawaban:


366

Saya pikir artikel Wikipedia , , dan vs. cukup bagus. Masih di sini adalah apa yang akan saya katakan: Bagian I , Bagian IIPNPPNP

[Saya akan menggunakan komentar di dalam tanda kurung untuk membahas beberapa detail teknis yang dapat Anda lewati jika Anda mau.]


Bagian I

Masalah Keputusan

Ada berbagai macam masalah komputasi. Namun dalam pengantar kursus teori kompleksitas komputasi lebih mudah untuk fokus pada masalah keputusan , yaitu masalah di mana jawabannya adalah YA atau TIDAK. Ada jenis lain dari masalah komputasi tetapi sebagian besar waktu pertanyaan tentang mereka dapat direduksi menjadi pertanyaan serupa tentang masalah keputusan. Apalagi masalah keputusan sangat sederhana. Oleh karena itu dalam pengantar kursus teori kompleksitas komputasi kami memfokuskan perhatian kami pada studi masalah keputusan.

Kami dapat mengidentifikasi masalah keputusan dengan subset input yang memiliki jawaban YA. Ini menyederhanakan notasi dan memungkinkan kita untuk menulis di tempat dan di tempat .xQQ(x)=YESx?QQ(x)=NO

Perspektif lain adalah bahwa kita berbicara tentang permintaan keanggotaan dalam suatu set. Berikut ini sebuah contoh:

Masalah Keputusan:

Input: Bilangan alami , Pertanyaan: Apakah bilangan genap?x
x

Masalah Keanggotaan:

Input: alami , Pertanyaan: Apakah dalam ?x
xEven={0,2,4,6,?}

Kami merujuk pada jawaban YA pada input sebagai menerima input dan untuk TIDAK menjawab pada input sebagai menolak input.

Kami akan melihat algoritma untuk masalah keputusan dan membahas seberapa efisien algoritma tersebut dalam penggunaan sumber daya yang dapat dihitung . Saya akan mengandalkan intuisi Anda dari pemrograman dalam bahasa seperti C untuk mendefinisikan secara formal apa yang kami maksud dengan algoritma dan sumber daya komputasi.

[Keterangan: 1. Jika kami ingin melakukan semuanya secara formal dan tepat, kami perlu memperbaiki model komputasi seperti model mesin Turing standar untuk secara tepat mendefinisikan apa yang kami maksudkan dengan suatu algoritma dan penggunaan sumber daya komputasinya. 2. Jika kita ingin berbicara tentang perhitungan objek yang tidak dapat ditangani secara langsung oleh model, kita perlu mengkodekannya sebagai objek yang dapat ditangani oleh model mesin, misalnya jika kita menggunakan mesin Turing, kita perlu menyandikan objek seperti bilangan dan grafik alami sebagai string biner.]


P = Masalah dengan Algoritma Efisien untukMenemukanSolusi

Asumsikan bahwa algoritma yang efisien berarti algoritma yang menggunakan sumber daya komputasi paling banyak jumlahnya . Sumber daya utama yang kami pedulikan adalah waktu berjalan terburuk dari algoritma sehubungan dengan ukuran input, yaitu jumlah langkah dasar algoritma mengambil input ukuran n . Ukuran input x adalah n jika dibutuhkan n bit memori komputer untuk menyimpan x , dalam hal ini kita menulis |x|=n . Jadi dengan algoritma yang efisien yang kami maksud adalah algoritma yang memiliki waktu menjalankan kasus terburuk polinomial .

The asumsi bahwa algoritma polinomial-waktu menangkap gagasan intuitif algoritma efisien dikenal sebagai tesis Cobham ini . Saya tidak akan membahas pada titik ini apakah P adalah model yang tepat untuk masalah yang dapat dipecahkan secara efisien dan apakah P menangkap atau tidak menangkap apa yang dapat dihitung secara efisien dalam praktik dan masalah terkait. Untuk saat ini ada alasan bagus untuk membuat asumsi ini, jadi untuk tujuan kami, kami menganggap inilah masalahnya. Jika Anda tidak menerima tesis Cobham, itu tidak membuat apa yang saya tulis salah di bawah ini, satu-satunya hal yang akan hilang adalah intuisi tentang perhitungan efisien dalam praktiknya. Saya pikir ini adalah asumsi yang membantu bagi seseorang yang mulai belajar tentang teori kompleksitas.

P adalah kelas masalah keputusan yang dapat diselesaikan secara efisien,
yaitu masalah keputusan yang memiliki algoritma polinomial-waktu.

Secara lebih formal, kami katakan masalah keputusan Q ada di P iff

ada algoritma A efisien sehingga
untuk semua input x ,

  • jika Q(x)=YES maka A(x)=YES ,
  • jika Q(x)=NO maka A(x)=NO .

Aku hanya bisa menulis A(x)=Q(x) tapi saya menulis seperti ini sehingga kita dapat membandingkannya dengan definisi NP .


NP = Masalah dengan Algoritma Efisien untukMemverifikasiBukti / Sertifikat / Saksi

Kadang-kadang kita tidak tahu cara yang efisien untuk menemukan jawaban untuk masalah keputusan, namun jika seseorang memberi tahu kita jawabannya dan memberi kita bukti, kita dapat memverifikasi secara efisien bahwa jawabannya benar dengan memeriksa bukti untuk melihat apakah itu adalah bukti yang valid . Ini adalah ide di balik kompleksitas kelas NP .

Jika buktinya terlalu lama, itu tidak benar-benar berguna, mungkin butuh waktu terlalu lama untuk hanya membaca buktinya apalagi memeriksa apakah itu valid. Kami ingin waktu yang diperlukan untuk verifikasi masuk akal dalam ukuran input asli, bukan ukuran bukti yang diberikan! Ini berarti apa yang kita inginkan bukanlah bukti panjang yang sewenang-wenang tetapi bukti singkat . Perhatikan bahwa jika waktu menjalankan verifier adalah polinomial dalam ukuran input asli maka hanya dapat membaca bagian polinomial dari bukti. Jadi singkatnya yang kami maksud adalah ukuran polinom .

Bentuk poin ini setiap kali saya menggunakan kata "bukti" yang saya maksudkan "bukti singkat".

Berikut adalah contoh masalah yang kami tidak tahu bagaimana menyelesaikannya secara efisien tetapi kami dapat memverifikasi bukti dengan efisien:


Input Partisi : himpunan bilangan asli S ,
pertanyaan: apakah mungkin untuk mempartisi S menjadi dua set A dan B ( AB=S dan AB=? )
sedemikian sehingga jumlah angka dalam A sama dengan jumlah angka dalam B ( xAx=xBx )?

Jika saya memberi Anda S dan bertanya apakah kami dapat mempartisi menjadi dua set sehingga jumlahnya sama, Anda tidak tahu algoritma yang efisien untuk menyelesaikannya. Anda mungkin akan mencoba semua cara yang mungkin untuk mempartisi angka menjadi dua set sampai Anda menemukan partisi di mana jumlahnya sama atau sampai Anda telah mencoba semua partisi yang mungkin dan tidak ada yang berhasil. Jika ada dari mereka yang bekerja, Anda akan mengatakan YA, jika tidak, Anda akan mengatakan TIDAK.

Tetapi ada banyak partisi yang mungkin secara eksponensial sehingga akan membutuhkan banyak waktu. Namun jika saya memberikan dua set A dan B , Anda dapat dengan mudah memeriksa apakah jumlah yang sama dan jika A dan B adalah partisi dari S . Perhatikan bahwa kita dapat menghitung jumlah secara efisien.

Di sini pasangan A dan B yang saya berikan kepada Anda adalah bukti untuk jawaban YA. Anda dapat memverifikasi klaim saya secara efisien dengan melihat bukti saya dan memeriksa apakah itu bukti yang valid . Jika jawabannya YA maka ada bukti yang valid, dan saya bisa memberikannya kepada Anda dan Anda dapat memverifikasinya secara efisien. Jika jawabannya TIDAK maka tidak ada bukti yang valid. Jadi, apa pun yang saya berikan, Anda dapat memeriksa dan melihatnya bukan bukti yang valid. Saya tidak bisa menipu Anda dengan bukti yang tidak valid bahwa jawabannya adalah YA. Ingatlah bahwa jika buktinya terlalu besar maka akan membutuhkan banyak waktu untuk memverifikasinya, kami tidak ingin ini terjadi, jadi kami hanya peduli dengan bukti yang efisien , yaitu bukti yang memiliki ukuran polinomial.

Terkadang orang menggunakan " sertifikat " atau " saksi " sebagai ganti "bukti".

Catatan Saya memberi Anda informasi yang cukup tentang jawaban untuk input yang diberikan x sehingga Anda dapat menemukan dan memverifikasi jawaban secara efisien. Misalnya, dalam contoh partisi kami saya tidak memberi tahu Anda jawabannya, saya hanya memberi Anda partisi, dan Anda dapat memeriksa apakah itu valid atau tidak. Perhatikan bahwa Anda harus memverifikasi sendiri jawabannya, Anda tidak dapat mempercayai saya tentang apa yang saya katakan. Selain itu Anda hanya dapat memeriksa kebenaran bukti saya . Jika bukti saya valid itu artinya jawabannya adalah YA. Tetapi jika bukti saya tidak valid itu tidak berarti jawabannya TIDAK. Anda telah melihat bahwa satu bukti tidak valid, bukan berarti tidak ada bukti yang valid. Kami berbicara tentang bukti untuk YA. Kami tidak berbicara tentang bukti untuk TIDAK.

Mari kita lihat sebuah contoh: A={2,4} dan B={1,5} adalah bukti bahwa S={1,2,4,5} dapat dipartisi menjadi dua set dengan jumlah yang sama. Kita hanya perlu untuk meringkas angka dalam A dan angka dalam B dan lihat apakah hasilnya sama, dan memeriksa apakah A , B adalah partisi dari S .

Jika saya memberi Anda A={2,5} dan B={1,4} , Anda akan memeriksa dan melihat bahwa bukti saya tidak valid. Itu tidak berarti jawabannya adalah TIDAK, itu hanya berarti bahwa bukti khusus ini tidak valid. Tugas Anda di sini bukan untuk menemukan jawabannya, tetapi hanya untuk memeriksa apakah bukti yang Anda berikan valid.

Ini seperti seorang siswa yang memecahkan pertanyaan dalam ujian dan seorang profesor memeriksa apakah jawabannya benar. :) (sayangnya sering siswa tidak memberikan informasi yang cukup untuk memverifikasi kebenaran jawaban mereka dan para profesor harus menebak sisa jawaban parsial mereka dan memutuskan berapa banyak tanda yang harus mereka berikan kepada siswa untuk jawaban parsial mereka, memang cukup sulit tugas).

Yang luar biasa adalah bahwa situasi yang sama berlaku untuk banyak masalah alam lain yang ingin kita selesaikan: kita dapat memverifikasi secara efisien jika bukti singkat yang diberikan valid, tetapi kita tidak tahu cara efisien untuk menemukan jawabannya . Ini adalah motivasi mengapa kelas kompleksitas NP adalah sangat menarik (meskipun ini bukan motivasi asli untuk mendefinisikan itu). Apa pun yang Anda lakukan (tidak hanya dalam CS, tetapi juga dalam matematika, biologi, fisika, kimia, ekonomi, manajemen, sosiologi, bisnis, ...) Anda akan menghadapi masalah komputasi yang termasuk dalam kelas ini. Untuk mendapatkan ide dari berapa banyak masalah berubah menjadi di NP check out ringkasan masalah optimasi NP . Memang Anda akan memiliki waktu sulit menemukan masalah alam yang tidak dalam NP . Sangat menakjubkan.

NP adalah kelas masalah yang memiliki pengukur efisien, yaitu
ada algoritma waktu polinomial yang dapat memverifikasi jika solusi yang diberikan benar.

Lebih formal, kami katakan masalah keputusan Q ada di NP iff

ada algoritma V efisien yang disebut verifier sehingga
untuk semua input x ,

  • jika Q(x)=YES maka ada bukti y sedemikian rupa sehingga V(x,y)=YES ,
  • jika Q(x)=NO maka untuk semua bukti y , V(x,y)=NO .

Kami mengatakan verifier baik jika tidak menerima bukti ketika jawabannya TIDAK. Dengan kata lain, penguji suara tidak bisa diakali untuk menerima bukti jika jawabannya benar-benar TIDAK. Tidak ada positif palsu.

Demikian pula, kami mengatakan verifier lengkap jika menerima setidaknya satu bukti ketika jawabannya adalah YA. Dengan kata lain, pemverifikasi lengkap dapat diyakinkan bahwa jawabannya YA.

Terminologi berasal dari sistem logika dan bukti . Kami tidak dapat menggunakan sistem bukti suara untuk membuktikan pernyataan yang salah. Kita dapat menggunakan sistem bukti lengkap untuk membuktikan semua pernyataan yang benar.

Verifier V mendapat dua input,

  • x : input asli untukQ , dan
  • y : bukti disarankan untukQ(x)=YES .

Perhatikan bahwa kita ingin V menjadi efisien dalam ukuran x . Jika y adalah bukti besar, verifier akan dapat membaca hanya bagian polinomial dari y . Itu sebabnya kami membutuhkan bukti yang singkat. Jika y pendek mengatakan bahwa V efisien dalam x sama dengan mengatakan bahwa V efisien dalam x dan y (karena ukuran y dibatasi oleh polinom tetap pada ukuran x ).

Singkatnya, untuk menunjukkan bahwa masalah keputusan Q adalah dalam NP kita harus memberikan algoritma verifikasi efisien yang baik dan lengkap .

Catatan sejarah: historis ini bukan definisi asli dari NP . Definisi asli menggunakan apa yang disebut mesin Turing non-deterministik . Mesin-mesin ini tidak sesuai dengan model mesin yang sebenarnya dan sulit untuk terbiasa (setidaknya ketika Anda mulai belajar tentang teori kompleksitas). Saya telah membaca bahwa banyak ahli berpikir bahwa mereka akan menggunakan definisi verifier sebagai definisi utama dan bahkan akan menamai kelas VP (untuk diverifikasi dalam polinomial-waktu) sebagai pengganti NP jika mereka kembali ke fajar teori kompleksitas komputasi. Definisi verifier lebih alami, lebih mudah untuk memahami secara konseptual, dan lebih mudah digunakan untuk menunjukkan masalah dalam NP .


P?NP

Oleh karena itu kami memiliki P = efisien dapat dipecahkan dan NP = efisien diverifikasi . Jadi P=NP iff masalah yang dapat diverifikasi secara efisien adalah sama dengan masalah yang dapat diselesaikan secara efisien.

Perhatikan bahwa masalah apa pun dalam P juga dalam NP , yaitu jika Anda dapat memecahkan masalah, Anda juga dapat memverifikasi apakah bukti yang diberikan benar: pemverifikasi akan mengabaikan buktinya!

Itu karena kita tidak membutuhkannya, pemverifikasi dapat menghitung sendiri jawabannya, dapat memutuskan apakah jawabannya YA atau TIDAK tanpa bantuan. Jika jawabannya TIDAK, kita tahu seharusnya tidak ada bukti dan pemverifikasi kami akan menolak setiap bukti yang disarankan. Jika jawabannya adalah YA, harus ada suatu bukti, dan pada kenyataannya kita hanya akan menerima apa pun sebagai bukti.

[Kami dapat membuat verifikator kami menerima hanya beberapa dari mereka, itu juga baik-baik saja, selama verifier kami menerima setidaknya satu bukti verifier bekerja dengan benar untuk masalah tersebut.]

Berikut ini sebuah contoh:

Jumlah
Input: daftar n+1 bilangan asli Sebuah1,?,Sebuahn , dan s ,
Pertanyaan: apakah Σsaya=1nSebuahsaya=s ?

Masalahnya adalah dalam P karena kita dapat merangkum angka-angka dan kemudian membandingkannya dengan s , kita mengembalikan YA jika mereka sama, dan TIDAK jika mereka tidak.

Masalahnya juga di NP . Pertimbangkan verifier V yang mendapat bukti plus input untuk Sum. Kerjanya dengan cara yang sama seperti algoritma dalam P yang kami jelaskan di atas. Ini adalah verifikasi efisien untuk Sum.

Perhatikan bahwa ada pengukur efisien lainnya untuk Sum, dan beberapa di antaranya mungkin menggunakan bukti yang diberikan kepada mereka. Namun yang kami desain tidak dan itu juga bagus. Karena kita memberikan verifier yang efisien untuk Sum masalahnya adalah di NP . Trik yang sama bekerja untuk semua masalah lain di P sehingga P?NP .


Algoritma Brute-Force / Exhaustive-Search untuk NP dan NP?ExhalTsayame

Algoritma terbaik yang kami ketahui untuk menyelesaikan masalah arbitrer di NP adalah algoritma brute-force / exhaustive-search . Pilih verifier yang efisien untuk masalah (itu memiliki verifier yang efisien dengan asumsi kami bahwa itu dalam NP ) dan periksa semua bukti yang mungkin satu per satu. Jika verifikasi menerima salah satu dari mereka maka jawabannya adalah YA. Kalau tidak, jawabannya adalah TIDAK.

Dalam contoh partisi kami, kami mencoba semua partisi yang mungkin dan memeriksa apakah jumlahnya sama di salah satu dari mereka.

Perhatikan bahwa algoritma brute-force berjalan dalam waktu eksponensial kasus terburuk. Ukuran buktinya adalah polinomial dalam ukuran input. Jika ukuran buktinya adalah m maka ada kemungkinan pembuktian 2m . Memeriksa masing-masing akan memakan waktu polinomial oleh pemverifikasi. Jadi secara total algoritma brute-force membutuhkan waktu yang eksponensial.

Ini menunjukkan bahwa setiap masalah NP dapat diselesaikan dalam waktu eksponensial, yaitu NP?ExhalTsayame . (Selain itu, algoritma brute-force hanya akan menggunakan jumlah ruang polinomial, yaitu NP?PShalSebuahce tapi itu adalah cerita untuk hari lain).

Masalah di NP dapat memiliki algoritma lebih cepat, misalnya masalah di P memiliki algoritma polinomial-waktu. Namun untuk masalah sewenang-wenang di NP kita tidak tahu algoritma yang dapat melakukan jauh lebih baik. Dengan kata lain, jika Anda hanya memberi tahu saya bahwa masalah Anda ada di NP (dan tidak ada yang lain tentang masalah) maka algoritma tercepat yang kami tahu untuk menyelesaikannya membutuhkan waktu yang eksponensial.

Namun itu tidak berarti bahwa tidak ada algoritma yang lebih baik, kami tidak tahu itu . Sejauh yang kita tahu masih mungkin (meskipun dianggap sangat tidak mungkin oleh hampir semua teori kompleksitas) bahwa NP=P dan semua masalah NP dapat diselesaikan dalam waktu polinomial.

Selain itu, beberapa ahli menduga bahwa kita tidak dapat melakukan jauh lebih baik, yaitu ada masalah di NP yang tidak bisa diselesaikan jauh lebih efisien daripada algoritma pencarian brute-force yang mengambil jumlah eksponensial dari waktu. Lihat Hipotesis Waktu Eksponensial untuk informasi lebih lanjut. Tapi ini tidak terbukti, itu hanya dugaan saja . Itu hanya menunjukkan seberapa jauh kita dari menemukan algoritma waktu polinomial untuk sewenang-wenang NP masalah.

Asosiasi ini dengan waktu eksponensial membingungkan beberapa orang: mereka berpikir tidak benar bahwa NP masalah membutuhkan eksponensial-waktu untuk menyelesaikan (atau bahkan lebih buruk tidak ada algoritma untuk mereka sama sekali). Menyatakan bahwa masalah adalah di NP tidak berarti masalah adalah sulit untuk memecahkan, itu hanya berarti bahwa itu adalah mudah untuk memverifikasi, itu adalah batas atas pada kesulitan memecahkan masalah, dan banyak NP masalah yang mudah untuk memecahkan sejak P?NP .

Namun demikian, ada NP masalah yang tampaknya sulit untuk memecahkan. Saya akan kembali ke ini ketika kita membahas NP Kesulitan.


Batas Bawah Tampaknya Sulit Dibuktikan

OK, jadi kita sekarang tahu bahwa ada banyak masalah alam yang ada di NP dan kita tidak tahu cara yang efisien untuk memecahkan mereka dan kami menduga bahwa mereka benar-benar membutuhkan waktu eksponensial untuk memecahkan. Bisakah kita membuktikan ini?

Sayangnya tugas membuktikan batas bawah sangat sulit. Kami bahkan tidak dapat membuktikan bahwa masalah ini memerlukan lebih dari waktu linier ! Apalagi membutuhkan waktu yang eksponensial.

Membuktikan batas bawah linear-waktu agak mudah: algoritma perlu membaca input setelah semua Membuktikan batas bawah super-linier adalah cerita yang sama sekali berbeda. Kita dapat membuktikan batas bawah super-linier dengan lebih banyak pembatasan tentang jenis algoritme yang kami pertimbangkan, misalnya menyortir algoritma menggunakan perbandingan, tetapi kami tidak tahu batas bawah tanpa batasan itu.

Untuk membuktikan batas atas masalah, kita hanya perlu merancang algoritma yang cukup baik. Seringkali diperlukan pengetahuan, pemikiran kreatif, dan bahkan kecerdikan untuk menghasilkan algoritma semacam itu.

Namun tugas ini jauh lebih sederhana dibandingkan dengan membuktikan batas bawah. Kami harus menunjukkan bahwa tidak ada algoritma yang baik . Bukan berarti kita tidak tahu algoritma yang cukup bagus saat ini, tetapi tidak ada algoritma yang baik , bahwa tidak ada yang akan menghasilkan algoritma yang baik . Pikirkan sebentar jika Anda belum pernah melakukannya, bagaimana kami bisa menunjukkan hasil yang tidak mungkin ?

Ini adalah tempat lain di mana orang menjadi bingung. Di sini, "ketidakmungkinan" adalah ketidakmungkinan matematis , artinya bukan kependekan dari kita yang bisa diperbaiki oleh beberapa orang genius di masa depan. Ketika kita mengatakan tidak mungkin, yang kami maksud adalah benar-benar tidak mungkin, tidak mungkin seperti 1=0 . Tidak ada kemajuan ilmiah yang memungkinkan. Itulah yang kami lakukan ketika kami membuktikan batas bawah.

Untuk membuktikan batas bawah, yaitu untuk menunjukkan bahwa masalah memerlukan beberapa jumlah waktu untuk menyelesaikan, berarti bahwa kita harus membuktikan bahwa setiapalgoritma, bahkan yang sangat cerdik yang belum tahu, tidak dapat menyelesaikan masalah lebih cepat. Ada banyak ide cerdas yang kita ketahui (serakah, cocok, pemrograman dinamis, pemrograman linier, pemrograman semidefinit, pemrograman jumlah-kuadrat, dan banyak ide cerdas lainnya) dan masih banyak lagi ide-ide cerdas yang belum kita ketahui. Mengesampingkan satu algoritma atau satu ide khusus untuk mendesain algoritma tidak cukup, kita perlu mengesampingkan semuanya, bahkan yang belum kita ketahui, bahkan yang mungkin belum pernah tahu! Dan seseorang dapat menggabungkan semua ini dalam suatu algoritma, jadi kita perlu mengesampingkan kombinasi mereka juga. Ada beberapa kemajuan yang menunjukkan bahwa beberapa ide tidak bisa memecahkan sulit NPmasalah, misalnya serakah dan ekstensi tidak dapat bekerja, dan ada beberapa pekerjaan yang berkaitan dengan algoritma pemrograman dinamis, dan ada beberapa pekerjaan pada cara-cara tertentu menggunakan pemrograman linier. Tetapi ini bahkan tidak mendekati mengesampingkan ide-ide cerdas yang kita tahu (mencari batas bawah dalam model komputasi terbatas jika Anda tertarik).


Hambatan: Turunkan Bounds Apakah Sulit Buktikan

Di sisi lain, kami memiliki hasil matematika yang disebut penghalang yang mengatakan bahwa bukti batas bawah tidak dapat berupa ini dan itu, dan ini dan itu hampir mencakup semua teknik yang telah kami gunakan untuk membuktikan batas bawah! Faktanya, banyak peneliti yang berhenti bekerja untuk membuktikan batas bawah setelah Alexander Razbarov dan Steven Rudich adalah pembatas bukti alami . Ternyata keberadaan jenis bukti batas bawah tertentu akan menyiratkan ketidakamanan generator nomor pseudorandom kriptografi dan banyak alat kriptografi lainnya.

Saya katakan hampir karena dalam beberapa tahun terakhir telah ada beberapa kemajuan terutama oleh Ryan Williams yang telah mampu secara cerdas menghindari hasil penghalang, masih hasilnya sejauh ini adalah untuk model komputasi yang sangat lemah dan cukup jauh dari mengesampingkan algoritma waktu polinomial umum .

Tapi saya menyimpang. Titik utama saya ingin membuat adalah bahwa membuktikan batas bawah adalah sulit dan kami tidak memiliki batas yang kuat lebih rendah untuk algoritma umum memecahkan NP masalah.

[Di sisi lain, karya Ryan Williams menunjukkan bahwa ada hubungan dekat antara membuktikan batas bawah dan membuktikan batas atas. Lihat ceramahnya di ICM 2014 jika Anda tertarik.]


Pengurangan: Memecahkan Masalah Menggunakan Masalah Lain sebagai Subroutine / Oracle / Black Box

Gagasan pengurangan sangat sederhana: untuk memecahkan masalah, gunakan algoritma untuk masalah lain.

Berikut ini adalah contoh sederhana: anggap kita ingin menghitung jumlah daftar n bilangan alami dan kami memiliki algoritma Skamum yang mengembalikan jumlah dua angka yang diberikan. Bisakah kita menggunakan Skamum untuk menjumlahkan angka dalam daftar? Tentu saja!

Masalah:

Input: daftar n bilangan x1,...,xn ,
Output: kembali saya=1nxsaya .

Algoritma Pengurangan:

  1. s=0
  2. untuk saya dari 1 hingga n
    2.1. s=Skamum(s,xsaya)
  3. kembali s

Di sini kita menggunakan Skamum dalam algoritma kami sebagai subrutin . Perhatikan bahwa kita tidak peduli tentang bagaimana Skamum karya, itu bertindak seperti kotak hitam bagi kita, kita tidak peduli apa yang terjadi di dalam Skamum . Kita sering menyebut subrutin Skamum sebagai oracle . Ini seperti oracle dari Delphi dalam mitologi Yunani, kami mengajukan pertanyaan dan oracle menjawabnya dan kami menggunakan jawabannya.

Inilah dasarnya reduksi: asumsikan bahwa kita memiliki algoritma untuk suatu masalah dan menggunakannya sebagai ramalan untuk menyelesaikan masalah lain. Di sini efisien berarti efisien dengan asumsi bahwa oracle menjawab dalam satuan waktu, yaitu kita menghitung setiap eksekusi oracle satu langkah.

Jika oracle mengembalikan jawaban yang besar kita harus membacanya dan yang dapat memakan waktu, jadi kita harus menghitung waktu yang dibutuhkan kita untuk membaca jawaban yang oracle telah diberikan kepada kita. Demikian pula untuk menulis / mengajukan pertanyaan dari oracle. Tetapi oracle bekerja secara instan, yaitu segera setelah kita mengajukan pertanyaan dari oracle, oracle menuliskan jawaban untuk kita dalam satu unit waktu. Semua pekerjaan yang dilakukan oracle dihitung sebagai satu langkah, tetapi ini tidak termasuk waktu yang diperlukan untuk menulis pertanyaan dan membaca jawabannya.

Karena kita tidak peduli bagaimana oracle bekerja tetapi hanya tentang jawaban yang dikembalikannya kita dapat membuat penyederhanaan dan menganggap oracle sebagai masalah itu sendiri sebagai pengganti algoritma untuk itu. Dengan kata lain, kami tidak peduli jika oracle bukan suatu algoritma, kami tidak peduli bagaimana oracle muncul dengan balasannya.

Sebagai contoh, Skamum dalam pertanyaan di atas adalah fungsi penambahan itu sendiri (bukan algoritma untuk penambahan komputasi).

Kita dapat mengajukan beberapa pertanyaan dari oracle, dan pertanyaan-pertanyaan itu tidak perlu ditentukan sebelumnya: kita dapat mengajukan pertanyaan dan berdasarkan jawaban bahwa oracle kembali, kita melakukan beberapa perhitungan sendiri dan kemudian mengajukan pertanyaan lain berdasarkan jawaban yang kita dapatkan. pertanyaan sebelumnya.

Cara lain untuk memandang ini adalah memikirkannya sebagai perhitungan interaktif . Perhitungan interaktif itu sendiri adalah topik besar sehingga saya tidak akan membahasnya di sini, tapi saya pikir menyebutkan perspektif pengurangan ini bisa membantu.

Algoritma SEBUAH yang menggunakan oracle / kotak hitam HAI biasanya dilambangkan sebagai SEBUAHHAI .

Reduksi yang kita bahas di atas adalah bentuk paling umum dari reduksi dan dikenal sebagai reduksi kotak hitam (alias reduksi oracle , reduksi Turing ).

Lebih formal:

Kita katakan bahwa masalah Q adalah kotak hitam direduksi menjadi masalah HAI dan tulis QTHAI jika
ada algoritma SEBUAH sedemikian rupa sehingga untuk semua input x ,
Q(x)=SEBUAHHAI(x) .

Dengan kata lain jika ada algoritma SEBUAH yang menggunakan oracle HAI sebagai sebuah sub rutin dan memecahkan masalah Q .

Jika algoritma pengurangan kami SEBUAH berjalan dalam waktu polinomial kita menyebutnya polinomial-waktu pengurangan black-box atau hanya pengurangan Masak (untuk menghormati Stephen A. Masak ) dan menulis QTPHAI . (Subskrip T singkatan dari "Turing" untuk menghormati Alan Turing ).

Namun kami mungkin ingin memberikan beberapa batasan pada bagaimana algoritma reduksi berinteraksi dengan oracle. Ada beberapa batasan yang dipelajari tetapi batasan yang paling berguna adalah yang disebut banyak-satu reduksi (alias pemetaan reduksi ).

Idenya di sini adalah bahwa pada input x diberikan , kami melakukan beberapa perhitungan waktu polinomial dan menghasilkan y yang merupakan turunan dari masalah yang dipecahkan oleh oracle. Kami kemudian meminta oracle dan mengembalikan jawaban yang dikembalikan kepada kami. Kami diizinkan untuk mengajukan satu pertanyaan dari oracle dan jawaban oracle adalah apa yang akan dikembalikan.

Lebih formal,

Kami mengatakan bahwa masalah Q banyak-dapat direduksi menjadi masalah HAI dan menulis QmHAI jika
ada algoritma SEBUAH sedemikian rupa sehingga untuk semua input x ,
Q(x)=HAI(SEBUAH(x)) .

Ketika algoritma reduksi waktu polinomial kita menyebutnya polinomial-waktu banyak-satu pengurangan atau hanya pengurangan Karp (untuk menghormati Richard M. Karp ) dan melambangkannya dengan QmPO .

Alasan utama untuk kepentingan dalam pengurangan non-interaktif khusus ini adalah bahwa itu mempertahankan NP masalah: jika ada waktu polinomial banyak-satu pengurangan dari masalah A ke NP masalah B , maka A juga di NP .

Gagasan sederhana reduksi adalah salah satu gagasan paling mendasar dalam teori kompleksitas bersama dengan P , NP , dan NP lengkap (yang akan kita bahas di bawah).


Posting menjadi terlalu panjang dan melebihi batas jawaban (30000 karakter). Saya akan melanjutkan jawabannya di Bagian II .


2
Sehubungan dengan intro Anda, pembaca mungkin tertarik pada masalah optimisasi "NP-complete" dan masalah Keputusan vs masalah "nyata" yang bukan ya-atau-tidak .
Raphael

4
@ Kaveh Itu posting yang luar biasa, terima kasih. Saya memang melakukan decidability sebelum bagian ini di kelas, tapi saya sedikit ketinggalan dalam pemahaman saya tentang pembuktian keraguan. Saya tidak tahu apakah ini ada hubungannya dengan kurangnya pemahaman saya dengan kompleksitas.
agen154

5
Saya telah membaca banyak buku kompleksitas dari tingkat intro (termasuk Sipser) hingga yang lebih maju. Saya tidak punya masalah dengan matematika abstrak (mis. Saya bisa membaca Lang's Aljabar). Jawaban ini adalah yang terbaik untuk menjelaskan NP vs P. Saya menyarankan Anda untuk menghabiskan lebih banyak waktu untuk memolesnya dan membuatnya menjadi catatan kuliah. Ini bisa membantu banyak orang.
scaaahu

@scaaahu, terima kasih atas komentarnya yang baik dan juga atas sarannya. Saya berencana untuk menyelesaikan dan memoles ini segera.
Kaveh

10
Jawaban ini harus dibuat sebagai jawaban referensi. Semua pertanyaan tipe P / NP dasar di masa mendatang harus dirujuk terlebih dahulu. Deskripsi sangat cair!
Paresh

180

Bagian II

Lanjutan dari Bagian I .

Yang sebelumnya melebihi jumlah maksimum huruf yang diizinkan dalam jawaban (30000) jadi saya memecahnya menjadi dua.

kelengkapan:Universal N P ProblemNP NP

OK, sejauh ini kita telah membahas kelas masalah yang dapat dipecahkan secara efisien ( ) dan kelas masalah yang dapat diverifikasi secara efisien ( N P ). Seperti yang kita bahas di atas, keduanya adalah batas atas . Mari kita fokus perhatian kita untuk saat ini pada masalah dalam N P sebagai luar biasa banyak masalah alam berubah menjadi dalam N P .PNPNPNP

Sekarang terkadang kita ingin mengatakan bahwa suatu masalah sulit untuk dipecahkan . Tetapi seperti yang kami sebutkan di atas, kami tidak dapat menggunakan batas bawah untuk tujuan ini: secara teoritis mereka persis apa yang ingin kami buktikan, namun dalam praktiknya kami belum terlalu berhasil dalam membuktikan batas bawah dan pada umumnya mereka sulit untuk dibuktikan seperti yang kami sebutkan. atas. Apakah masih ada cara untuk mengatakan bahwa masalah sulit dipecahkan ?

Di sinilah gagasan -completeness. Tapi sebelum mendefinisikan N P -completeness mari kita melihat lagi pengurangan.NPNP

Pengurangan sebagai Kesulitan Relatif

Kita dapat menganggap batas bawah sebagai kesulitan mutlak masalah. Kemudian kita dapat menganggap pengurangan sebagai kesulitan relatif dari masalah. Kita bisa mengambil sebuah pengurangan dari ke BSEBUAHB mengatakan lebih mudah daripada BSEBUAHB . Ini tersirat dalam gagasan kami gunakan untuk reduksi. Secara formal, pengurangan memberikan perintah parsial pada masalah.

Jika kita dapat secara efisien mengurangi masalah ke masalah lain B maka A seharusnya tidak lebih sulit daripada B untuk dipecahkan. Intuisi adalah sebagai berikut:SEBUAHBSEBUAHB

Mari menjadi pengurangan efisien dari A ke B , yaitu M adalah algoritma yang efisien yang menggunakan B dan memecahkan A . Biarkan N menjadi algoritma yang efisien yang memecahkan B . Kita bisa menggabungkan pengurangan efisien M B dan efisien algoritma N untuk mendapatkan M N yang merupakan algoritma yang efisien yang memecahkan A .M.BSEBUAHBM.BSEBUAHNBM.BNM.NSEBUAH

Ini karena kita dapat menggunakan subrutin yang efisien dalam algoritma yang efisien (di mana setiap panggilan subrutin menghabiskan satu unit waktu) dan hasilnya adalah algoritma yang efisien. Ini adalah properti penutupan yang sangat bagus dari algoritma polinomial-time dan , tidak berlaku untuk banyak kelas kompleksitas lainnya.P

-Lengkap berarti paling sulit N P masalahNPNP

Sekarang bahwa kita memiliki cara relatif membandingkan kesulitan masalah yang kita dapat meminta masalah mana yang paling sulit di antara masalah di ? Kami menyebutnya masalah seperti N P -lengkap .NPNP

masalah -Lengkap yang paling sulit N P masalahNPNP,
jika kita bisa memecahkan masalah -Lengkap efisien, kita bisa menyelesaikan semua N P masalah efisien.NPNP

Secara lebih formal, kami katakan masalah keputusan adalah N P -lengkap iffSEBUAHNP

adalah di N P , dan untuk semua N P masalah B , B adalah polinomial-waktu banyak-satu direduksi menjadi A ( B P m A ).SEBUAHNP
NPBBSEBUAHBmPA

Cara lain untuk berpikir tentang masalah -Lengkap adalah berpikir tentang mereka sebagai versi kompleksitas mesin Turing yang universal . Sebuah N P masalah -Lengkap adalah yang universal antara N P masalah dalam arti yang sama: Anda dapat menggunakannya untuk memecahkan N P masalah.NPNPNPNP

Ini adalah salah satu alasan mengapa pemecah SAT yang baik itu penting, khususnya di industri. SAT adalah -complete (lebih lanjut tentang ini nanti), jadi kita dapat fokus pada merancang algoritma yang sangat baik (sebanyak yang kita bisa) untuk memecahkan SAT. Untuk mengatasi masalah lain di N P kita dapat mengkonversi contoh masalah untuk contoh SAT dan kemudian menggunakan-kualitas industri yang sangat dioptimalkan SAT-solver.NPNP

(Dua masalah lain yang banyak orang kerjakan untuk mengoptimalkan algoritme mereka untuk mereka untuk penggunaan praktis dalam industri adalah Pemrograman Integer dan Masalah Kepuasan Kendala . Tergantung pada masalah Anda dan kejadian yang Anda pedulikan tentang algoritma yang dioptimalkan untuk salah satu dari ini mungkin berkinerja lebih baik daripada lainnya.)

Jika masalah memenuhi kondisi kedua dalam definisi -completeness (yaitu kondisi universalitas) kita sebut masalah N P -Hard .NP
NP

Kekerasan adalah cara untuk mengatakan bahwa masalah itu sulit.NP

Saya pribadi lebih suka menganggap kekerasan sebagai universalitas, jadi mungkin N P- universal bisa menjadi nama yang lebih benar, karena kita tidak tahu saat ini apakah mereka benar-benar keras atau hanya karena kita belum mampu untuk menemukan algoritma waktu polinomial untuk mereka).NPNP

Nama -hard juga membingungkan orang untuk salah berpikir bahwa masalah N P -hard adalah masalah yang benar - benar sulit untuk dipecahkan. Kita tidak tahu yang belum, kita hanya tahu bahwa mereka sesulit apapun N P masalah untuk memecahkan. Meskipun para ahli pikir itu tidak mungkin masih mungkin bahwa semua N P masalah yang mudah dan efisien dipecahkan. Dengan kata lain, menjadi sesulit apapun lainnya N P masalah tidak berarti benar-benar sulit. Itu hanya berlaku jika ada N P masalah yang benar-benarNPNPNPNPNPNP hard (yaitu tidak memiliki algoritma waktu polinomial).

Sekarang pertanyaannya adalah:

  • Apakah ada masalah -complete?NP

  • Apakah kita mengenal mereka?

Saya sudah memberikan jawaban ketika kita membahas SAT-solver. Hal yang mengejutkan adalah bahwa banyak alami masalah berubah menjadi N P -Lengkap (lebih lanjut tentang ini nanti). Jadi jika kita memilih secara acak memilih masalah alam di N P , dengan probabilitas yang sangat tinggi itu adalah baik bahwa kita tahu algoritma polinomial-waktu untuk itu atau yang kita tahu itu adalah N P -Lengkap. Jumlah masalah alami yang tidak diketahui baik cukup kecil (contoh penting adalah bilangan bulat anjak piutang, lihat daftar ini untuk daftar masalah serupa).NPNPNPNP

Sebelum pindah ke contoh masalah -Lengkap, perhatikan bahwa kami dapat memberikan definisi yang sama untuk kelas kompleksitas lain dan mendefinisikan kelas kompleksitas seperti E x p T i m e -Lengkap. Tapi seperti yang saya katakan, N P memiliki tempat yang sangat istimewa: tidak seperti N P kelas kompleksitas lain memiliki beberapa masalah lengkap alami.NPExhalTsayameNPNP

(Masalah alami yang saya maksud adalah masalah yang orang benar-benar pedulikan, bukan masalah yang didefinisikan secara artifisial oleh orang untuk menunjukkan beberapa hal. Kita dapat memodifikasi masalah dengan cara yang pada dasarnya tetap merupakan masalah yang sama, misalnya kita dapat mengubah jawaban untuk input dalam SAT menjadi TIDAK. Kita dapat mendefinisikan banyak masalah berbeda dengan cara yang sama tanpa dasarnya mengubah masalah. Tetapi siapa yang benar-benar peduli dengan masalah buatan ini sendiri?)hal?hal

- Masalah Lengkap: Ada Masalah Universal di N PNPNP

Pertama, perhatikan bahwa jika adalah N P -hard dan A polinomial-waktu banyak-satu berkurang menjadi B maka B juga N P -hard. Kita bisa memecahkan N P masalah dengan menggunakan A dan kita dapat memecahkan A sendiri menggunakan B , sehingga kita dapat memecahkan N P masalah dengan menggunakan B !SEBUAHNPSEBUAHBBNPNPSEBUAHSEBUAHBNPB

Ini adalah lemma yang sangat berguna. Jika kita ingin menunjukkan bahwa masalah adalah -Hard kita harus menunjukkan bahwa kita dapat mengurangi semua N P masalah untuk itu, yang tidak mudah karena kita tahu apa-apa tentang masalah ini selain itu mereka berada di N P .NPNPNP

Pikirkan sebentar. Sungguh menakjubkan saat pertama kali kita melihat ini. Kita dapat membuktikan semua masalah yang direduksi menjadi SAT dan tanpa mengetahui apa-apa tentang masalah-masalah lain selain fakta bahwa mereka berada di N P !NPNP

Untungnya kita tidak perlu melakukan ini lebih dari sekali. Setelah kami menunjukkan masalah seperti adalah N P-sulit untuk masalah lain, kita hanya perlu mengurangi S A T ke mereka. Misalnya, untuk menunjukkan bahwa S u b s e t S u m adalah N P-keras kita hanya perlu memberikan pengurangan dari S A T ke S u b s e t S u m .SSEBUAHTNPSSEBUAHTSkamubsetSkamumNPSSEBUAHTSkamubsetSkamum

OK, mari kita tunjukkan ada masalah -complete.NP

Universal Verifier adalah -completeNP

Catatan: bagian berikut mungkin sedikit teknis pada bacaan pertama.

Contoh pertama agak buatan tapi saya pikir ini lebih sederhana dan berguna untuk intuisi. Ingat definisi verifier . Kami ingin mendefinisikan masalah yang dapat digunakan untuk menyelesaikan semuanya. Jadi mengapa tidak mendefinisikan masalah itu saja?NP


Input Verifier Universal Berbatas Waktu : kode algoritma yang mendapatkan input dan bukti, input x , dan dua angka t dan k . Output: Y E S jika ada bukti ukuran paling banyak k st itu diterima oleh V untuk input x dalam t-langkah , N O jika tidak ada bukti seperti itu.Vxtk
YESkVxtNHAI

Tidak sulit untuk menunjukkan masalah ini yang saya sebut adalah N P -hard:UnsayaVerNP

VNPxVxUnsayaVer
tkVxVx

tttk

NPUnsayaVerNP


M.xM.t
YESM.xYEStNHAIYESt

CPt

sayanterhalreter

UnsayaVerNPM.xtkccksayanterhalreterM.YESxct

SSEBUAHTNP

UnsayaVerNPUnsayaVerNP

NPSSEBUAHT

SSEBUAHT


φ
YESφNHAI

SSEBUAHTNP


Untuk ditulis ...

NP

NP

NP

PNP

Apa berikutnya? Ke mana Harus Pergi Dari Sini?


6
Saya berharap saya bisa lebih memilih sekali, terima kasih telah berusaha keras untuk menjawab!
Fingolfin

2
Wow, artikel yang luar biasa! Saya juga sangat menantikan bagian yang diumumkan, terutama "Apa yang harus dilakukan jika Anda harus menyelesaikan masalah NP-complete?".
Tobias Hermann

5
@ xci13 Anda bisa! Suara positif bagian pertama;)
Vince Emigh

4
Saya membuat akun di sini hanya untuk memilih kedua posting Anda!
ghosts_in_the_code

6
@ Kaveh Apakah ada rencana untuk menyelesaikan artikel yang ditulis dengan luar biasa ini?
Gab

26

Lebih dari jawaban yang disebutkan bermanfaat, saya sangat merekomendasikan Anda untuk menonton " Melampaui Komputasi: Masalah P vs NP " oleh Michael Sipser . Saya pikir video ini harus diarsipkan sebagai salah satu video pengajaran terkemuka dalam ilmu komputer.!

Nikmati!


Menariknya, buku teks saya adalah miliknya. Itu bukan buku yang mengerikan, tetapi meninggalkan beberapa yang diinginkan.
agen154

8

Menyalin jawaban saya ke pertanyaan serupa di Stack Overflow:

Cara termudah untuk menjelaskan Pv. NP dan semacamnya tanpa masuk ke teknis adalah untuk membandingkan "masalah kata" dengan "masalah pilihan ganda".

Ketika Anda mencoba memecahkan "masalah kata", Anda harus menemukan solusinya dari awal. Ketika Anda mencoba untuk memecahkan "masalah pilihan ganda" Anda punya pilihan: pecahkanlah seperti halnya "masalah kata", atau coba masukkan setiap jawaban yang diberikan kepada Anda, dan pilih jawaban kandidat yang cocok.

Sering terjadi bahwa "masalah pilihan ganda" jauh lebih mudah daripada "masalah kata" yang sesuai: mengganti jawaban kandidat dan memeriksa apakah cocok mungkin memerlukan upaya yang jauh lebih sedikit daripada menemukan jawaban yang tepat dari awal.

Sekarang, jika kita akan menyetujui upaya yang memakan waktu polinomial "mudah" maka kelas P akan terdiri dari "masalah kata mudah", dan kelas NP akan terdiri dari "masalah pilihan ganda yang mudah".

Inti dari Pv. NP adalah pertanyaan: "Apakah ada masalah pilihan ganda yang mudah yang tidak semudah masalah kata"? Yaitu, adakah masalah yang mudah untuk memverifikasi validitas jawaban yang diberikan tetapi sulit menemukan jawaban dari awal?

Sekarang kita mengerti secara intuitif apa itu NP, kita harus menantang intuisi kita. Ternyata ada "masalah pilihan ganda" yang, dalam beberapa hal, adalah yang paling sulit dari semuanya: jika seseorang akan menemukan solusi untuk salah satu dari masalah "yang paling sulit dari semuanya", seseorang akan dapat menemukan solusi untuk SEMUA Masalah NP! Ketika Cook menemukan ini 40 tahun yang lalu, itu mengejutkan. Masalah "paling sulit dari semuanya" ini dikenal sebagai NP-hard. Jika Anda menemukan "solusi masalah kata" untuk salah satu dari mereka, Anda akan secara otomatis menemukan "solusi masalah kata" untuk masing-masing dan setiap "masalah pilihan ganda yang mudah"!

Akhirnya, masalah NP-lengkap adalah mereka yang secara bersamaan NP dan NP-keras. Mengikuti analogi kami, mereka secara bersamaan "mudah seperti masalah pilihan ganda" dan "yang paling sulit dari semuanya sebagai masalah kata".


Sekarang kita mengerti secara intuitif apa itu NP, kita harus menantang intuisi kita. Ternyata ada "masalah pilihan ganda" - apakah maksud Anda "masalah kata" di sana? Saya pikir begitu, karena semua masalah NP semudah "pilihan ganda" menurut definisi.
Dmitry Grigoryev

By the line Ternyata ada "masalah pilihan ganda" yang, dalam beberapa hal, adalah yang paling sulit dari semua yang saya maksud. Ternyata ada masalah NP yang, dalam beberapa hal, adalah yang paling sulit dari semuanya . Masalah NP ini memang masalah pilihan ganda yang mudah menurut definisi, tetapi mereka juga paling sulit dari semuanya sebagai masalah kata. Contoh standar adalah SAT3: mudah sebagai masalah pilihan ganda, tetapi sulit sebagai masalah kata.
Michael

7

Yang paling sederhana adalah P, masalah yang dapat dipecahkan dalam waktu polinomial di sini.

Lalu datanglah NP. Masalah dipecahkan dalam waktu polinomial pada mesin Turing non-deterministik termasuk di sini.

Kekerasan dan kelengkapan harus dengan pengurangan. Masalah A sulit untuk kelas C jika setiap masalah dalam C berkurang menjadi A. Jika masalah A sulit untuk NP , atau NP-keras, jika setiap masalah di NP berkurang menjadi A.

Akhirnya, masalah selesai untuk kelas C jika dalam C dan sulit untuk C. Dalam kasus Anda, masalah A selesai untuk NP , atau NP-lengkap, jika setiap masalah di NP dikurangi menjadi A, dan A di NP .

Untuk menambah penjelasan NP, masalah ada di NP jika dan hanya jika solusi dapat diverifikasi dalam waktu polinomial (deterministik). Pertimbangkan masalah NP-complete yang Anda tahu, SAT, KLIIK, SUMU SUBSET, PENUTUP VERTEX, dll. Jika Anda "mendapatkan solusinya", Anda dapat memverifikasi kebenarannya dalam waktu polinomial. Mereka adalah, resp., Penugasan kebenaran untuk variabel, subgraph lengkap, subset angka dan set simpul yang mendominasi semua tepi.


7

Dari video P vs. NP dan Computational Complexity Zoo .

Untuk komputer dengan benar-benar besar versi masalah ...

Masalah P

mudah dipecahkan (rubix cube)

Masalah NP

sulit dipecahkan - tetapi memeriksa jawaban itu mudah (sudoku)

Mungkin ini semua benar-benar masalah P tetapi kita tidak mengetahuinya ... P vs. NP .

NP-lengkap

Banyak masalah NP mendidih ke yang sama (sudoku adalah pendatang baru ke daftar).

Masalah EXP

sangat sulit untuk dipecahkan (mis. langkah terbaik berikutnya dalam catur)

Masalah NP-hard

NP-hard tidak dijelaskan dengan baik dalam video (itu semua bit merah muda di diagram di bawah ini). Diagram NP-hard Euler Wikipedia lebih jelas dalam hal ini.

SVG Euler diagram P, NP, NP-complete, dan NP-hard

Diagram

Seperti yang ditampilkan di dekat akhir video.

Blackboard Euler diagram P, NP, NP-complete, EXP dan NP-hard


2

P , NP , NP-complete dan NP-hard adalah kelas kompleksitas, mengklasifikasikan masalah sesuai dengan kompleksitas algoritmik untuk menyelesaikannya. Singkatnya, mereka didasarkan pada tiga properti:

tabel kelas kompleksitas

Dapat dipecahkan dalam waktu polinomial: Menentukan masalah keputusan yang dapat diselesaikan dengan mesin Turing deterministik (DTM) menggunakan jumlah polinom waktu komputasi, yaitu, waktu berjalannya dibatasi oleh ekspresi polinom dalam ukuran input untuk algoritma. Menggunakan notasi Big-O kompleksitas waktu ini didefinisikan sebagai O(n ^ k), di mana n adalah ukuran input dan koefisien konstanta ka.

Solusi dapat diverifikasi dalam waktu polinomial: Menentukan masalah keputusan yang solusinya dapat diverifikasi oleh DTM menggunakan jumlah waktu komputasi polinomial, meskipun untuk mendapatkan solusi yang tepat mungkin memerlukan jumlah waktu yang lebih tinggi.

Mengurangi masalah NP dalam waktu polinomial : Menentukan masalah keputusan yang algoritmanya untuk menyelesaikannya dapat digunakan untuk menyelesaikan masalah NP apa pun setelah langkah terjemahan polinomial waktu.


Saya baru-baru ini menulis sebuah artikel tentang subjek ini memberikan rincian lebih lanjut, termasuk demonstrasi kode untuk mengurangi masalah NP menjadi masalah NP-keras: Kelas kompleksitas masalah

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