တဳအဝ်ရဳ ပရေင်ချပ်ဂၞန်
တဳအဝ်ရဳ ပရေင်ချပ်ဂၞန် (အၚ်္ဂလိက်: Computational complexity theory) ဟီုမ္ဂးဂှ် ဒှ် ကဏ္ဍမွဲ ပ္ဍဲကဵု သိပ္ပံကောန်ပျူတာ မဆေင်ကဵု တဳအဝ်ရဳ (Theoretical computer science) ကေုာံ သင်္ချာ (Mathematics) မအာရီုစွံ လတူ ပရေင်ပါ်ကရေက် ကေုာံ ပရေင်သ္ၚေဝ်ဂၠေပ် ပြသၞာ ပရေင်ချပ်ဂၞန် (Computational problems) အတိုင် အကာဲအရာ မဇြိုင် ဟွံသေင်မ္ဂး မလောဲ သွက် ကောန်ပျူတာ တအ် ဂွံ သောင်ကလး ရ။ တဳအဝ်ရဳ ဏအ်ဝွံ လ္ၚတ် ပရူ ဒဒှ်ရ သွက်ဂွံ သောင်ကလး ပြသၞာ မွဲမွဲ ဂှ် နွံပၟိက် အခိင် (Time) ဗလိုင်လဵု ကေုာံ ဒၞာဲ သီသိပ် (Space/Memory) ဗလိုင်လဵု ရော ဂှ်ရ။[၁]
ဘာသာရပ် ဏအ်ဝွံ ပြံင်လှာဲ လညာတ် မဟီုတွံ ဒဒှ်ရ "ပြသၞာ အိုတ်သီု မာန် သောင်ကလး နကဵု ကောန်ပျူတာ" ဂှ် တုဲ၊ ထ္ၜးကဵု သက်သဳ ဒဒှ်ရ ပြသၞာ လ္ၚဵုတအ်ဂှ် ၜိုန်ရ မာန် သောင်ကလး ကီုလေဝ်၊ ဍေဟ်တအ် ကေတ် အခိင် မဂၠိုင် ကဵု အသင်္ချေယျ သၞာံ (Billions of years) မာန် ရ။ ပြသၞာ P = NP မဒှ် ပြသၞာ အဓိကအိုတ် ပ္ဍဲ သိပ္ပံ ကောန်ပျူတာ ဂှ်လေဝ် ကတဵုဒှ် ကၠုင် နူကဵု တဳအဝ်ရဳ ဏအ် ရ။
၁။ နိဒါန် ကေုာံ ပွံက်အဓိပ္ပါယ် (Introduction and Definition)
[ပလေဝ်ဒါန် | ပလေဝ်ဒါန် တမ်ကၞက်]တဳအဝ်ရဳ ပရေင်ချပ်ဂၞန် (Computational complexity theory) ဂှ် ဒးပါ်ခြာ ကေတ် နူကဵု တဳအဝ်ရဳ ပရေင်တွက်ဂွံ (Computability theory) ရ။ တဳအဝ်ရဳ ပရေင်တွက်ဂွံ ဂှ် သၟာန် ဇၟာန်သၟာန် ဒဒှ်ရ "ပြသၞာ ဏအ် တွက်ဂွံ ဟာ ဟွံမာန် ဟာ?" သၟးရ။ ဆဂး တဳအဝ်ရဳ ပရေင်ချပ်ဂၞန် ဂှ် သၟာန် ဇၟာန်သၟာန် ဒဒှ်ရ "ပြသၞာ ဏအ် ယဝ်ရ တွက်ဂွံ မ္ဂး၊ ဍေဟ် ကေတ် ဒြဟတ် ရိုဟ်ကၞက် (Resources) ဗလိုင်လဵု ရော?" ရ။
ဒြဟတ် ရိုဟ်ကၞက် (Resources) အဓိက ၜါ သာ် မလ္ၚတ် ပ္ဍဲကဵု ဘာသာရပ် ဏအ်ဂှ် ဒှ်-
- အခိင် (Time): လၟိဟ် ကဆံင် (Steps) သွက် အလ်ဂဝ်ရဳထမ် (Algorithm) မွဲ ဂွံ ကၠောန် တုဲဒှ်။
- ဒၞာဲ (Space): လၟိဟ် တင်ဂၞင် (Memory/RAM) မနွံပၟိက် သွက်ဂွံ ကၠောန် လၟေင်ကမၠောန် ဂှ်။
တၠပညာ တအ် ၜတ်ကၞာတ် ဒြဟတ် ရိုဟ်ကၞက် တအ်ဏအ် နဒဒှ် ဖှ်ေရှေန် (Function) မဆက်စပ် ကု ဇမၞော် တင်ဂၞင် လုပ် (Input size) မကော်စ $n$ ရ။ ဥပမာ သွက်ဂွံ ရုဲစှ် (Sort) စရင် မနွံကဵု လၟိဟ် $n$ မ ဂှ်၊ ကေတ် အခိင် $O(n \log n)$ ဟွံသေင်မ္ဂး $O(n^2)$ မာန် ရ။
၂။ ဝင် ကေုာံ ပရေင်ဇၞော်မောဝ် (History and Development)
[ပလေဝ်ဒါန် | ပလေဝ်ဒါန် တမ်ကၞက်]ပရေင်လ္ၚတ် မဆေင်ကဵု တဳအဝ်ရဳ ဏအ်ဝွံ စကတဵုဒှ် ကၠုင် ပ္ဍဲ လဒေါဝ် သၞာံ ၁၉၆၀ တအ် ရ။ ပ္ဍဲ သၞာံ ၁၉၆၅ ဂှ် တၠပညာ သင်္ချာ ဂျူရဳ ဟာတ်မာနဳစ် (Juris Hartmanis) ကေုာံ ရဳချာတ် သတန် (Richard Stearns) တအ် ပတိတ် လိက်သုတေသန မွဲ မနွံယၟု "On the Computational Complexity of Algorithms" ရ။ လိက်ဏအ်ဝွံ ဖန်ဗဒှ် လဝ် လညာတ် ဒဒှ်ရ ပြသၞာ တအ်ဂှ် ပါ်ကရေက် နကဵု ဂကောံ (Classes) အတိုင် အခိင် ဍေဟ်တအ် မနွံပၟိက် ရ။[၂]
ကြဴနူဂှ် ပ္ဍဲ သၞာံ ၁၉၇၁ ဂှ် သတဳဗေန် ကွတ် (Stephen Cook) ကေုာံ လဳယဝ်နစ် လဳဗေန် (Leonid Levin) တအ် ထ္ၜးကဵု သက်သဳ တွဵု (Theorem) မကော်စ "Cook-Levin theorem" မဟီုတွံ ဒဒှ်ရ ပြသၞာ Boolean satisfiability problem (SAT) ဂှ် ဒှ် ပြသၞာ ဇြိုင်အိုတ် ပ္ဍဲ ဂကောံ $\mathcal{NP}$ ရ။ လညာတ် ဏအ်ဝွံ ဒှ် တမ်ရိုဟ် သွက် ပြသၞာ $\mathcal{P}$ vs $\mathcal{NP}$ မပြာကတ် ဒၟံင် စဵုကဵု တ္ၚဲဏအ် ရ။
၃။ မဝ်ဒယ် ပရေင်ချပ်ဂၞန် ကေုာံ စက်တူရိန် (Computational Models and Turing Machines)
[ပလေဝ်ဒါန် | ပလေဝ်ဒါန် တမ်ကၞက်]သွက်ဂွံ သ္ၚေဝ်ဂၠေပ် အခိင် ကေုာံ ဒၞာဲ ဗွဲမချိုတ်ပၠိုတ် ဂှ်၊ ပိုယ် နွံပၟိက် "မဝ်ဒယ် သင်္ချာ" (Mathematical model) သွက် ကောန်ပျူတာ ရ။ မဝ်ဒယ် မစကာ ဂၠိုင်အိုတ် ဂှ် ဒှ် စက် တူရိန် (Turing machine) ရ။
စက် တူရိန် ဝွံ ပါ်လဝ် ၜါ သာ် -
- Deterministic Turing Machine (DTM): ပ္ဍဲ ဇၟာပ် ကဆံင်၊ စက် ဏအ် နွံကဵု ဂၠံင်တရဴ ဆ မွဲဓဝ် ဟေင် သွက်ဂွံ ဆက်အာ။ ဍေဟ် တုပ် ကဵု ကောန်ပျူတာ ဓမ္မတာ မပိုယ် စကာ ဒၟံင် တ္ၚဲဏအ် ရ။
- Non-deterministic Turing Machine (NTM): ပ္ဍဲ ဇၟာပ် ကဆံင်၊ စက် ဏအ် မာန် ရုဲစှ် ဂၠံင်တရဴ ဗွဲမဂၠိုင် မွဲစွံ (Guessing)။ ယဝ်ရ သွဟ် ဍာံပြ နွံမ္ဂး၊ စက် ဏအ် တီ ကေတ် ဂၠံင်တရဴ ဂှ် ဗွဲမပြဟ် ရ။ (ဍေဟ်ဝွံ ဒှ် မဝ်ဒယ် အာဗ်သတြက် သက်သက် သွက် လညာတ် သဳအိုရဳ ရ)။
၄။ အခိင် ကေုာံ ဒၞာဲ (Time and Space Complexity)
[ပလေဝ်ဒါန် | ပလေဝ်ဒါန် တမ်ကၞက်]ပရေင်ၜတ်ကၞာတ် အခိင် (Time) ကေုာံ ဒၞာဲ (Space) ဂှ် စကာ သင်္ကေတ Big O notation (Big O notation) ရ။ သင်္ကေတ ဏအ်ဝွံ ထ္ၜးကဵု လၟေင် ဇၞော်မောဝ် (Growth rate) သွက် ဖှ်ေရှေန် မွဲ ရ။
- Polynomial time ($O(n^k)$): အခိင် မဇၞော်မောဝ် တိုန် နကဵု ပဝ်လဳနဝ်မဳယာယ်။ ဥပမာ $O(n^2)$ ဟွံသေင်မ္ဂး $O(n^3)$။ ပြသၞာ မနွံ အခိင် သာ်ဏအ် ဂှ် စၟတ်သမ္တီ ဒဒှ်ရ "သောင်ကလး မာန် ပြဟ်ပြဟ်" (Tractable) ရ။
- Exponential time ($O(2^n)$): အခိင် မဇၞော်မောဝ် တိုန် နကဵု အိတ်သပဝ်နေန်ရှေယ်။ ဥပမာ - ယဝ်ရ တင်ဂၞင် လုပ် $n$ ထပ်ဇၞော် တိုန် မွဲ ဆ မ္ဂး၊ အခိင် ဒးစကာ ထပ်ဇၞော် တိုန် ၜါ ဆ ရ။ ပြသၞာ သာ်ဏအ် ဂှ် စၟတ်သမ္တီ ဒဒှ်ရ "သောင်ကလး ဟွံမာန် ပ္ဍဲ အခိင် ဂၠေအ်အ်" (Intractable) ရ။
၅။ ဂကောံ ပြသၞာ P ကေုာံ NP (Complexity Classes P and NP)
[ပလေဝ်ဒါန် | ပလေဝ်ဒါန် တမ်ကၞက်]ဂကောံ ပြသၞာ (Complexity classes) ဝွံ ဒှ် အရာ အဓိကအိုတ် ပ္ဍဲ တဳအဝ်ရဳ ပရေင်ချပ်ဂၞန် (Computational complexity theory) ရ။
- ဂကောံ $\mathcal{P}$ (Polynomial time): ဒှ် ဂကောံ ပြသၞာ အိုတ်သီု မမာန် သောင်ကလး ပြဟ်ပြဟ် နကဵု DTM ပ္ဍဲ အခိင် ပဝ်လဳနဝ်မဳယာယ် ရ။ (ဥပမာ - ပရေင်ပတၟောအ် ဂၞန်၊ ပရေင်ဂၠာဲ တင်ဂၞင် ပ္ဍဲ စရင်)။
- ဂကောံ $\mathcal{NP}$ (Non-deterministic Polynomial time): ဒှ် ဂကောံ ပြသၞာ အိုတ်သီု ယဝ်ရ သွဟ် မွဲ ကဵုလဝ် မ္ဂး၊ မာန် "စၟတ်သမ္တီ" (Verify) ဒဒှ်ရ ဍာံ ဟွံဍာံ ပြဟ်ပြဟ် (ပ္ဍဲ အခိင် ပဝ်လဳနဝ်မဳယာယ်) နကဵု DTM ရ။ ဆဂး သွက်ဂွံ "ဂၠာဲ" (Solve) သွဟ် ဂှ် ကေတ် အခိင် ဂၠိုင် မာန် ရ။ (ဥပမာ - ပြသၞာ Sudoku ဇၞော်ဇၞော်။ ယဝ်ရ ကဵုလဝ် သွဟ်၊ ပိုယ် ရံင် တုဲ တီ ဒဒှ်ရ ဍာံ ပြဟ်ပြဟ် မာန်၊ ဆဂး သွက်ဂွံ စ တွက် နူ တမ် ဂှ် ဇြိုင်သန်)။[၃]
| ဂကောံ (Class) | ပရေင်သောင်ကလး (Solving) | ပရေင်စၟတ်သမ္တီ (Verifying) | ဥပမာ |
|---|---|---|---|
| $\mathcal{P}$ | လောဲသွာ (Polynomial time) | လောဲသွာ | ပရေင်ရုဲစှ် လၟေင် (Sorting) |
| $\mathcal{NP}$ | ဟွံတီ ဏီ (လဆောဝ် ဇြိုင်သန်) | လောဲသွာ (Polynomial time) | ပြသၞာ သောင်ကလး ပဟေဠိ (Sudoku) |
| $\mathcal{EXP}$ | ဇြိုင်သန် လောန် (Exponential) | ဇြိုင်သန် | တၠုင်လအာ ဂိမ်း ဇၞော်ဇၞော် (Chess) |
၆။ ပြသၞာ NP-Complete ကေုာံ NP-Hard (NP-Complete and NP-Hard Problems)
[ပလေဝ်ဒါန် | ပလေဝ်ဒါန် တမ်ကၞက်]ပ္ဍဲ အပ္ဍဲ ဂကောံ $\mathcal{NP}$ ဂှ်၊ နွံကဵု ပြသၞာ မဇြိုင်အိုတ် တအ် မကော်စ $\mathcal{NP}$-Complete ရ。
- $\mathcal{NP}$-Hard: ပြသၞာ မွဲ ဒှ် $\mathcal{NP}$-Hard ယဝ်ရ ပြသၞာ $\mathcal{NP}$ အိုတ်သီု တအ် မာန် ပြံင်လှာဲ စုတ် ပ္ဍဲ ပြသၞာ ဏအ် ပြဟ်ပြဟ် (Polynomial time reduction)။ သွဟ် ပြသၞာ ဏအ် မာန် သောင်ကလး ပြသၞာ $\mathcal{NP}$ သီုဖအိုတ် ရ။
- $\mathcal{NP}$-Complete: ပြသၞာ မွဲ ဒှ် $\mathcal{NP}$-Complete ယဝ်ရ ဍေဟ် ဒှ် သီု $\mathcal{NP}$ ကေုာံ သီု $\mathcal{NP}$-Hard ရ။
ဥပမာ သွက် ပြသၞာ $\mathcal{NP}$-Complete ဂှ် ဒှ် ပြသၞာ တၠဖျာ တရဴ (Traveling Salesperson Problem - TSP) ရ။ ယဝ်ရ တၠဖျာ မွဲ ဒးအာ ဍုင် ၁၀၀ ဍုင် မ္ဂး၊ သွက်ဂွံ ဂၠာဲ ဂၠံင် မဂၠေအ်အိုတ် ဂှ် ကောန်ပျူတာ ခေတ်လၟုဟ် တအ် ကေတ် အခိင် မဂၠိုင် နူ အာယုက် စကြဝဠာ ဏီ ရ။
၇။ ပရေင်ဆက်စပ် ပြသၞာ P = NP? (The P vs NP Problem)
[ပလေဝ်ဒါန် | ပလေဝ်ဒါန် တမ်ကၞက်]ပြသၞာ $\mathcal{P} = \mathcal{NP}$ ဂှ် ဒှ် ပြသၞာ မဟွံမာန် သောင်ကလး ဏီ (Unsolved problem) မပြာကတ်အိုတ် ပ္ဍဲ သိပ္ပံ ကောန်ပျူတာ ကေုာံ သင်္ချာ ရ။ ပြသၞာ ဏအ် သၟာန် ဒၟံင် ဒဒှ်ရ "ယဝ်ရ ပြသၞာ မွဲ စၟတ်သမ္တီ သွဟ် ပြဟ်ပြဟ် မာန် မ္ဂး၊ ပြသၞာ ဂှ် မာန် သောင်ကလး နူ တမ် ပြဟ်ပြဟ် မာန် ကီု ဟာ?" ရ။[၄]
ယဝ်ရ $\mathcal{P} = \mathcal{NP}$ ကတဵုဒှ် ဍာံပြ မ္ဂး၊ ဍေဟ် ပကဵု ညံင် ဂၠးတိ ဏအ် ပြံင်လှာဲ အာ ဗွဲမဇၞော် မာန် ရ။ ပရေင်ဂၠာဲ ဂဥုဲ တၟိ (Drug discovery)၊ ပရေင်သောင်ကလး ပရိုတိန် (Protein folding) တအ် မာန် ကၠောန် ဂွံ ပ္ဍဲ အခိင် မဂၠေအ်အိုတ် ရ။ ဆဂး တၠပညာ ဗွဲမဂၠိုင် ပတှ်ေ ကေတ် ဒဒှ်ရ $\mathcal{P} \neq \mathcal{NP}$ (ဟွံတုပ်) ရ။ ပြသၞာ ဏအ် ပါလုပ် ပ္ဍဲ စရင် Millennium Prize Problems မနွံကဵု လာပ် သြန် မွဲ ပြကောဋိ (1 Million USD) နူကဵု Clay Mathematics Institute ရ။
၈။ ပရေင်ဖအောန်ဖျေဟ် ကေုာံ ပရေင်ပြံင်လှာဲ (Reduction and Transformation)
[ပလေဝ်ဒါန် | ပလေဝ်ဒါန် တမ်ကၞက်]ပရေင်ဖအောန်ဖျေဟ် (Reduction) ဝွံ ဒှ် နဲကဲ အဓိက သွက်ဂွံ ထ္ၜး သက်သဳ ဒဒှ်ရ ပြသၞာ ၜါ ဂှ် နွံကဵု ကဆံင် မဇြိုင် တုပ်သၟဟ် ရ။
ယဝ်ရ ပိုယ် နွံ ပြသၞာ $A$ ကေုာံ ပြသၞာ $B$ တုဲ၊ ပိုယ် မာန် ပြံင်လှာဲ ပြသၞာ $A$ ညံင်ဂွံ ဒှ် ပြသၞာ $B$ ပ္ဍဲ အခိင် ပဝ်လဳနဝ်မဳယာယ် (Polynomial time) မ္ဂး၊ ပိုယ် ဟီု မာန် ဒဒှ်ရ "$A$ reduces to $B$" ($A \leq_p B$) ရ။ အရာဏအ် ထ္ၜးကဵု ဒဒှ်ရ ယဝ်ရ ပိုယ် တီ နဲကဲ သောင်ကလး $B$ မ္ဂး၊ ပိုယ် လေဝ် မာန် သောင်ကလး $A$ ရ။ နဲကဲ ဏအ်ဝွံ စကာ သွက်ဂွံ ထ္ၜး သက်သဳ ပြသၞာ တၟိ တအ် ဒဒှ် $\mathcal{NP}$-Complete ရ။
၉။ လွပ် ပ္ဍဲ ခရိပ်တဝ်ဂရပ်ဖဳ ကေုာံ ဂီုကၠီု (Applications in Cryptography and Security)
[ပလေဝ်ဒါန် | ပလေဝ်ဒါန် တမ်ကၞက်]ခရိပ်တဝ်ဂရပ်ဖဳ (Cryptography) ခေတ်လၟုဟ် ဗွဲမဂၠိုင် မပ္တံကဵု RSA အလ်ဂဝ်ရဳထမ် တအ်ဝွံ ဒုင်သဇိုင် လတူ လညာတ် ဒဒှ်ရ ပြသၞာ လ္ၚဵုတအ်ဂှ် သောင်ကလး ဇြိုင်သန် (Hard to solve) ရ။
RSA ဝွံ ဒုင်သဇိုင် လတူ ပရေင်ပါ်ကရေက် ဂၞန်သဇိုင် (Prime factorization) ရ။ ယဝ်ရ ပိုယ် ပတၟောအ် ဂၞန်သဇိုင် ဇၞော်ဇၞော် ၜါ မ မ္ဂး၊ ကလိဂွံ သွဟ် လောဲသွာ ရ။ ဆဂး ယဝ်ရ ကဵုလဝ် သွဟ် ဂှ် တုဲ သွက်ဂွံ ကလေင် ဂၠာဲ ဂၞန်သဇိုင် ၜါ မ ဂှ်၊ ကောန်ပျူတာ တအ် ကေတ် အခိင် ဇၞော် ကဵု သၞာံ ဏီ ရ။ ယဝ်ရ တၠပညာ မွဲမွဲ ဂၠာဲဆဵု နဲကဲ သောင်ကလး ပြသၞာ $\mathcal{NP}$ ပြဟ်ပြဟ် မာန် (ဝါ $\mathcal{P} = \mathcal{NP}$) မ္ဂး၊ သၞောတ် ဂီုကၠီု အင်တာနေတ် အလုံဂၠးတိ ဏအ် လီုလာ် အာ မာန် ရ။[၅]
၁၀။ အနာဂတ် ကေုာံ ကွမ်တမ် ပရေင်ချပ်ဂၞန် (Future and Quantum Complexity Theory)
[ပလေဝ်ဒါန် | ပလေဝ်ဒါန် တမ်ကၞက်]အနာဂတ် သွက် တဳအဝ်ရဳ ပရေင်ချပ်ဂၞန် ဂှ် ဆက်စပ် ဒၟံင် ကု ကွမ်တမ် ကောန်ပျူတာ (Quantum computing) ဗွဲမဇၞော် ရ။ ကောန်ပျူတာ ကွမ်တမ် တအ် စကာ သဘာဝ ရူပဗေဒ ကွမ်တမ် မပ္တံကဵု Superposition သွက်ဂွံ တွက်ဂၞန် ရ။
ဟိုတ်ဂှ်ရ တၠပညာ တအ် ဖန်ဗဒှ် လဝ် ဂကောံ ပြသၞာ တၟိ မကော်စ BQP (Bounded-error Quantum Polynomial time) မဒှ် ပြသၞာ အိုတ်သီု မမာန် သောင်ကလး ပြဟ်ပြဟ် နကဵု ကောန်ပျူတာ ကွမ်တမ် ရ။ Shor's algorithm ဝွံ ထ္ၜးကဵု ဒဒှ်ရ ပရေင်ပါ်ကရေက် ဂၞန်သဇိုင် (Prime factorization) ဂှ် ပါလုပ် ပ္ဍဲ BQP ရ။ အရာဏအ် ပကဵု ညံင် သၞောတ် ဂီုကၠီု ခေတ်လၟုဟ် တအ် ဒးဒုင် အန္တရာယ် မာန် တုဲ၊ သုတေသန Post-quantum cryptography တအ် ကတဵုဒှ် ကၠုင် ရ။
နိဿဲဂမၠိုင်
[ပလေဝ်ဒါန် | ပလေဝ်ဒါန် တမ်ကၞက်]- ↑ Sipser, M. (2012). Introduction to the Theory of Computation, 3rd, Cengage Learning, 245-250။
- ↑ Papadimitriou, C. H. (1994). Computational Complexity. Addison-Wesley, 10-15။
- ↑ Arora, S. (2009). Computational Complexity: A Modern Approach. Cambridge University Press, 41-45။
- ↑ Fortnow, L. (2013). The Golden Ticket: P, NP, and the Search for the Impossible. Princeton University Press, 1-10။
- ↑ Garey, M. R. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 8-12။
ဆက်ဗှ်လ္ၚတ်
[ပလေဝ်ဒါန် | ပလေဝ်ဒါန် တမ်ကၞက်]- သိပ္ပံကောန်ပျူတာ မဆေင်ကဵု တဳအဝ်ရဳ (Theoretical computer science)
- အလ်ဂဝ်ရဳထမ် (Algorithm)
- စက် တူရိန် (Turing machine)
- ပြသၞာ P ကေုာံ NP (P versus NP problem)
- ခရိပ်တဝ်ဂရပ်ဖဳ (Cryptography)