P বনাম NP — NP-complete আর reduction

১ · সহজ সমস্যা, কঠিন সমস্যা — আর “দক্ষ” মানে কী

এই কোর্সে এ পর্যন্ত প্রায় সব সমস্যার একটি দ্রুত অ্যালগরিদম পেয়েছেন: sort-এ O(n log n), shortest path-এ O((V + E) log V), MST-তে O(E log V). কিন্তু পর্ব ৫৬ আর ৫৭-এ এমন কিছু সমস্যা দেখেছেন — Hamiltonian cycle, traveling salesman, graph colouring — যেখানে backtracking আর branch and bound-এর বেশি কিছু পাওয়া যায়নি, আর worst case-এ সময় 2ⁿ বা n!-এর ধাঁচে। প্রশ্নটি স্বাভাবিক: এগুলোর দ্রুত অ্যালগরিদম কি আমরা এখনো খুঁজে পাইনি, নাকি এগুলো সত্যিই কঠিন? এই পর্বের পুরো তত্ত্ব এই প্রশ্নটি সঠিকভাবে জিজ্ঞেস করার ভাষা।

Decision আর optimization

তত্ত্বের সুবিধার জন্য সমস্যাগুলোকে হ্যাঁ/না প্রশ্নে লেখা হয় — decision problem. “সবচেয়ে ছোট vertex cover কত বড়?” একটি optimization problem; তার decision রূপ: “k বা তার কম vertex দিয়ে কি cover করা যায়?” এতে কিছু হারায় না। Decision রূপের দ্রুত সমাধান থাকলে k = 0, 1, 2, … (বা পর্ব ১৯-এর মতো k-এর ওপর binary search) চেষ্টা করে সর্বনিম্ন মানটি পাওয়া যায় — মাত্র O(log n) বার ডাকলেই। উল্টো দিকে, optimization সমাধান করতে পারলে decision তো সাথে সাথেই। তাই কঠিনতার প্রশ্নে দুটি প্রায় সমান, আর decision রূপ নিয়ে কথা বলা অনেক পরিষ্কার।

Polynomial সময় কেন “দক্ষ”

একটি অ্যালগরিদম polynomial time-এর, যদি ইনপুটের আকার n হলে সময় O(nᶜ) হয় কোনো স্থির c-এর জন্য — n, n log n, n², n³ সবই এর মধ্যে। 2ⁿ, n!, nⁿ এর বাইরে। পার্থক্যটি সংখ্যায় দেখুন, ধরে নিয়ে কম্পিউটার সেকেন্ডে ১০^৮টি কাজ করে:

আরও গুরুত্বপূর্ণ একটি পার্থক্য: কম্পিউটার দ্বিগুণ দ্রুত হলে n² অ্যালগরিদম একই সময়ে প্রায় ১.৪১ গুণ বড় ইনপুট সামলায়, কিন্তু 2ⁿ অ্যালগরিদম মাত্র একটি বেশি — n থেকে n + 1. Exponential অ্যালগরিদমকে হার্ডওয়্যার দিয়ে বাঁচানো যায় না।

১৯৬৫ সালে দুজন গবেষক আলাদাভাবে প্রস্তাব করেন যে “দক্ষ অ্যালগরিদম” মানে polynomial সময়ের অ্যালগরিদম — Alan Cobham (“The intrinsic computational difficulty of functions”) আর Jack Edmonds (“Paths, trees, and flowers”, যেখানে তিনি সাধারণ গ্রাফে maximum matching-এর polynomial অ্যালগরিদম দেন)। একে বলা হয় Cobham–Edmonds thesis. এটি উপপাদ্য নয়, একটি কাজের সংজ্ঞা — n¹⁰⁰ বাস্তবে মোটেই দ্রুত নয়। তবু সংজ্ঞাটি টিকে আছে তিনটি কারণে: বাস্তবে যে polynomial অ্যালগরিদম পাওয়া যায় তাদের ঘাত প্রায় সবসময় ছোট (২ বা ৩); polynomial-এর শ্রেণি যোগ, গুণ আর একটির ভেতর আরেকটি ডাকায় বন্ধ থাকে (polynomial-এর polynomial আবার polynomial); আর যুক্তিসংগত সব কম্পিউটার-মডেলে (RAM, Turing machine) একই সমস্যাগুলো polynomial থাকে।

২ · P আর NP — সমাধান করা বনাম যাচাই করা

এই “খুঁজে বের করা কঠিন, কিন্তু দেখে মিলিয়ে নেওয়া সহজ” — এটিই NP-এর মূল কথা। সংজ্ঞাগুলো:

এই প্রমাণকে বলে certificate (বা witness, সাক্ষী)। Vertex cover-এ certificate হলো vertex-গুলোর তালিকা; SAT-এ চলকগুলোর মান; Hamiltonian cycle-এ vertex-এর ক্রম; subset sum-এ বাছাই করা সংখ্যাগুলো; sudoku-তে ভরা বোর্ড; বিয়ের সমস্যায় (আসলে graph colouring — অতিথি vertex, মনোমালিন্য edge, টেবিল রং) প্রত্যেকের টেবিল নম্বর। প্রতিটি ক্ষেত্রে certificate ছোট, আর মিলিয়ে দেখতে polynomial সময় লাগে।

নিচের গ্রাফে প্রশ্ন: ৩টি বা কম vertex দিয়ে কি সব edge cover করা যায়? Verifier কীভাবে দুটি certificate যাচাই করে দেখুন:

নিচের প্রোগ্রাম একই কথা সংখ্যায় দেখায়। একটি ring গ্রাফে (0–1–2–…–(n−1)–0, এখানে n জোড়) সবচেয়ে ছোট vertex cover-এর আকার n/2 — একটি করে বাদ দিয়ে vertex নিলেই হয়। Verifier certificate মেলায় O(V + E)-এ; brute-force search সব 2ⁿ subset চেষ্টা করে গোনে কতবার চেষ্টা লাগল:

#include <bit>
#include <initializer_list>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;
using Edges = vector<pair<int, int>>;

Edges ring(int n) {                              // cycle 0-1-2-...-(n-1)-0
    Edges e;
    for (int i = 0; i < n; ++i) e.push_back({i, (i + 1) % n});
    return e;
}
// VERIFIER, O(V + E): is S a vertex cover with |S| <= k?
bool verify(int n, const Edges& e, const vector<int>& S, int k) {
    if ((int)S.size() > k) return false;
    vector<bool> in(n, false);
    for (int v : S) in[v] = true;
    for (auto [u, v] : e) if (!in[u] && !in[v]) return false;   // an uncovered edge
    return true;
}
// SEARCH, O(2^n * E): try every subset as a bitmask, count the tries
bool search(int n, const Edges& e, int k, long long& tries) {
    tries = 0;
    for (unsigned long long m = 0; m < (1ULL << n); ++m) {
        ++tries;
        if (popcount(m) > k) continue;
        bool ok = true;
        for (auto [u, v] : e) if (!(m >> u & 1) && !(m >> v & 1)) { ok = false; break; }
        if (ok) return true;
    }
    return false;
}
int main() {
    Edges e = ring(10);
    cout << "verify {0 2 4 6 8}, k=5: " << (verify(10, e, {0, 2, 4, 6, 8}, 5) ? "YES" : "NO") << '\n';
    cout << "verify {0 2 4 6 7}, k=5: " << (verify(10, e, {0, 2, 4, 6, 7}, 5) ? "YES" : "NO") << '\n';
    for (int n : {8, 12, 16, 20})
        for (int k : {n / 2 - 1, n / 2}) {
            long long tries;
            bool found = search(n, ring(n), k, tries);
            cout << "ring n=" << n << " k=" << k << ": " << (found ? "yes" : "no ") << "  subsets tried=" << tries << '\n';
        }
}

verify {0 2 4 6 8}, k=5: YES
verify {0 2 4 6 7}, k=5: NO
ring n=8 k=3: no   subsets tried=256
ring n=8 k=4: yes  subsets tried=86
ring n=12 k=5: no   subsets tried=4096
ring n=12 k=6: yes  subsets tried=1366
ring n=16 k=7: no   subsets tried=65536
ring n=16 k=8: yes  subsets tried=21846
ring n=20 k=9: no   subsets tried=1048576
ring n=20 k=10: yes  subsets tried=349526

NP মানে “non-polynomial” নয়

৩ · Reduction — একটি সমস্যাকে আরেকটির ভাষায় লেখা

সমস্যা A থেকে B-তে একটি polynomial-time reduction, লেখা হয় A ≤p B, হলো একটি polynomial সময়ের রূপান্তর f, যা A-এর প্রতিটি ইনপুট x-কে B-এর একটি ইনপুট f(x)-এ বদলায়, এমনভাবে যে

এর মানে: B-এর একটি দ্রুত অ্যালগরিদম থাকলে A-এরও আছে — x নিন, f(x) বানান, B-এর অ্যালগরিদম চালান। Polynomial-এর ভেতর polynomial আবার polynomial, তাই মোট সময়ও polynomial. উল্টো দিক থেকে পড়লে আরও কাজের: A কঠিন হলে B-ও অন্তত ততটা কঠিন। চিহ্ন “≤” এই কারণেই — A-এর কঠিনতা B-এর কঠিনতার চেয়ে বেশি নয়। Reduction transitive: A ≤p B আর B ≤p C হলে A ≤p C (দুটি রূপান্তর পরপর চালান)।

NP-hard আর NP-complete

প্রতিটি নতুন সমস্যার জন্য NP-এর সব সমস্যা থেকে reduction দেখানো অসম্ভব। কিন্তু transitivity বাঁচিয়ে দেয়: একটি জানা NP-complete সমস্যা C থেকে C ≤p X দেখালেই সব NP সমস্যা C হয়ে X-এ পৌঁছায়। তাই NP-completeness প্রমাণের চারটি ধাপ:

1. X ∈ NP: certificate কী, আর verifier কেন polynomial — বলুন।
2. একটি জানা NP-complete সমস্যা C বাছুন — 3-SAT, vertex cover, Hamiltonian cycle, subset sum ইত্যাদি, যেটি X-এর গঠনের সবচেয়ে কাছে।
3. রূপান্তর f বানান C-এর ইনপুট থেকে X-এর ইনপুটে, আর দেখান f polynomial সময়ে চলে।
4. সঠিকতা প্রমাণ করুন দুই দিকেই: C-এর হ্যাঁ ⇒ X-এর হ্যাঁ, আর X-এর হ্যাঁ ⇒ C-এর হ্যাঁ.

৪ · প্রথম NP-complete সমস্যা — Cook–Levin আর Karp-এর ২১টি

শিকলের প্রথম আংটা কোথা থেকে? কাউকে সরাসরি দেখাতে হয়েছিল যে NP-এর প্রতিটি সমস্যা একটি নির্দিষ্ট সমস্যায় reduce হয়। সেই সমস্যা SAT: কয়েকটি true/false চলকের একটি যুক্তি-সূত্র — চলকগুলোর এমন মান আছে কি, যাতে সূত্রটি true হয়? সাধারণত সূত্রটি থাকে CNF রূপে: কয়েকটি clause-এর AND, প্রতিটি clause কয়েকটি literal-এর OR. যেমন

প্রতিটি clause-এ ঠিক তিনটি literal থাকলে সমস্যাটির নাম 3-SAT. φ satisfiable: x₁ = 1, x₂ = 0, x₃ = 0 দিলে প্রথম clause-এ x₁, দ্বিতীয়তে ¬x₂, তৃতীয়তে x₁ সত্য। এই মানগুলোই certificate — m টি clause-এর প্রতিটি একবার দেখে O(m)-এ যাচাই।

এই পর্বের বাকি অংশে আমরা একটি ছোট শিকল নিজে হাতে বানাব:

SAT ──(Cook–Levin)──► 3-SAT ──► Independent Set ◄──► Vertex Cover
                                       │
                                       ▼
                                    Clique

Hamiltonian cycle ──► TSP (decision)          Subset Sum ──► Knapsack

৫ · 3-SAT → Independent Set — clause-ত্রিভুজ আর বিরোধের edge

গ্রাফের একটি independent set হলো এমন vertex-এর সেট, যাদের কোনো দুজনের মধ্যে edge নেই — বন্ধুসভায় এমন কয়েকজনকে ডাকা, যাদের কেউ কাউকে অপছন্দ করেন না। Decision প্রশ্ন: “k আকারের একটি independent set আছে কি?” এটি NP-তে (certificate হলো সেই k টি vertex, মিলিয়ে দেখতে O(k²) বা O(V + E)). এখন দেখাব 3-SAT ≤p Independent Set.

m টি clause-এর একটি 3-CNF সূত্র φ থেকে গ্রাফ G বানান:

• প্রতিটি literal-এর জন্য একটি vertex — প্রতিটি clause-এর জন্য তিনটি, মোট 3m.
• Clause-ত্রিভুজ: একই clause-এর তিনটি vertex পরস্পর যুক্ত। তাই প্রতিটি clause থেকে সর্বোচ্চ একজনকে বাছা যায়।
• বিরোধের edge: দুটি ভিন্ন clause-এ x আর ¬x থাকলে তাদের মধ্যে edge. তাই একই চলককে একসাথে সত্য আর মিথ্যা “ধরে নেওয়া” যায় না।
• k = m.

Pseudocode — 3-SAT to Independent Set (clauses 1..m, vertex (j, t) = t-th literal of clause j)

reduce(phi with clauses C1..Cm):
    V = { (j, t) : 1 ≤ j ≤ m, 1 ≤ t ≤ 3 }               // 3m vertices
    for each j: join (j,1)-(j,2), (j,2)-(j,3), (j,1)-(j,3) // clause triangle
    for each pair of vertices in different clauses:
        if their literals are x and NOT x: join them       // conflict edge
    return (G = (V, E), k = m)                             // O(m^2) time

এখন কোডে দুই দিকই brute force দিয়ে মিলিয়ে দেখুন। প্রোগ্রামটি দুটি সূত্র নেয়: F1 = ওপরের φ, আর F2 = তিন চলকের সব ৮টি চিহ্ন-বিন্যাসের clause — প্রতিটি assignment ঠিক একটি clause-কে মিথ্যা করে, তাই F2 unsatisfiable. প্রতিটির জন্য গ্রাফ বানায়, SAT-এর দিকে সব 2ⁿ assignment চেষ্টা করে, গ্রাফের দিকে k আকারের independent set খোঁজে (প্রতিটি vertex নেব/নেব না — পর্ব ৫৬-এর subset গাছ, সাথে “বাকি সব নিলেও k হবে না” সীমা), আর পাওয়া set থেকে assignment ফিরিয়ে আবার verifier দিয়ে মেলায়। x=100 মানে x1 = 1, x2 = 0, x3 = 0; ~x2@C2 মানে C2-এর ¬x2 vertex.

#include <cstdlib>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
using Formula = vector<vector<int>>;     // literal +i = x_i, -i = NOT x_i
bool satisfied(const Formula& f, int a) {          // verifier: O(m) for m clauses
    for (auto& c : f) {
        bool ok = false;
        for (int l : c) if (((a >> (abs(l) - 1)) & 1) == (l > 0)) ok = true;
        if (!ok) return false;
    }
    return true;
}
int V, K; vector<int> lit; vector<long long> adj; long long nodes;   // vertex 3j+t = t-th literal of clause j
long long findIS(int i, long long chosen, int size) {                // returns the set, or -1
    ++nodes;
    if (size == K) return chosen;
    if (i == V || size + (V - i) < K) return -1;
    if (!(adj[i] & chosen)) { long long r = findIS(i + 1, chosen | 1LL << i, size + 1); if (r >= 0) return r; }
    return findIS(i + 1, chosen, size);
}
string bits(int a, int n) { string s; for (int i = 0; i < n; ++i) s += char('0' + (a >> i & 1)); return s; }
void run(const string& name, const Formula& f, int n) {
    K = f.size(); V = 3 * K; lit.clear(); adj.assign(V, 0); nodes = 0;
    int E = 0; for (auto& c : f) for (int l : c) lit.push_back(l);
    for (int u = 0; u < V; ++u) for (int v = u + 1; v < V; ++v)
        if (u / 3 == v / 3 || lit[u] == -lit[v]) { adj[u] |= 1LL << v; adj[v] |= 1LL << u; ++E; }  // triangle / conflict
    int tries = 0, sat = -1;                                         // side 1: try all 2^n assignments
    for (int a = 0; a < (1 << n); ++a) { ++tries; if (satisfied(f, a)) { sat = a; break; } }
    long long S = findIS(0, 0, 0);                                   // side 2: independent set of size K
    cout << name << ": n=" << n << " clauses=" << K << " -> graph V=" << V << " E=" << E << ", ask: independent set of size " << K << "?\n";
    cout << "  SAT  : " << (sat < 0 ? "no" : "yes x=" + bits(sat, n)) << " (tries=" << tries << ")\n";
    if (S < 0) { cout << "  IS   : no (search nodes=" << nodes << ")\n"; return; }
    cout << "  IS   : yes {"; int b = 0;
    for (int v = 0, first = 1; v < V; ++v) if (S >> v & 1) {
        cout << (first ? "" : " ") << (lit[v] < 0 ? "~x" : "x") << abs(lit[v]) << "@C" << v / 3 + 1; first = 0;
        if (lit[v] > 0) b |= 1 << (lit[v] - 1);                      // chosen literal = true, others false
    }
    cout << "} (search nodes=" << nodes << ")\n  IS -> x=" << bits(b, n) << " satisfies: " << (satisfied(f, b) ? "yes" : "no") << '\n';
}
int main() {
    run("F1", {{1, 2, 3}, {-1, -2, 3}, {1, -2, -3}}, 3);
    run("F2", {{1, 2, 3}, {-1, 2, 3}, {1, -2, 3}, {-1, -2, 3},        // every sign pattern
               {1, 2, -3}, {-1, 2, -3}, {1, -2, -3}, {-1, -2, -3}}, 3);
}

F1: n=3 clauses=3 -> graph V=9 E=15, ask: independent set of size 3?
  SAT  : yes x=100 (tries=2)
  IS   : yes {x1@C1 ~x2@C2 x1@C3} (search nodes=8)
  IS -> x=100 satisfies: yes
F2: n=3 clauses=8 -> graph V=24 E=72, ask: independent set of size 8?
  SAT  : no (tries=8)
  IS   : no (search nodes=10799)

def satisfied(f, a):                     # verifier: O(m) for m clauses
    return all(any((a >> (abs(l) - 1) & 1) == (l > 0) for l in c) for c in f)

def run(name, f, n):
    k = len(f); V = 3 * k                 # vertex 3j+t = t-th literal of clause j
    lit = [l for c in f for l in c]
    adj = [0] * V; E = 0
    for u in range(V):
        for v in range(u + 1, V):
            if u // 3 == v // 3 or lit[u] == -lit[v]:   # triangle edge / conflict edge
                adj[u] |= 1 << v; adj[v] |= 1 << u; E += 1
    tries, sat = 0, None                  # side 1: try all 2^n assignments
    for a in range(1 << n):
        tries += 1
        if satisfied(f, a):
            sat = a; break
    nodes = 0                             # side 2: search for an independent set of size k
    def find(i, chosen, size):
        nonlocal nodes
        nodes += 1
        if size == k: return chosen
        if i == V or size + (V - i) < k: return None
        if not adj[i] & chosen:
            r = find(i + 1, chosen | 1 << i, size + 1)
            if r is not None: return r
        return find(i + 1, chosen, size)
    S = find(0, 0, 0)
    print(f"{name}: n={n} clauses={k} -> graph V={V} E={E}, ask: independent set of size {k}?")
    print("  SAT  :", "no" if sat is None else "yes x=" + "".join(str(sat >> i & 1) for i in range(n)), f"(tries={tries})")
    if S is None:
        print(f"  IS   : no (search nodes={nodes})")
        return
    print("  IS   : yes {" + " ".join(("~x" if lit[v] < 0 else "x") + str(abs(lit[v])) + f"@C{v // 3 + 1}" for v in range(V) if S >> v & 1) + f"}} (search nodes={nodes})")
    b = 0                                 # chosen literal = true; untouched variables = false
    for v in range(V):
        if S >> v & 1 and lit[v] > 0: b |= 1 << (lit[v] - 1)
    print("  IS -> x=" + "".join(str(b >> i & 1) for i in range(n)), "satisfies:", "yes" if satisfied(f, b) else "no")

run("F1", [[1, 2, 3], [-1, -2, 3], [1, -2, -3]], 3)
run("F2", [[1, 2, 3], [-1, 2, 3], [1, -2, 3], [-1, -2, 3],          # every sign pattern
          [1, 2, -3], [-1, 2, -3], [1, -2, -3], [-1, -2, -3]], 3)

F1: n=3 clauses=3 -> graph V=9 E=15, ask: independent set of size 3?
  SAT  : yes x=100 (tries=2)
  IS   : yes {x1@C1 ~x2@C2 x1@C3} (search nodes=8)
  IS -> x=100 satisfies: yes
F2: n=3 clauses=8 -> graph V=24 E=72, ask: independent set of size 8?
  SAT  : no (tries=8)
  IS   : no (search nodes=10799)

৬ · Independent set, vertex cover আর clique — একই সমস্যার তিন চেহারা

Independent set NP-complete হয়ে গেলে আরও দুটি সমস্যা প্রায় বিনামূল্যে আসে। একটি গ্রাফ G = (V, E), |V| = n.

• Independent set ↔ vertex cover: S independent ⇔ V \ S একটি vertex cover. কারণ: S-এর ভেতরে কোনো edge নেই ⇔ প্রতিটি edge-এর অন্তত এক প্রান্ত S-এর বাইরে ⇔ বাইরের অংশ সব edge ছোঁয়। তাই “k আকারের independent set আছে?” ⇔ “n − k আকারের vertex cover আছে?” রূপান্তর: (G, k) ↦ (G, n − k) — O(1)!
• Independent set ↔ clique: Clique হলো এমন vertex-সেট যার প্রতিটি জোড়া যুক্ত — সবাই সবার বন্ধু। Complement graph Ḡ-তে ঠিক সেই জোড়াগুলো যুক্ত যারা G-তে যুক্ত নয়। S G-তে independent ⇔ S Ḡ-তে clique. রূপান্তর: (G, k) ↦ (Ḡ, k) — O(n²).

এখানে একটি সূক্ষ্মতা আছে, যা ইন্টারভিউতে প্রায়ই ধরা হয়। সাধারণ গ্রাফে vertex cover NP-complete, কিন্তু bipartite গ্রাফে König-এর উপপাদ্য অনুযায়ী সর্বনিম্ন vertex cover = maximum matching, যা পর্ব ৪৭-এর flow বা Hopcroft–Karp দিয়ে polynomial সময়ে পাওয়া যায়। একইভাবে tree-তে maximum independent set একটি সরল tree DP (পর্ব ৫৫)। “সমস্যাটি NP-hard” কথাটি সবসময় সাধারণ ইনপুটের কথা — বিশেষ গঠনের ইনপুটে সহজ হতেই পারে।

৭ · Hamiltonian cycle → TSP, আর subset sum-এর “প্রায়-polynomial” ফাঁদ

Hamiltonian cycle (প্রতিটি vertex ঠিক একবার ছুঁয়ে শুরুতে ফেরা) Karp-এর তালিকায় NP-complete. এখন TSP-এর decision রূপ: “ওজনসহ complete graph-এ মোট খরচ B বা কম এমন একটি tour আছে কি?” Reduction: Hamiltonian cycle-এর গ্রাফ H (n টি vertex) থেকে complete graph বানান — H-এর edge-এর ওজন 1, বাকি সব জোড়ার ওজন 2; B = n.

এই রূপান্তরের একটি গভীর ফল আছে: ওজন 2-এর জায়গায় খুব বড় একটি সংখ্যা দিলে দেখা যায়, সাধারণ TSP-তে “সর্বোত্তমের কাছাকাছি” উত্তর দেওয়াও NP-hard — যদি না ওজনগুলো triangle inequality মানে। সেই গল্প পর্ব ৬৬-তে।

Subset sum আর knapsack — pseudo-polynomial মানে polynomial নয়

Subset sum (n টি ধনাত্মক সংখ্যার কোনো subset-এর যোগফল ঠিক T কি না) Karp-এর তালিকার knapsack-এর একটি রূপ, আর NP-complete. কিন্তু পর্ব ৫৩-এ আপনি এর একটি O(n · T) DP লিখেছেন! তাহলে কি P = NP প্রমাণ হয়ে গেল? না। “ইনপুটের আকার” মানে ইনপুট লিখতে কতগুলো bit লাগে। T লিখতে লাগে মাত্র প্রায় log₂ T টি bit; ধরুন সেটি b. তাহলে T ≈ 2ᵇ, আর O(n · T) = O(n · 2ᵇ) — ইনপুটের দৈর্ঘ্যে exponential. T = ১০^৬ হলে DP দারুণ; কিন্তু T-তে ৩০টি অঙ্ক থাকলে (b ≈ ১০০) টেবিলের আকার ১০^৩০-এর ঘরে। এমন সময়কে বলে pseudo-polynomial: সংখ্যাগুলোর মানে polynomial, ইনপুটের দৈর্ঘ্যে নয়। একই কথা 0/1 knapsack-এর O(n · W)-এর জন্যও।

৮ · P = NP? — co-NP, পুরস্কার আর কেন প্রশ্নটি এত গুরুত্বপূর্ণ

co-NP — “না” উত্তরের প্রমাণ

NP-এর সংজ্ঞা অসমমিত: শুধু “হ্যাঁ”-এর ছোট প্রমাণ চাই। “এই সূত্র কখনোই সত্য হয় না” বা “এই গ্রাফে কোনো Hamiltonian cycle নেই” — এর ছোট প্রমাণ কী? সব সম্ভাবনা দেখানো ছাড়া কোনো উপায় জানা নেই। যেসব সমস্যার “না” উত্তরের ছোট, দ্রুত-যাচাইযোগ্য প্রমাণ আছে, তারা co-NP — সমতুল্যভাবে, যাদের complement (হ্যাঁ আর না অদলবদল) NP-তে। UNSAT (সূত্রটি unsatisfiable কি না) co-NP-তে। P ⊆ NP ∩ co-NP, কারণ polynomial সমাধান দুই দিকের উত্তরই দেয়। NP = co-NP কি না, সেটিও অজানা; অনেকে মনে করেন সমান নয়, আর P = NP হলে সমান হতেই হতো। একটি সুন্দর উদাহরণ: “n কি মৌলিক?” প্রশ্নটি NP ∩ co-NP-তে বহু আগেই জানা ছিল (১৯৭৫ সালে Vaughan Pratt দেখান মৌলিকতারও ছোট certificate আছে) — আর ২০০২ সালে Agrawal, Kayal আর Saxena প্রমাণ করেন এটি P-তেই।

প্রশ্নটি আর তার দাম

২০০০ সালে Clay Mathematics Institute সাতটি “Millennium Prize Problems” ঘোষণা করে, প্রতিটির সমাধানে ১০ লাখ মার্কিন ডলার পুরস্কার; P বনাম NP তার একটি। (সাতটির মধ্যে এখন পর্যন্ত শুধু Poincaré conjecture সমাধান হয়েছে, Grigori Perelman-এর হাতে।) প্রশ্নটি কেন এত গুরুত্বপূর্ণ:

• যদি P = NP (আর অ্যালগরিদমটি বাস্তবে দ্রুত হয়): সময়সূচি, রুট, chip-এর নকশা, প্রোটিনের গঠনের মতো হাজারো optimization প্রশ্ন দ্রুত সমাধানযোগ্য হতো। গণিতের যেকোনো উপপাদ্যের, যার যুক্তিসংগত দৈর্ঘ্যের প্রমাণ আছে, প্রমাণ খুঁজে পাওয়া যাচাই করার মতোই সহজ হয়ে যেত। আবার আজকের প্রায় সব public-key cryptography ভেঙে পড়ত — গোপন চাবি পেলে যাচাই করা সহজ, তাই “গোপন চাবি খোঁজা” একটি NP প্রশ্ন। bKash লেনদেন থেকে ব্যাংকের ওয়েবসাইট পর্যন্ত নিরাপত্তা এই “খোঁজা কঠিন” অনুমানের ওপর দাঁড়িয়ে।
• যদি P ≠ NP: হাজারো NP-complete সমস্যার কোনোটিরই polynomial অ্যালগরিদম নেই — তখন আমাদের কাজ approximation, heuristic, বিশেষ গঠন আর exponential কিন্তু চতুর অ্যালগরিদম (পর্ব ৬৫–৬৬)। প্রমাণটি নিজেই সম্ভবত গণনা সম্পর্কে নতুন গভীর ধারণা দেবে।

গবেষকরা কী মনে করেন: William Gasarch ২০০২, ২০১২ আর ২০১৯ সালে গবেষকদের মধ্যে জরিপ করেন; প্রতিবার বেশিরভাগ উত্তরদাতা মনে করেছেন P ≠ NP, আর সেই অংশ সময়ের সাথে বেড়েছে। কিন্তু এটি বিশ্বাস, প্রমাণ নয় — ইতিহাসে বিশেষজ্ঞদের ধারণা ভুলও হয়েছে। নিয়মিতভাবে “P = NP প্রমাণ করেছি” বা “P ≠ NP প্রমাণ করেছি” দাবি আসে; এখন পর্যন্ত কোনোটি বিশেষজ্ঞদের যাচাইয়ে টেকেনি।

মাঝখানে কিছু আছে কি? — NP-intermediate

১৯৭৫ সালে Richard Ladner প্রমাণ করেন: P ≠ NP হলে NP-তে এমন সমস্যা অবশ্যই আছে যা P-তেও নয়, NP-complete-ও নয় — NP-intermediate. কোন স্বাভাবিক সমস্যা এমন, তা নিশ্চিত জানা নেই (জানলে P ≠ NP প্রমাণ হয়ে যেত), কিন্তু দুটি প্রধান সন্দেহভাজন:

• Integer factorization (decision রূপে: “N-এর কি k-এর চেয়ে ছোট কোনো উৎপাদক আছে?”) — NP ∩ co-NP-তে, তাই NP-complete হলে NP = co-NP হয়ে যেত, যা অনেকে অসম্ভাব্য মনে করেন। RSA-এর নিরাপত্তা এর কঠিনতার ওপর নির্ভর করে। ১৯৯৪ সালে Peter Shor দেখান যে quantum কম্পিউটারে factorization polynomial সময়ে হয় — কিন্তু তাতে NP-complete সমস্যা সহজ হয় এমন কোনো প্রমাণ নেই।
• Graph isomorphism — দুটি গ্রাফ কি একই, শুধু vertex-এর নাম আলাদা? ২০১৫ সালে László Babai একটি quasi-polynomial (প্রায় n^(log n)-এর ধাঁচের) অ্যালগরিদম ঘোষণা করেন — polynomial নয়, কিন্তু exponential-এর চেয়ে অনেক কম।

৯ · ইন্টারভিউ আর কনটেস্টে NP-hard সমস্যা চেনা

বাস্তবে আপনি প্রায় কখনো NP-completeness-এর আনুষ্ঠানিক প্রমাণ লিখবেন না। কিন্তু একটি সমস্যা পড়ে “এটি আসলে vertex cover / TSP / subset sum-এর ছদ্মবেশ” চিনতে পারা অনেক ঘণ্টা বাঁচায় — আপনি polynomial সমাধান খোঁজা বন্ধ করে সঠিক প্রশ্ন করেন: সীমাগুলো কী বলছে? কনটেস্টের সমস্যা-রচয়িতা NP-hard সমস্যা দিলে সবসময় কোনো একটি ছাড় রাখেন।

শেষ সারিটি সবচেয়ে কাজের। “Longest simple path” NP-hard, কিন্তু DAG-এ longest path O(V + E). “Graph colouring” NP-hard, কিন্তু ২টি রঙে bipartite পরীক্ষা O(V + E). সাধারণ SAT কঠিন, 2-SAT সহজ। সমস্যার নাম শুনে নয়, তার সীমা আর গঠন দেখে সিদ্ধান্ত নিন। আর ইন্টারভিউতে “এর polynomial সমাধান জানা নেই, কারণ এটি vertex cover-এর সমতুল্য; n ছোট হলে bitmask, বড় হলে 2-approximation” — এমন একটি উত্তর প্রায়ই পুরো কোডের চেয়েও বেশি নম্বর আনে।

১০ · AI-এর যুগে complexity — দাবি নয়, reduction যাচাই করুন

AI সহকারীকে একটি নতুন সমস্যা দিলে দুই রকম ভুল প্রায়ই দেখা যায়। এক, একটি আত্মবিশ্বাসী “O(n²) greedy” সমাধান, যা আসলে একটি NP-hard সমস্যার ভুল সমাধান — ছোট উদাহরণে চলে, বড় বা চতুর ইনপুটে ভুল উত্তর দেয়। দুই, উল্টোটা: সহজ একটি সমস্যাকে “এটি NP-hard, তাই brute force ছাড়া উপায় নেই” বলে দেওয়া, যদিও সীমা বা গঠন একটি polynomial পথ খুলে রেখেছে। Reduction-এর প্রমাণেও AI দিক উল্টে ফেলে, বা ⇔-এর এক দিক বাদ দেয়।

Complexity-র দাবি যাচাইয়ের চেকলিস্ট

• সমস্যাটির decision রূপ লিখেছি, আর certificate কী ও verifier কত সময় নেয় তা বলতে পারি
• Reduction জানা NP-complete সমস্যা থেকে নতুনটিতে, আর দুই দিকের (⇔) প্রমাণই আছে
• রূপান্তরের সময় ইনপুটের দৈর্ঘ্যে polynomial; সংখ্যার মান নয়, bit-সংখ্যা গুনেছি
• AI-এর “দ্রুত” সমাধান ছোট এলোমেলো ইনপুটে brute force-এর সাথে মিলিয়েছি — stress testing; ছোট reduction হাতে trace করেছি
• সীমা আর বিশেষ গঠন (ছোট n, ছোট মান, tree, bipartite, দুই-চলকের শর্ত) খুঁজেছি — edge case-সহ