2000 ခုနှစ် ၊ May လ မှာ Clay Mathematics Institute က သင်္ချာ ပုစ္ဆာ 7 ခု ကို ဒေါ်လာ တစ်သန်းစီ နဲ့ ဆုကြေး ထုတ်ခဲ့ပါတယ်။ ပုစ္ဆာ 7 ခု ထဲက တစ်ခုကို ဖြေရှင်း နိုင်ရင် ဒေါ်လာတစ်သန်း ချီးမြှင့် ခံရမှာပါ့။ Problem 7 ခု ကတော့ –
(1) Riemann Hypothesis
(2) Hodge Conjecture
(3) Birch Swinnerton Dyer Conjecture
(4) Poincare Conjecture
(5) Yang Mills Theory and Mass Gap Hypothesis
(6) Navier Stokes Equations
(7) P vs. NP Problem
ဒီ problem 7 ခုမှာ no. 4 problem (Poincare conjecture) တစ်ခုကိုပဲ ဖြေရှင်းနိုင်ပါသေးတယ်။ Preleman ဆိုတဲ့ ပညာရှင်က ဖြေရှင်း နိုင်ခဲ့တာပါ။ ဒီ ဆောင်းပါးမှာတော့ no. 7 (P vs. NP problem) ကို ဖော်ပြသွားပါမယ်။
Problem 7 ခုရဲ့ အသေးစိတ်ကို အောက်ပါ website မှာ လေ့လာနိုင်ပါတယ်။
https://www.claymath.org/millennium-problems
P vs. NP problem ဟာ Computer science နယ်ပယ် က ပုစ္ဆာ တစ်ခုပါ။ အရှင်းလင်းဆုံး ပြောပြရရင်တော့ “Problem တစ်ခုရဲ့ အဖြေကို verify လုပ်ရတာ ၊ မှန်မမှန် စစ်ရတာ ဟာ လွယ်ကူတယ် ဆိုရင် အဲ့ဒီ problem ကိုလည်း solve လုပ်ရတာ လွယ်ကူမှာလား?” ဆိုတဲ့ မေးခွန်းပါ။ ဒေါ်လာ တစ်သန်းတန်တဲ့ မေးခွန်းပေါ့။
ဥပမာ – “15 ကို ဆခွဲကိန်း ခွဲပါ” ဆိုရင် 3 x 5 လို့ သင်က ချက်ချင်း ဖြေနိုင်မှာပါ။
“3633407 ကို ဆခွဲကိန်း ခွဲပါ” ဆိုရင်တော့ သင့်အနေနဲ့ ချက်ချင်း အဖြေပေးဖို့ ခက်သွားပါပြီ။ သို့သော် “1187 နဲ့ 3061 က သူ့ရဲ့ ဆခွဲကိန်းပါ” လို့ ပြောလိုက်ရင် သင့်အနေနဲ့ check လုပ်ဖို့ လွယ်ပါတယ်။ Calculator မှာ 1187 x 3061 လို့ သွားနှိပ်လိုက်ရုံပါပဲ။
ဒါက P vs. NP problem ရဲ့ အနှစ်သာရပါ။ “ပုစ္ဆာတစ်ခုရဲ့ အဖြေကို မှန် ၊ မမှန် စစ်ဖို့ လွယ်ရင် အဖြေရှာဖို့ရော လွယ်ပါ့မလား?” ဆိုတာဟာ P vs. NP problem ရဲ့ မေးခွန်းပါပဲ။
P ဆိုတာ polynomial ကို ဆိုလိုပါတယ်။ P problem တွေဆိုရင် computer အနေနဲ့ solve လုပ်ဖို့ polynomial time ပဲကြာမယ်ပေါ့။
ဥပမာ အားဖြင့် A to Z အစဉ်လိုက်စီတာတို့ ၊ matrix နှစ်ခု မြှောက်ခိုင်းတာတို့ ၊ number တွေကို ကြီးစဉ် ငယ်လိုက် စီတာတို့ က computer တွေ အတွက် လွယ်ကူတဲ့ အလုပ်တွေပါ။
NP ဆိုတာ non-polynomial ပါ။ Computer တစ်ခု အဖို့ NP problem တွေ solve လုပ်ရတဲ့ ကြာချိန် ဟာ exponential function နဲ့ သွားပါတယ်။
ဥပမာ အားဖြင့် Traveling salesman problem တို့ ၊ Protein folding problem တို့ ၊ Chess ကစားတာ တို့ ၊ Sudoku တို့က NP problem တွေပါ။
Sudoku puzzle တစ်ခုကို computer အနေနဲ့ solve လုပ်ဖို့ ခက်ပါတယ်။ ဖြေရှင်း ပြီးသား အဖြေရှိရင်တော့ မှန်၊ မမှန် check လုပ်ရတာ လွယ်ပါတယ်။ နာမည်ကြီး game တွေဖြစ်တဲ့ super mario တို့ candy crush တို့ က NP problem တွေ ဖြစ်ကြောင်း computer scientists တွေက သက်သေပြပြီးပါပြီ။
NP problem တွေကို P problem အဖြစ် reduce လုပ်နိုင်တဲ့ algorithm ကို သင်တီထွင်နိုင်ရင် ဒေါ်လာ တစ်သန်း ဆုချီးမြှင့်ခံရ မှာ ဖြစ်ပါတယ်။
ဒါမှ မဟုတ်လည်း NP problem တွေကို P problem အဖြစ် reduce လုပ်လို့ မရကြောင်းကို သင်္ချာနည်း အားဖြင့် သက်သေပြနိုင်ရင် လည်း ဒေါ်လာ တစ်သန်း ဆုချီးမြှင့်ခံရ မှာပါ။
P problem နဲ့ NP problem တွေဟာ fundamental level မှာ တူညီ သလား ကွဲပြားသလားဆိုတာ အခုထိ မသိကြသေးတဲ့ ပဟေဠိ ပုစ္ဆာ တစ်ပုဒ်ပါ။
P = NP ဖြစ်ရင် ဘာတွေ ဆက်ဖြစ်မှာလဲ ?
Protein folding problem တွေ ဖြေရှင်းနိုင်လာမယ်။ ဒီက တဆင့် cancer ကုလို့ ရမယ်။
Traveling salesman problem ကို ဖြေရှင်း နိုင်ရင်တော့ တစ်နေရာ ကနေ တစ်နေရာ သွားဖို့ အတိုဆုံး လမ်းကြောင်းတွေကို အမြန်ဆုံးတွက်ချက်နိုင်မယ်။
သူ့ရဲ့ dark side ကတော့ cryptography ကို သုံးထားတဲ့ bank credit card တွေ ၊ social media account password တွေကို crack ရတာ ပိုပြီး လွယ်ကူသွားမှာပါ။ တစ်ဖက်မှာ ကောင်းကျိုးရှိပေမယ့် တစ်ဖက်မှာကတော့ အနုတ် လက္ခဏာ ရှိတတ်တာ သဘာ၀ ပါပဲ။
ဒီလောက်ဆိုရင် P vs. NP problem က ဘာလဲ ဆိုတာ အကြမ်းဖျင်း သိလောက်မယ် ထင်ပါတယ်။ အဆုံးထိ ဖတ်ပေးတာ ကျေးဇူးအများကြီး တင်ပါတယ်။
-Uranium-
References
https://brilliant.org/wiki/millennium-prize-problems
https://www.claymath.org/millennium-problems/p-vs-np-problem
https://www.claymath.org/millennium-problems/millennium-prize-problems
https://youtu.be/EHp4FPyajKQ
https://youtu.be/YX40hbAHx3s
Image source: science4all.org
Image credit to the rightful owner. No copyright infringement is intended.
အသိအမြင်၊ အတွေးအခေါ် အသစ်တစ်ခုခုရသွားလို့ လှူဒါန်းလိုပါက Science Nuts (Facebook Page) ကို ဆက်သွယ်လှူဒါန်းနိုင်ပါတယ်။
လှူသမျှငွေအကုန်လုံးကို လိုအပ်တဲ့နေရာတွေမှာ ပြန်လည်လှူဒါန်းပေးသွားမှာပါ။
Science Nuts 