နောက်ဆက်တွဲ ၁ - P, NP, NP-Hard, NP-Complete

ဒီစာအုပ်တစ်လျှောက် — ပြဿနာတစ်ခုကို ပိုမြန်အောင် ($O(n^2) → O(n \log n) → O(n)$) ဖြေနည်းတွေ လေ့လာခဲ့ပါတယ်။ ဒါပေမယ့် developer အနေနဲ့ တစ်ခါတစ်ရံ — ဘယ်လို optimize လုပ်လုပ် မြန်အောင် မရတဲ့ ပြဿနာတွေ တွေ့ရတယ်။ ဥပမာ — "delivery truck တစ်စီးက မြို့ ၂၀ ကို အကုန်လည်ပြီး အတိုဆုံး လမ်းနဲ့ ပြန်ရောက်ဖို့" — ဒါက ရိုးရှင်းသလို ထင်ရပေမယ့် — တကယ်တမ်း computer အကြီးတွေတောင် အချိန်ကုန် မဖြေနိုင်တဲ့ ပြဿနာ ဖြစ်နေတယ်။

ဘာကြောင့်လဲ? ဒီနောက်ဆက်တွဲမှာ — ဘယ် ပြဿနာတွေက "လွယ်" ပြီး ဘယ်ဟာတွေက တကယ် "ခက်" လဲ ဆိုတဲ့ theory ကို — developer အတွက် လိုအပ်သလောက်သာ ရှင်းပြပါမယ်။ ဒါက အဓိက သင်ခန်းစာ တစ်ခု ပေးတယ် — ပြဿနာ တိုင်းမှာ ပြီးပြည့်စုံတဲ့ မြန်တဲ့ အဖြေ မရှိဘူး၊ တစ်ခါတစ်ရံ "လုံလောက်တဲ့ အဖြေ (good enough)" ကို လက်ခံတတ်ဖို့ လိုတယ်။

မှတ်ရန်: ဒီအပိုင်းက main learning flow မဟုတ်ဘဲ — appendix ပါ။ academic proof တွေ မဟုတ်ဘဲ — "ဒီ ပြဿနာ ခက်လား၊ ခက်ရင် ဘာလုပ်မလဲ" ဆိုတာ ဆုံးဖြတ်နိုင်ဖို့ အဆင့်ထိပဲ ရှင်းပြပါမယ်။

Brute Force Explosion — ဘာကြောင့် တချို့ ပြဿနာ ခက်လဲ

ပြဿနာ တချို့ ခက်ရတဲ့ အကြောင်းရင်းက — ဖြစ်နိုင်ခြေ (possibilities) အရေအတွက်က input ကြီးလာတာနဲ့ ပေါက်ကွဲ (explode) သွားလို့ပါ။

မြို့ n မြို့ကို လည်တဲ့ လမ်းကြောင်း (Traveling Salesman) ကို ကြည့်ရအောင် — ဖြစ်နိုင်တဲ့ လမ်းကြောင်း အရေအတွက်က n! (factorial) —

n = 25 ဆိုရင် — တစ်စက္ကန့်မှာ လမ်းကြောင်း သန်းပေါင်း ၁,၀၀၀ စစ်နိုင်တဲ့ computer နဲ့တောင် — စကြဝဠာ သက်တမ်းထက် ကြာမယ်။ ဒါက "brute force explosion" — ဖြစ်နိုင်ခြေ အကုန် စစ်တဲ့ နည်းက input နည်းနည်း ကြီးတာနဲ့ လက်တွေ့ မဖြစ်နိုင်တော့တာပါ။

ဒီလို ပြဿနာတွေကို — computer scientist တွေက အုပ်စု ဖွဲ့ပြီး အမည် ပေးထားတယ် — P, NP, NP-Hard, NP-Complete။

P — လွယ်တဲ့ ပြဿနာ (အမြန် ဖြေနိုင်)

P (Polynomial time) = polynomial time ($O(n)$, $O(n^2)$, $O(n^3)$ ...) နဲ့ ဖြေနိုင်တဲ့ ပြဿနာတွေ။ ဒီစာအုပ်က ပြဿနာ အများစုဟာ P ထဲ ပါတယ် —

• list ကို sort လုပ် ($O(n \log n)$)
• array ထဲ element ရှာ ($O(n)$ / $O(\log n)$)
• graph မှာ shortest path (Dijkstra — $O(E \log V)$)

P ပြဿနာတွေက — input ကြီးလာရင် အချိန် "သင့်တင့်စွာ" တိုးတယ် (ပေါက်ကွဲ မသွား)။ ဒါတွေက "လက်တွေ့ ဖြေနိုင်တဲ့" (tractable) ပြဿနာတွေပါ။

NP — အဖြေ မှန်မမှန် အမြန် စစ်နိုင်

NP (Nondeterministic Polynomial time) = အဖြေ တစ်ခု ပေးထားရင် — အဲ့ဒါ မှန်မမှန်ကို polynomial time နဲ့ အမြန် စစ်နိုင်တဲ့ ပြဿနာတွေ။

အရေးကြီးတဲ့ ကွဲပြားချက်က — "ဖြေဖို့" ခက်ပေမယ့် "စစ်ဖို့" လွယ်တာ —

   Sudoku ဥပမာ —
   ဖြေဖို့:    ဆဲလ် အကုန် မှန်အောင် ဖြည့်ဖို့ — ဖြစ်နိုင်ခြေ အများကြီး စစ်ရ (ခက်)
   စစ်ဖို့:    ဖြည့်ပြီးသား Sudoku တစ်ခု မှန်မမှန် — တန်း/ကော်လံ/box စစ်ရုံ (လွယ်, polynomial)

NP ထဲမှာ — P ပြဿနာ အကုန် ပါတယ် (မြန်မြန် ဖြေနိုင်ရင် — မြန်မြန် စစ်နိုင်တာ သေချာ)။ ဒါပေမယ့် "ဖြေဖို့လည်း လွယ်ရဲ့လား" (P = NP လား) ဆိုတာ — computer science ရဲ့ အဖြေမရှိသေးတဲ့ အကြီးမားဆုံး မေးခွန်းပါ ($1 သန်း ဆုကြေး ရှိ)။ အများစုက "P ≠ NP" (ဖြေဖို့ တကယ် ခက်တယ်) လို့ ယုံကြတယ်။

NP-Hard — အနည်းဆုံး NP လောက် ခက်

NP-Hard = NP ထဲက ပြဿနာ အကုန်လုံး လောက် (အနည်းဆုံး) ခက်တဲ့ ပြဿနာတွေ။ ဒါတွေက — အဖြေ စစ်ဖို့တောင် polynomial time နဲ့ မရနိုင်တာ ပါနိုင်တယ် (NP ထဲ မပါတာ ပါ ပါနိုင်)။

ဥပမာ — Traveling Salesman (TSP) ရဲ့ optimization version ("အတိုဆုံး လမ်းကြောင်း ရှာ") က NP-Hard ပါ — ပေးထားတဲ့ လမ်းကြောင်း တစ်ခုက "အတိုဆုံး ဟုတ်မဟုတ်" စစ်ဖို့တောင် — ကျန်တဲ့ လမ်းကြောင်း အကုန်နဲ့ နှိုင်းရလို့ ခက်တယ်။

NP-Complete — အခက်ဆုံး NP ပြဿနာများ

NP-Complete = NP ထဲမှာ ပါပြီး၊ NP-Hard လည်း ဖြစ်တဲ့ ပြဿနာတွေ — ဆိုလိုတာ "NP ထဲက အခက်ဆုံး" ပြဿနာတွေ —

   NP-Complete = NP  ∩  NP-Hard
                 (NP ထဲ ပါ)   (NP လောက် ခက်)

အရေးကြီးတဲ့ ဂုဏ်သတ္တိ — NP-Complete ပြဿနာ တစ်ခုကို polynomial time နဲ့ ဖြေနိုင်ရင် — NP ပြဿနာ အကုန်လုံးကို ဖြေနိုင်မယ် (P = NP ဖြစ်သွားမယ်)။ ဒါပေမယ့် အခုထိ ဘယ်သူမှ မရှာနိုင်သေး။ ဥပမာ NP-Complete ပြဿနာတွေ — Sudoku (general)၊ Boolean satisfiability (SAT)၊ Knapsack (decision)၊ Graph coloring။

ဆက်စပ်ပုံ Diagram

• P ⊆ NP — P က NP ထဲ (ဖြေနိုင်ရင် စစ်နိုင်တာ သေချာ)
• NP-Complete = NP ∩ NP-Hard — NP ထဲက အခက်ဆုံး subset
• TSP-optimize က NP-Hard ဖြစ်ပေမယ့် NP ထဲ မပါ

ခက်တဲ့ ပြဿနာ တွေ့ရင် — ဘာလုပ်မလဲ

NP-Hard / NP-Complete ပြဿနာ တွေ့ရင် — "ပြီးပြည့်စုံတဲ့ အဖြေ" ကို အချိန်ကုန်ခံ ရှာနေမယ့်အစား — developer တွေက လက်တွေ့ နည်း ၂ မျိုး သုံးတယ်။

Approximation (ခန့်မှန်း အဖြေ)

"အကောင်းဆုံး မဟုတ်ပေမယ့် — အကောင်းဆုံးနဲ့ နီးစပ်တဲ့ အဖြေ"ကို polynomial time နဲ့ ရှာတာ။ ဥပမာ — TSP အတွက် "အတိုဆုံးထက် အများဆုံး ၂ ဆ မပိုတဲ့ လမ်းကြောင်း" ကို အမြန် ရှာပေးတဲ့ approximation algorithm ရှိတယ်။

Heuristic (အတွေ့အကြုံ နည်းလမ်း)

"အမြဲ မှန်တယ်လို့ အာမ မခံပေမယ့် — လက်တွေ့မှာ ကောင်းတဲ့ အဖြေ ပေးလေ့ရှိတဲ့" rule of thumb။ ဥပမာ — TSP အတွက် greedy heuristic: "အခု ရှိတဲ့ မြို့ကနေ — အနီးဆုံး မြို့ကို အရင်သွား" (nearest neighbor)။ အမြဲ အကောင်းဆုံး မဟုတ်ပေမယ့် — အလွန် မြန်ပြီး၊ လက်တွေ့ လုံလောက်တဲ့ အဖြေ ပေးတယ်။

// TSP — Nearest Neighbor heuristic (အကောင်းဆုံး မဟုတ်၊ ဒါပေမယ့် မြန် + good enough)
int nearestNeighborTour(int[][] dist, int start) {
    int n = dist.length;
    boolean[] visited = new boolean[n];
    int cur = start, total = 0;
    visited[start] = true;
    for (int step = 1; step < n; step++) {
        int next = -1, best = Integer.MAX_VALUE;
        for (int j = 0; j < n; j++) {           // အနီးဆုံး မ visit ရသေးတဲ့ မြို့
            if (!visited[j] && dist[cur][j] < best) {
                best = dist[cur][j];
                next = j;
            }
        }
        visited[next] = true;
        total += best;
        cur = next;
    }
    return total + dist[cur][start];            // start ဆီ ပြန်
}

ဒီ heuristic က $O(n^2)$ ပဲ — n=25 အတွက်တောင် ချက်ချင်း ပြီးတယ် (brute force က စကြဝဠာ သက်တမ်း)။ အဖြေက "အတိုဆုံး" မဟုတ်ပေမယ့် — လက်တွေ့ delivery app တွေမှာ ဒီလို heuristic + optimization တွေ ပေါင်းသုံးကြတာပါ။

Real-world Examples

ဒီ "ခက်တဲ့" ပြဿနာတွေက — academic theory မဟုတ်ဘဲ — developer တွေ နေ့စဉ် တွေ့ရတဲ့ ပြဿနာတွေပါ —

• Scheduling — ဝန်ထမ်း shift, meeting room, CPU job ကို အကောင်းဆုံး စီစဉ်ဖို့ — constraint များလာရင် NP-Hard (လက်တွေ့မှာ heuristic သုံး)။
• Route Optimization — delivery, logistics ("မြို့ အကုန် လည်ပြီး အတိုဆုံး") — TSP — NP-Hard (Google Maps, ride-share က approximation သုံး)။
• Resource Allocation — server / cloud capacity ကို request တွေဆီ အကောင်းဆုံး ခွဲဝေ — Bin Packing / Knapsack — NP-Hard။
• Traveling Salesman Problem (TSP) — အထက်ပါ အားလုံးရဲ့ "ပုံစံ" — NP-Hard ရဲ့ classic ဥပမာ။

Practical Message — Developer အတွက် သင်ခန်းစာ

ဒီနောက်ဆက်တွဲရဲ့ အဓိက ရည်ရွယ်ချက်က — proof တွေ ကျက်ဖို့ မဟုတ်ဘဲ — developer အနေနဲ့ ဆုံးဖြတ်ချက် ချနိုင်ဖို့ပါ —

1. ပြဿနာ တိုင်းမှာ ပြီးပြည့်စုံ မြန်တဲ့ အဖြေ မရှိ — တချို့ ပြဿနာတွေက အခြေခံကတည်းက ခက်တယ် (NP-Hard)။ ကိုယ့်ဘက်က code မညံ့လို့ မဟုတ်။
2. "ခက်တဲ့ ပြဿနာ" ဆိုတာ မှတ်မိဖို့ — ပြဿနာတစ်ခု TSP / scheduling / packing ပုံစံ ဆိုရင် — "perfect solution" ရှာနေမယ့်အစား — approximation / heuristic ဆီ ချက်ချင်း ကူးတာ ပိုသင့်တယ်။
3. "Good enough" ကို လက်ခံတတ်ဖို့ — လက်တွေ့ business မှာ — "၉၅% အကောင်းတဲ့ အဖြေ ၁ စက္ကန့်" က "၁၀၀% အဖြေ ၁ နှစ်နဲ့" ထက် အများကြီး တန်ဖိုးရှိတယ်။
4. ဘယ်တော့ optimize ရပ်ရမလဲ သိဖို့ — over-engineering မလုပ်ဘဲ — ပြဿနာရဲ့ သဘာဝ ခက်ခဲမှုကို နားလည်ပြီး — အချိန်/အရင်းအမြစ်ကို သင့်တော်စွာ သုံးတတ်ဖို့။