NP-hardness
Masalah NP-hard adalah masalah ya / tidak di mana menemukan solusi untuk itu setidaknya sama sulitnya dengan menemukan solusi untuk masalah tersulit yang solusinya dapat dengan cepat diperiksa sebagai benar. Beberapa masalah NP-hard adalah masalah di mana solusi yang berhasil dapat diperiksa dengan cepat (masalah NP) dan beberapa tidak. Masalah NP-hard yang juga merupakan masalah NP masuk ke dalam kategori yang disebut NP-complete.
Contoh masalah yang paling tidak sulit untuk dipecahkan seperti masalah lain yang dapat kita periksa solusinya dengan cepat, yang juga dapat diperiksa dengan cepat (NP-hard dan NP):
Seorang salesman keliling ingin mengunjungi 100 kota dengan mengemudi, memulai dan mengakhiri perjalanannya di rumah. Ia memiliki persediaan bensin yang terbatas, sehingga ia hanya bisa berkendara sejauh 10.000 kilometer. Ia ingin mengetahui apakah ia bisa mengunjungi semua kota tanpa kehabisan bensin.
Orang tidak tahu bagaimana menyelesaikan masalah ini lebih cepat daripada menguji setiap jawaban yang mungkin, tetapi jika ditemukan solusi yang memungkinkan salesman melakukan ini, kita dapat menggunakan algoritma untuk memeriksa bahwa itu benar. Masalah ini juga dikenal sebagai Travelling salesman problem.
Contoh masalah yang paling tidak sulit untuk dipecahkan seperti masalah lain yang dapat kita periksa solusinya dengan cepat, tetapi tidak dapat diperiksa dengan cepat (NP-hard, tetapi bukan NP):
jika seseorang memulai sebuah program yang hanya berjalan begitu saja,
while(true){ lanjutkan; }dan tidak pernah menghentikannya, apakah akan berjalan selamanya?
Tidak ada cara yang diketahui untuk menemukan solusi bagi semua masalah semacam ini, dan ini juga tidak dapat diperiksa.
Pertanyaan dan Jawaban
T: Apa yang dimaksud dengan masalah NP-hard?
A: Masalah NP-hard adalah jenis masalah matematika yang digunakan dalam ilmu komputer yang merupakan masalah ya/tidak di mana menemukan solusinya setidaknya sama sulitnya dengan menemukan solusi untuk masalah tersulit yang solusinya dapat dengan cepat diperiksa sebagai benar.
T: Dapatkah solusi yang berhasil diperiksa dengan cepat untuk semua masalah NP-hard?
J: Tidak, hanya beberapa masalah NP-hard, yang disebut masalah NP, yang memiliki solusi yang dapat diperiksa dengan cepat.
T: Apa nama kategori untuk soal-soal NP-hard yang juga merupakan soal NP?
J: Soal NP-sulit yang juga merupakan soal NP masuk ke dalam kategori yang disebut soal NP-lengkap.
T: Apakah semua soal NP-sulit adalah soal NP-lengkap?
J: Tidak, tidak semua soal NP-sulit adalah soal NP-lengkap. Hanya soal-soal yang juga merupakan soal NP yang termasuk dalam kategori ini.
T: Apakah soal-soal NP-sulit mudah diselesaikan?
J: Tidak, soal NP-sulit tidak mudah diselesaikan. Faktanya, menemukan solusi untuk masalah ini setidaknya sama sulitnya dengan menemukan solusi untuk masalah tersulit yang solusinya dapat dengan cepat diperiksa kebenarannya.
T: Apakah ada manfaat dari menyelesaikan soal-soal NP-hard?
J: Ya, menyelesaikan soal NP-hard dapat memberikan keuntungan di berbagai bidang, seperti ilmu komputer, fisika, dan ilmu sosial, karena soal-soal tersebut membutuhkan perhitungan dan pemodelan yang rumit.
T: Apakah ada penelitian yang sedang berlangsung dalam memecahkan masalah NP-hard?
J: Ya, penelitian dalam memecahkan masalah NP-hard sedang berlangsung karena masalah ini terus relevan di berbagai bidang, dan menemukan algoritme dan solusi yang efisien dapat memiliki implikasi yang signifikan.
