NP-Hard dan Mario Bros

P-Problems
P-Problems atau Polynomial Problems adalah permasalahan-permasalahan yang dapat diselesaikan dalam waktu Polynomial.

Polynomial Time
Yang termasuk dalam waktu polynomial adalah linier time O(n), quadratic time O(n²), exponential time O(2ⁿ), logaritmic time O(lg n) dan sebagainya.
n: size of the problem

Contoh permasalahan P-Problems
Masalah-masalah yang biasa kita selesaikan seperti Bubble Sort, Binary Search adalah contoh P-Problems.

Nondeterministic Polynomial Time
Pada NP time, kita cenderung membuat suatu tebakan daripada melakukan perhitungan seperti pada P time. Contoh: Sebuah masalah pengambilan keputusan yang memiliki jawaban ya atau tidak. Idenya adalah kita ingin mencari tebakan yang mengarah kepada jawaban “ya”, kemudian mesin akan memberikan satu solusi yang ditemukan (jika ditemukan). Kadang orang menyebut NP sebagai “lucky model of computation”.

Contoh Nondeterministic Polynomial
3-SAT
Diberikan boolean formula:
(x₁ ∨ x₃ ∨ ¬x₆) ∧ (x₂ ∨ x₃ ∨ ¬x₇ ) ∧ …

Kita memiliki formula and, yang didalamnya terdapat or, dan setiap klausa or memiliki 3 literal (klausa pertama memiliki literal x₁, x₃ dan not x₆, klausa kedua memiliki literal x₂, x₃ dan not x₇).
Tujuan kita adalah memenuhi atau satisfying (because SAT stands for Satisfy) formula dengan cara mengatur variabel dengan nilai true atau false untuk mendapatkan output true. Permasalahan di atas tidak dapat diselesaikan dalam waktu polynomial, karena kita akan melakukan penebakan. Jika beruntung menebak, kita dapat menemukan solusi dengan cepat.

Jika tidak ada solusi (formula tidak dapat dipenuhi) apakah ini tetap merupakan permasalahan NP?
Jawabannya adalah Ya.

Ketika formula terpenuhi atau satisfy, ini berarti formula tersebut dapat diselesaikan dalam waktu polynomial time. Misalkan kita telah mendapatkan suatu set variabel yang dapat menghasilkan keluaran true. Anggap saja x₁ true, x₃ false, x₆ true dan seterusnya. Maka waktu yang dibutuhkan untuk menyelesaikan formula ini adalah O(1) atau constant. Kasus inilah yang biasa disebut dengan NP-Problems.

NP-Problems
Permasalahan NP yang dapat diverifikasi pada waktu polynomial untuk yes-input.

NP-Hard
Permasalahan dikatakan NP-Hard jika setiap subpermasalahan pada permasalahan tersebut dapat direduce ke permasalahan NP.

Reduction
Reduction dari masalah A ke masalah B artinya jika terdapat solusi B yang dapat dikerjakan dalam P time atau NP time, maka solusi tersebut juga merupakan solusi untuk masalah A.
if B ∈ P then A ∈ P
if B ∈ NP then A ∈ NP

NP-Completeness
Permasalahan yang termasuk kedalam NP-Problems dan NP-Hard

NP-Hard pada Mario Bros
Permainan Mario Bros memiliki beberapa peraturan seperti:

1. Mario berjalan kedepan, dan tidak bisa kembali ke belakang.
2. Jika kita memilih suatu jalan A, maka kita tidak bisa kembali untuk memilih jalan lain, kecuali kita mati atau mengulang permainan.
3. Tujuan dari permainan ini adalah mencapai bendera finish untuk menuju level selanjutnya.

Dalam gambar di atas, Mario memiliki 2 opsi, yaitu memilih jalan atas, atau jalan bawah. Kita dapat menganalogikan jalan atas sebagai x₁ dan jalan bawah sebagai x₂ jadi kita punya formula (x₁ ∨ x₂). Mario harus menebak jalan mana yang memiliki keuntungan terbanyak. Ketika Mario memilih jalan atas, maka x₁ diatur menjadi True, x₂ menjadi False, dan sebaliknya.

Setelah rintangan pertama, akan ada rintangan kedua dan seterusnya. Setiap rintangan kita analogikan sebagai formula, sehingga untuk setiap rintangan dapat dimisalkan sebagai (x₁ ∨ x₂) ∧ (x₃ ∨ ¬x₄ ∨ x₅) ∧ …

Setiap keputusan yang kita ambil, harus dapat men-satisfy suatu clause. Kita dapat mencapai garis finish jika semua clause telah di-satisfy, dengan artian dari semua formula yang terbentuk, menghapilkan output true.

Referensi:
MIT OpenCourseWare, Complexity: P, NP, NP-completeness, Reductions
https://www.youtube.com/watch?v=mr1FMrwi6Ew
https://arxiv.org/pdf/1203.1895v3.pdf