Pengantar NP-Completeness

Selama dekade 1970-an, Cook, Karp, dan Levin membangun kerangka teori yang mengubah cara kita memandang kesulitan masalah komputasi: klasifikasi P, NP, NP-hard, dan NP-complete. Inti teori ini menjawab pertanyaan “Apakah masalah ini bisa diselesaikan dalam waktu polinomial?” — dan untuk ribuan masalah penting, jawabannya “Kami tidak tahu, tetapi bila salah satu bisa, semua bisa”. Pada Chapter ini kita mendefinisikan empat kelas kompleksitas, mendemonstrasikan algoritma brute-force untuk SAT (NP-complete klasik), menjelaskan konsep reduksi polinomial, dan menutup dengan daftar masalah NP-complete yang sering muncul di interview dan kompetisi. Pemahaman teori ini krusial agar kita tidak menghabiskan waktu mencari algoritma polinomial untuk masalah yang (kemungkinan besar) tidak memilikinya.

Aturan: Empat Kelas Kompleksitas #

Definisi Formal: Reduksi Polinomial #

A ≤p B (A reducible ke B secara polinomial) berarti: ada fungsi f yang dapat dihitung polinomial sehingga untuk setiap input x:

x ∈ A  ⟺  f(x) ∈ B

Inti: bila kita punya algoritma polinomial untuk B, kita dapat algoritma polinomial untuk A dengan transformasi input via f lalu jalankan solver B. Maka B paling tidak sama mudahnya dengan A.

Hierarki #

Bila P = NP (masalah terbuka), maka NPC = P — semua masalah NP-complete punya solusi polinomial. Konsensus ilmiah: P ≠ NP, sehingga NP-complete tidak punya solusi polinomial.

Mekanisme: Brute-Force SAT dan Eksponensialitas #

SAT (Boolean Satisfiability): diberikan formula boolean dalam CNF (Conjunctive Normal Form), cari assignment variabel yang membuat formula true.

Contoh formula 2 variabel:

• (x1 ∨ x2) ∧ (¬x1 ∨ x2) ∧ (x1 ∨ ¬x2) ∧ (¬x1 ∨ ¬x2)

Cek semua 4 assignment:

Semua assignment gagal — UNSATISFIABLE. Brute-force selalu O(2^n · m) di mana n = jumlah variabel dan m = jumlah clause. Untuk n = 30, ini sudah ~10^9 iterasi; n = 50 mustahil dalam waktu manusia.

Kode: Brute-Force SAT Solver #

#include <iostream>
#include <vector>
#include <string>
#include <cstdio>

using namespace std;

// SAT instance: variabel x1..xn, clause adalah list literal (positif = xi, negatif = NOT xi)
struct SATInstance {
    int n_vars;
    vector<vector<int>> clauses;
};

// Brute-force SAT: coba semua 2^n assignment. Kompleksitas O(2^n * m) di mana m = jumlah clause.
// Mengembalikan jumlah assignment yang dicoba (untuk demo kompleksitas).
long long sat_solve(const SATInstance& inst, vector<bool>& assignment, bool& found) {
    int n = inst.n_vars;
    long long tried = 0;
    for (int mask = 0; mask < (1 << n); ++mask) {
        ++tried;
        bool all_sat = true;
        for (const auto& clause : inst.clauses) {
            bool clause_sat = false;
            for (int lit : clause) {
                int var = abs(lit) - 1;
                bool val = (mask >> var) & 1;
                if (lit > 0 && val) { clause_sat = true; break; }
                if (lit < 0 && !val) { clause_sat = true; break; }
            }
            if (!clause_sat) { all_sat = false; break; }
        }
        if (all_sat) {
            assignment.assign(n, false);
            for (int i = 0; i < n; ++i) assignment[i] = (mask >> i) & 1;
            found = true;
            return tried;
        }
    }
    found = false;
    return tried;
}

string fmt_clause(const vector<int>& c) {
    string s = "(";
    for (size_t i = 0; i < c.size(); ++i) {
        if (i) s += " OR ";
        if (c[i] < 0) s += "NOT ";
        s += "x" + to_string(abs(c[i]));
    }
    s += ")";
    return s;
}

string fmt_instance(const SATInstance& inst) {
    string s;
    for (size_t i = 0; i < inst.clauses.size(); ++i) {
        if (i) s += " AND ";
        s += fmt_clause(inst.clauses[i]);
    }
    return s;
}

int main() {
    // Instance 1: UNSATISFIABLE
    // (x1 OR x2) AND (NOT x1 OR x2) AND (x1 OR NOT x2) AND (NOT x1 OR NOT x2)
    SATInstance unsat;
    unsat.n_vars = 2;
    unsat.clauses = {{1, 2}, {-1, 2}, {1, -2}, {-1, -2}};

    cout << "Instance 1: " << fmt_instance(unsat) << '\n';
    vector<bool> a1;
    bool r1;
    long long t1 = sat_solve(unsat, a1, r1);
    cout << "Satisfiable? " << (r1 ? "YA" : "TIDAK") << '\n';
    cout << "Assignment yang dicoba: " << t1 << " (2^n = " << (1 << unsat.n_vars) << ")\n\n";

    // Instance 2: SATISFIABLE
    // (x1 OR x2) AND (NOT x1 OR x2) AND (x1 OR NOT x2)
    SATInstance sat;
    sat.n_vars = 2;
    sat.clauses = {{1, 2}, {-1, 2}, {1, -2}};

    cout << "Instance 2: " << fmt_instance(sat) << '\n';
    vector<bool> a2;
    bool r2;
    long long t2 = sat_solve(sat, a2, r2);
    cout << "Satisfiable? " << (r2 ? "YA" : "TIDAK") << '\n';
    if (r2) {
        cout << "Assignment: x1=" << a2[0] << ", x2=" << a2[1] << '\n';
    }
    cout << "Assignment yang dicoba: " << t2 << " (2^n = " << (1 << sat.n_vars) << ")\n";

    // Demo kompleksitas eksponensial: jumlah iterasi untuk n berbeda (instance UNSAT penuh)
    cout << "\nDemo kompleksitas (instance UNSAT, coba semua 2^n):\n";
    cout << "   n  | 2^n        | iterasi\n";
    cout << "  ----|------------|------------\n";
    for (int n : {5, 10, 15, 20}) {
        // Instance UNSAT sederhana: (x1) AND (NOT x1)
        SATInstance unsat_n;
        unsat_n.n_vars = n;
        unsat_n.clauses.push_back({1});         // x1 harus true
        unsat_n.clauses.push_back({-1});        // x1 harus false
        for (int i = 2; i <= n; ++i) {
            unsat_n.clauses.push_back({i, -i});  // tautology, tidak mengubah satisfiability
        }
        vector<bool> a;
        bool r;
        long long it = sat_solve(unsat_n, a, r);
        printf("  %3d | %10d | %lld\n", n, (1 << n), it);
    }
    return 0;
}

Output yang Dihasilkan:

Instance 1: (x1 OR x2) AND (NOT x1 OR x2) AND (x1 OR NOT x2) AND (NOT x1 OR NOT x2)
Satisfiable? TIDAK
Assignment yang dicoba: 4 (2^n = 4)

Instance 2: (x1 OR x2) AND (NOT x1 OR x2) AND (x1 OR NOT x2)
Satisfiable? YA
Assignment: x1=1, x2=1
Assignment yang dicoba: 4 (2^n = 4)

Demo kompleksitas (instance UNSAT, coba semua 2^n):
   n  | 2^n        | iterasi
  ----|------------|------------
    5 |         32 | 32
   10 |       1024 | 1024
   15 |      32768 | 32768
   20 |    1048576 | 1048576

Bedah Kode Baris-per-Baris #

1. struct SATInstance { int n_vars; vector<vector<int>> clauses; }: variabel x1..xn. Clause = list literal; literal positif +i berarti xi, negatif -i berarti ¬xi.
2. for (int mask = 0; mask < (1 << n); ++mask): iterasi semua 2^n assignment. Bit ke-i dari mask menentukan nilai xi (1 = true, 0 = false).
3. for (int lit : clause): cek setiap literal. abs(lit) - 1 = indeks variabel (0-based). val = (mask >> var) & 1 ekstrak bit variabel tersebut.
4. if (lit > 0 && val) { clause_sat = true; break; }: literal positif satisfied bila variabel true. Break clause loop — clause sudah pasti satisfied.
5. if (lit < 0 && !val) { clause_sat = true; break; }: literal negatif satisfied bila variabel false.
6. if (!clause_sat) { all_sat = false; break; }: clause tidak satisfied → instance tidak satisfied untuk mask ini. Lanjut ke mask berikutnya.
7. Instance 1 (UNSAT): 4 assignment semua gagal. Cek tabel di atas — kolom kanan semua F. Brute-force mencoba semua 4 = 2^2 assignment.
8. Instance 2 (SAT): assignment x1=T, x2=T (mask = 3) men-satisfy semua clause. Brute-force mencoba mask = 0, 1, 2 (gagal) lalu mask = 3 (sukses). Total 4 iterasi (karena mask = 3 adalah iterasi ke-4).
9. Demo kompleksitas: instance UNSAT dengan n variabel. Tabel menunjukkan iterasi = 2^n tepat. Untuk n = 30 → ~10^9 iterasi; n = 40 → ~10^12; n = 50 → ~10^15 — di luar jangkauan komputer modern (1 GHz × 1 tahun = ~3 × 10^16 siklus).

Mekanisme: Reduksi Polinomial #

Untuk membuktikan masalah B NP-hard, kita lakukan reduksi dari masalah A yang sudah diketahui NP-hard ke B:

1. Asumsi: A NP-hard (mis. 3-SAT).
2. Konstruksi f: untuk setiap input x masalah A, bangun input f(x) masalah B dalam waktu polinomial.
3. Bukti ekuivalensi: x ∈ A ⟺ f(x) ∈ B. Yaitu, x adalah “yes” instance untuk A iff f(x) adalah “yes” instance untuk B.
4. Konklusi: bila B punya solver polinomial, maka A juga (via f). Karena A NP-hard, B juga NP-hard.

Contoh Klasik: 3-SAT ≤p Vertex Cover #

Diberikan instance 3-SAT dengan m clause dan n variabel, bangun graph:

• Untuk setiap variabel xi: dua node T_i (true) dan F_i (false) dihubungkan edge.
• Untuk setiap clause (l1 ∨ l2 ∨ l3): triangle (3 node, satu per literal), dengan label literal.
• Hubungkan setiap node triangle dengan node variable yang sesuai (mis. node untuk literal xi di triangle connect ke T_i; node untuk ¬xi connect ke F_i).

Claim: 3-SAT instance satisfiable iff graph punya vertex cover ukuran k = n + 2m.

Sketsa bukti:

• (⇒) Bila assignment memuaskan: pilih T_i atau F_i sesuai assignment (1 per variabel → n vertex), lalu untuk setiap clause pilih 2 dari 3 triangle node yang tidak match literal yang true (2 per clause → 2m vertex). Total n + 2m.
• (⇐) Bila vertex cover ukuran n + 2m: edge variabel T_i - F_i memaksa pilih salah satu — menentukan assignment. Edge triangle-clause-to-variable memaksa setiap clause punya ≥ 1 literal true (bila tidak, ketiga node triangle harus dipilih, tapi hanya 2 yang di-cover, kontradiksi). Maka assignment men-satisfy 3-SAT.

Reduksi ini berjalan dalam O(n + m) — polinomial. Maka Vertex Cover NP-hard. Karena Vertex Cover ∈ NP (verifikasi polinomial), Vertex Cover NP-complete.

Cook-Levin Theorem #

Theorem (Cook 1971, Levin 1973): SAT adalah NP-complete.

Sketsa bukti: Untuk setiap masalah L ∈ NP, ada mesin Turing non-deterministik M yang memutus L dalam waktu polinomial p(n). Konstruksi formula SAT yang mengkodekan:

1. Konfigurasi awal tape M berisi input x.
2. Setiap langkah komputasi M valid sesuai transisi.
3. Konfigurasi akhir adalah “accept”.

Formula ini berukuran polinomial dalam |x| (karena M berjalan polinomial), dan satisfiable iff M menerima x (untuk beberapa guess non-deterministik). Maka L ≤p SAT untuk semua L ∈ NP — artinya SAT NP-hard. Karena SAT ∈ NP (verifikasi assignment polinomial), SAT NP-complete.

Konsekuensi: setiap masalah NP dapat direduksi ke SAT. Ini dasar dari SAT solver modern (DPLL, CDCL) yang dipakai di industri (verifikasi hardware, planning, scheduling).

Masalah NP-Complete Klasik #

Semua masalah di atas dapat direduksi satu sama lain dalam waktu polinomial (jaringan reduksi). Bila satu ditemukan punya algoritma polinomial, semua juga punya.

Kenapa Ini Penting bagi Praktisi DSA #

1. Mengenali masalah NP-complete menghindari kita dari mengejar solusi polinomial yang (kemungkinan besar) tidak ada. Alih-alih, arahkan energi ke approximation atau heuristik.

2. Reduksi sebagai tool memungkinkan kita menggunakan SAT solver atau ILP solver untuk masalah sulit: encode masalah sebagai SAT instance, lempar ke solver industri (Minisat, Z3), dapat solusi dalam milidetik untuk input sedang.

3. Kompleksitas praktis vs teoretis: algoritma O(2^n) untuk n ≤ 30 masih feasible dengan optimasi (mis. branch-and-bound). Algoritma O(n^3) untuk n = 1000 pun juga feasible. Konstanta sering kali lebih penting daripada asimptotik untuk input praktis.

4. Open problem P = NP: bila satu masalah NP-complete punya algoritma polinomial, maka P = NP — implikasi revolusioner untuk kriptografi (RSA hancur), AI (banyak masalah optim jadi mudah), dan teori komputasi. Konsensus: P ≠ NP, tetapi belum ada bukti formal.

Ringkasan #

• P = masalah dengan solusi polinomial; NP = masalah dengan verifikasi polinomial.
• NP-hard = paling tidak lebih mudah dari semua NP; NP-complete = NP-hard ∩ NP.
• Reduksi polinomial A ≤p B membuktikan B paling tidak sama sulitnya dengan A.
• Cook-Levin theorem: SAT adalah NP-complete — semua masalah NP dapat direduksi ke SAT.
• Brute-force SAT kompleksitas O(2^n · m) — eksponensial, tidak feasible untuk n ≥ 30 (1 miliar+ iterasi).
• Strategi praktis: approximation algorithm, heuristik, SAT/ILP solver, parameterized complexity.
• Jangan mencari algoritma polinomial untuk masalah NP-complete kecuali P = NP.