Apakah NP-complete dalam ilmu komputer?

Apa masalah NP-complete? Mengapa topik ini begitu penting dalam ilmu komputer?

NP adalah waktu Polinomial Non-deterministik .

Ini berarti bahwa masalah dapat diselesaikan dalam waktu Polinomial menggunakan mesin Turing Non-deterministik (seperti mesin Turing biasa tetapi juga termasuk fungsi "pilihan" non-deterministik). Pada dasarnya, solusi harus dapat diuji dalam waktu poli. Jika itu masalahnya, dan masalah NP yang diketahui dapat diselesaikan menggunakan masalah yang diberikan dengan input yang dimodifikasi (masalah NP dapat dikurangi menjadi masalah yang diberikan) maka masalahnya adalah NP selesai.

Hal utama yang harus diambil dari masalah NP-complete adalah tidak dapat diselesaikan dalam waktu polinomial dengan cara apa pun yang diketahui. NP-Hard / NP-Complete adalah cara untuk menunjukkan bahwa kelas-kelas masalah tertentu tidak dapat dipecahkan dalam waktu yang realistis.

Sunting: Seperti yang telah dicatat orang lain, seringkali ada solusi perkiraan untuk masalah NP-Complete. Dalam hal ini, solusi perkiraan biasanya memberikan perkiraan pendekatan menggunakan notasi khusus yang memberitahu kita seberapa dekat perkiraan itu.

Apa itu NP ?

NP adalah himpunan semua masalah keputusan (pertanyaan dengan jawaban ya-atau-tidak) yang jawaban 'ya' dapat diverifikasi dalam waktu polinomial (O (n ^k ) di mana n adalah ukuran masalah, dan k adalah konstan) oleh mesin Turing deterministik . Waktu polinomial kadang digunakan sebagai definisi cepat atau cepat .

Apa itu P ?

P adalah himpunan semua masalah keputusan yang dapat diselesaikan dalam waktu polinomial oleh mesin Turing deterministik . Karena mereka dapat diselesaikan dalam waktu polinomial, mereka juga dapat diverifikasi dalam waktu polinomial. Oleh karena itu P adalah bagian dari NP.

Apa itu NP-Complete ?

Masalah x yang ada di NP juga di NP-Complete jika dan hanya jika setiap masalah lain di NP dapat dengan cepat (mis. Dalam waktu polinomial) diubah menjadi x.

Dengan kata lain:

1. x dalam NP, dan
2. Setiap masalah dalam NP dapat direduksi menjadi x

Jadi, apa yang membuat NP-Complete begitu menarik adalah bahwa jika salah satu dari masalah NP-Complete harus diselesaikan dengan cepat, maka semua masalah NP dapat diselesaikan dengan cepat.

Lihat juga pos Apa itu "P = NP?", Dan mengapa ini merupakan pertanyaan yang terkenal?

Apa itu NP-Hard ?

NP-Hard adalah masalah yang setidaknya sama sulitnya dengan masalah tersulit dalam NP. Perhatikan bahwa masalah NP-Complete juga NP-hard. Namun tidak semua masalah NP-hard adalah NP (atau bahkan masalah keputusan), meskipun memiliki NPsebagai awalan. Itu adalah NP dalam NP-hard tidak berarti waktu polinomial non-deterministik . Ya, ini membingungkan, tetapi penggunaannya tertanam dan tidak mungkin berubah.

NP-Complete berarti sesuatu yang sangat spesifik dan Anda harus berhati-hati atau Anda akan mendapatkan definisi yang salah. Pertama, masalah NP adalah masalah ya / tidak

1. Ada bukti polinomial-waktu untuk setiap contoh masalah dengan jawaban "ya" bahwa jawabannya adalah "ya", atau (setara)
2. Ada algoritma waktu polinomial (mungkin menggunakan variabel acak) yang memiliki probabilitas tidak nol untuk menjawab "ya" jika jawaban untuk contoh masalah adalah "ya" dan akan mengatakan "tidak" 100% dari waktu jika jawabannya adalah tidak." Dengan kata lain, algoritma harus memiliki tingkat false-negative kurang dari 100% dan tidak ada false positive.

Masalah X adalah NP-Complete jika

1. X dalam NP, dan
2. Untuk setiap masalah Y dalam NP, ada "reduksi" dari Y ke X: algoritma polinomial-waktu yang mengubah setiap instance dari Y menjadi instance dari X sehingga jawaban untuk instance-Y adalah "ya" jika dan hanya jika jawaban X-instance adalah "ya".

Jika X adalah NP-lengkap dan deterministik, ada algoritma waktu polinomial yang dapat menyelesaikan semua instance X dengan benar (0% false-positive, 0% false-negative), maka setiap masalah dalam NP dapat diselesaikan dalam deterministic-polynomial- waktu (dengan mereduksi menjadi X).

Sejauh ini, tidak ada yang datang dengan algoritma waktu polinomial deterministik seperti itu, tetapi tidak ada yang membuktikan satu tidak ada (ada satu juta dolar untuk siapa saja yang dapat melakukan keduanya: ini adalah masalah P = NP ). Itu tidak berarti bahwa Anda tidak dapat menyelesaikan contoh tertentu dari masalah NP-Complete (atau NP-Hard). Ini hanya berarti Anda tidak dapat memiliki sesuatu yang akan bekerja dengan andal pada semua contoh masalah dengan cara yang sama Anda dapat mengurutkan daftar bilangan bulat. Anda mungkin bisa membuat algoritma yang akan bekerja dengan sangat baik pada semua contoh praktis masalah NP-Hard.

Pada dasarnya masalah dunia ini dapat dikategorikan sebagai

         1) Masalah yang Tidak Dapat Diatasi 2) Masalah yang Dapat Diambil 3) Masalah-NP 4) Masalah-P

         1) Yang pertama adalah tidak ada solusi untuk masalah tersebut. 2) Yang kedua adalah kebutuhan waktu eksponensial (yaitu O (2 ^ n) di atas). 3) Yang ketiga disebut NP. 4) Masalah keempat mudah.

P: merujuk pada solusi masalah Waktu Polinomial.

NP: merujuk Waktu Polinomial belum menemukan solusi. Kami tidak yakin tidak ada solusi Waktu Polinomial, tetapi begitu Anda memberikan solusi, solusi ini dapat diverifikasi dalam Polinomial Time.

NP Complete: merujuk pada Waktu Polinomial kami masih belum menemukan solusi, tetapi dapat diverifikasi dalam Polinomial Time. Masalah NPC dalam NP adalah masalah yang lebih sulit, jadi jika kita dapat membuktikan bahwa kita memiliki solusi P untuk masalah NPC maka masalah NP yang dapat ditemukan dalam solusi P.

NP Hard: merujuk Waktu Polinomial belum menemukan solusi, tetapi pasti tidak dapat diverifikasi dalam Polinomial Time. Masalah NP Sulit melampaui kesulitan NPC.

NP-Complete adalah kelas masalah.

Kelas Pterdiri dari masalah-masalah yang dapat dipecahkan dalam waktu polinomial . Sebagai contoh, mereka dapat diselesaikan dalam O ( ^nk ) untuk beberapa konstanta k, di mana n adalah ukuran input. Sederhananya, Anda dapat menulis sebuah program yang akan berjalan dalam waktu yang wajar .

Kelas NPterdiri dari masalah-masalah yang dapat diverifikasi dalam waktu polinomial. Yaitu, jika kita diberi solusi potensial, maka kita dapat memeriksa apakah solusi yang diberikan benar dalam waktu polinomial.

Beberapa contoh adalah masalah Boolean Satisfiability (atau SAT ), atau masalah siklus Hamiltonian. Ada banyak masalah yang diketahui berada di kelas NP.

NP-Completeberarti masalahnya setidaknya sekeras masalah apa pun dalam NP.

Penting bagi ilmu komputer karena telah terbukti bahwa masalah apa pun dalam NP dapat diubah menjadi masalah lain dalam NP-complete. Itu berarti bahwa solusi untuk setiap masalah NP-complete adalah solusi untuk semua masalah NP.

Banyak algoritma dalam keamanan tergantung pada kenyataan bahwa tidak ada solusi yang dikenal untuk masalah-masalah sulit NP. Ini pasti akan berdampak signifikan pada komputasi jika solusi ditemukan.

Ini adalah kelas masalah di mana kita harus mensimulasikan setiap kemungkinan untuk memastikan kita memiliki solusi optimal.

Ada banyak heuristik yang bagus untuk beberapa masalah NP-Complete, tetapi mereka hanya tebakan paling baik.

Jika Anda mencari contoh masalah NP-complete maka saya sarankan Anda melihat 3-SAT .

Premis dasarnya adalah Anda memiliki ekspresi dalam bentuk konjungtif normal , yang merupakan cara untuk mengatakan Anda memiliki serangkaian ekspresi yang bergabung dengan OR bahwa semuanya harus benar:

(a or b) and (b or !c) and (d or !e or f) ...

Masalah 3-SAT adalah menemukan solusi yang akan memuaskan ekspresi di mana masing-masing ekspresi-OR memiliki tepat 3 boolean untuk dicocokkan:

(a or !b or !c) and (!a or b or !d) and (b or !c or d) ...

Solusi untuk yang ini mungkin (a = T, b = T, c = F, d = F). Namun, tidak ada algoritma yang ditemukan yang akan menyelesaikan masalah ini dalam kasus umum dalam waktu polinomial. Artinya, cara terbaik untuk menyelesaikan masalah ini adalah dengan melakukan tebak-dan-periksa pada dasarnya dan coba kombinasi yang berbeda sampai Anda menemukan yang berfungsi.

Apa yang istimewa tentang masalah 3-SAT adalah bahwa SETIAP masalah NP-complete dapat dikurangi menjadi masalah 3-SAT. Ini berarti bahwa jika Anda dapat menemukan algoritma waktu polinomial untuk menyelesaikan masalah ini maka Anda mendapatkan $ 1.000.000 , belum lagi rasa hormat dan kekaguman dari para ilmuwan komputer dan ahli matematika di seluruh dunia.

Jujur saja, Wikipedia mungkin tempat terbaik untuk mencari jawaban.

Jika NP = P, maka kita dapat memecahkan masalah yang sangat sulit lebih cepat dari yang kita duga sebelumnya. Jika kita menyelesaikan hanya satu masalah NP-Complete dalam waktu P (polinomial), maka itu dapat diterapkan untuk semua masalah lain dalam kategori NP-Complete.

Kita perlu memisahkan algoritma dan masalah. Kami menulis algoritma untuk memecahkan masalah, dan mereka skala dengan cara tertentu. Meskipun ini penyederhanaan, mari beri label algoritma dengan 'P' jika penskalaannya cukup baik, dan 'NP' jika tidak.

Sangat membantu untuk mengetahui hal-hal tentang masalah yang kami coba selesaikan, daripada algoritma yang kami gunakan untuk menyelesaikannya. Jadi kita akan mengatakan bahwa semua masalah yang memiliki algoritma penskalaan baik adalah "dalam P". Dan yang memiliki algoritma penskalaan buruk adalah "dalam NP".

Itu berarti bahwa banyak masalah sederhana "dalam NP" juga, karena kita dapat menulis algoritma yang buruk untuk menyelesaikan masalah yang mudah. Akan lebih baik untuk mengetahui masalah mana dalam NP yang benar-benar rumit, tetapi kami tidak hanya ingin mengatakan "itu adalah masalah yang belum kami temukan algoritma yang bagus untuk". Lagipula, saya bisa menemukan masalah (sebut saja X) yang menurut saya membutuhkan algoritma yang sangat luar biasa. Saya memberi tahu dunia bahwa algoritma terbaik yang dapat saya buat untuk menyelesaikan skala X sangat buruk, jadi saya pikir X adalah masalah yang sangat sulit. Tapi besok, mungkin seseorang yang lebih pintar dari saya menciptakan sebuah algoritma yang memecahkan X dan berada dalam P. Jadi ini bukan definisi yang sangat baik dari masalah sulit.

Semua sama, ada banyak masalah dalam NP yang tidak diketahui oleh siapa pun algoritma yang baik. Jadi jika saya bisa membuktikan bahwa X adalah masalah tertentu: di mana algoritma yang baik untuk menyelesaikan X juga dapat digunakan, dalam beberapa cara bundaran, untuk memberikan algoritma yang baik untuk setiap masalah lain dalam NP. Nah sekarang orang mungkin sedikit lebih yakin bahwa X adalah masalah yang benar-benar rumit. Dan dalam hal ini kita sebut X NP-Complete.

Definisi untuk masalah lengkap NP di atas adalah benar, tetapi saya pikir saya mungkin akan liris tentang pentingnya filosofis mereka karena belum ada yang membahas masalah itu.

Hampir semua masalah rumit yang akan Anda hadapi adalah NP Lengkap. Ada sesuatu yang sangat mendasar tentang kelas ini, dan yang tampaknya berbeda secara komputasional dari masalah yang mudah dipecahkan. Mereka memiliki rasa sendiri, dan tidak sulit untuk mengenali mereka. Ini pada dasarnya berarti bahwa algoritma apa pun yang cukup rumit tidak mungkin Anda selesaikan dengan tepat - penjadwalan, pengoptimalan, pengepakan, perlindungan, dll.

Tetapi tidak semua hilang jika masalah yang Anda temui adalah NP Lengkap. Ada bidang yang luas dan sangat teknis di mana orang mempelajari algoritma perkiraan, yang akan memberi Anda jaminan untuk menjadi dekat dengan solusi dari masalah lengkap NP. Beberapa di antaranya adalah jaminan yang sangat kuat - misalnya, untuk 3sat, Anda bisa mendapatkan jaminan 7/8 melalui algoritma yang sangat jelas. Bahkan lebih baik, pada kenyataannya, ada beberapa heuristik yang sangat kuat, yang unggul dalam memberikan jawaban yang bagus (tapi tidak ada jaminan!) Untuk masalah ini.

Perhatikan bahwa dua masalah yang sangat terkenal - grafik isomorfisme dan anjak piutang - tidak diketahui sebagai P atau NP.

Saya telah mendengar penjelasan, yaitu: "NP-Completeness mungkin adalah salah satu ide yang lebih membingungkan dalam studi algoritma." NP "singkatan dari" waktu polinomial nondeterministik, "dan merupakan nama untuk apa yang disebut kelas kompleksitas untuk masalah mana yang bisa termasuk. Yang penting tentang kelas kompleksitas NP adalah bahwa masalah dalam kelas tersebut dapat diverifikasioleh algoritma waktu polinomial. Sebagai contoh, perhatikan masalah penghitungan barang. Misalkan ada banyak apel di atas meja. Masalahnya adalah "Ada berapa apel?" Anda diberikan jawaban yang memungkinkan, 8. Anda dapat memverifikasi jawaban ini dalam waktu polinomial dengan menggunakan algoritma, duh, menghitung apel. Menghitung apel terjadi dalam waktu O (n) (itu notasi Big-oh), karena dibutuhkan satu langkah untuk menghitung setiap apel. Untuk n apel, Anda perlu n langkah. Masalah ini ada di kelas kompleksitas NP.

Masalah diklasifikasikan sebagai NP-lengkap jika dapat ditunjukkan bahwa keduanya NP-Hard dan dapat diverifikasi dalam waktu polinomial. Tanpa membahas terlalu dalam NP-Hard, cukuplah untuk mengatakan bahwa ada masalah tertentu yang belum ditemukan solusi waktu polinomialnya. Artinya, dibutuhkan sesuatu seperti n! (n faktorial) langkah untuk menyelesaikannya. Namun, jika Anda diberi solusi untuk masalah NP-Complete, Anda dapat memverifikasinya dalam waktu polinomial.

Contoh klasik dari masalah NP-Complete adalah The Traveling Salesman Problem. "

Penulis: ApoxyButt Dari: http://www.everything2.com/title/NP-complete

Masalah NP: -

1. Masalah NP adalah masalah yang dapat diselesaikan dalam waktu polinomial non-deterministik.
2. Algoritma non deterministik beroperasi dalam dua tahap.
3. Tahapan menebak non deterministik && Tahap verifikasi non deterministik.

Jenis Masalah Np

1. NP selesai
2. NP Hard

Masalah lengkap NP: -

1 Masalah Keputusan A disebut NP selesai jika memiliki dua sifat berikut: -

1. Itu milik NP kelas.
2. Setiap masalah lain dalam NP dapat diubah menjadi P dalam waktu polinomial.

Beberapa Kelebihan: -

• Masalah ransel
• masalah sub set jumlah
• Vertex meliputi masalah

Masalah NP-complete adalah serangkaian masalah yang masing-masing masalah NP lainnya dapat dikurangi dalam waktu polinomial, dan yang solusinya masih dapat diverifikasi dalam waktu polinomial. Artinya, masalah NP apa pun dapat ditransformasikan menjadi masalah NP-lengkap. - Secara informal, masalah NP-complete adalah masalah NP yang setidaknya sama "tangguh" seperti masalah lainnya di NP.

Sejauh yang saya mengerti

P adalah serangkaian masalah yang dapat diselesaikan dalam waktu polinomial dengan TM deterministik.

NP adalah serangkaian masalah yang membutuhkan TM non-deterministik agar dapat diselesaikan dalam waktu polinomial. Ini berarti untuk secara parsial memeriksa semua variabel yang mungkin, masing-masing contoh mengambil waktu polinomial. Jika masalah dapat dipecahkan maka setidaknya salah satu dari kondisi paralel tersebut harus memiliki solusi untuk masalah tersebut. Ini juga berarti bahwa jika Anda menebak variabel solusi maka satu-satunya hal yang diperlukan adalah memeriksa validitas solusi dalam waktu polinomial.

NP-Hard adalah set di mana masalah setidaknya sekeras NP. Setiap masalah dalam NP dapat diubah menjadi masalah NP-Hard dalam waktu polinomial. Masalah-masalah ini tidak dapat diselesaikan dalam waktu polinomial jika P tidak sama dengan NP. Saat itulah masalah yang paling sulit di NP adalah waktu polinom terpecahkan maka hanya masalah NP-Hard yang polinomial waktu yang dapat dipecahkan.

NP-Complete adalah set persimpangan NP dan NP-Hard. Masalah NP apa pun dapat diubah menjadi masalah NP-Lengkap dalam waktu polinomial. Itu berarti jika salah satu NP-Lengkap dapat memiliki solusi yang efisien maka masalah NP dapat diselesaikan dengan efisiensi yang sama.

Tolong beri tahu saya jika saya melakukan kesalahan.

masalah NP adalah masalah di mana algoritma komputer yang memverifikasi solusi dapat dibuat dalam waktu polinomial.

masalah NP-Complete adalah NP, tetapi juga jika Anda dapat menyelesaikannya dalam waktu polinomial (disebut P) maka semua masalah NP adalah P.

Jadi cepatlah.