
EITC/IS/CCTF Computational Complexity Theory Fundamentals သည် အင်တာနက်တွင် အသုံးများသော classical asymmetric public-key cryptography ၏ အခြေခံလည်းဖြစ်သည့် ဂန္တဝင်မညီသော အများသူငှာသော့ဝှက်စာရိုက်ခြင်း၏ အခြေခံဖြစ်သည့် ကွန်ပျူတာသိပ္ပံ၏ အခြေခံသဘောတရားဆိုင်ရာ သီအိုရီဆိုင်ရာ ရှုထောင့်ဆိုင်ရာ ဥရောပ IT အသိအမှတ်ပြု ပရိုဂရမ်ဖြစ်သည်။
EITC/IS/CCTF Computational Complexity Theory Fundamentals ၏ သင်ရိုးညွှန်းတမ်းသည် ကွန်ပျူတာသိပ္ပံ၏ အခြေခံအုတ်မြစ်များနှင့် တွက်ချက်မှုဆိုင်ရာ မော်ဒယ်များအပေါ် သီအိုရီဆိုင်ရာ အသိပညာကို အကျုံးဝင်သော အခြေခံသဘောတရားများဖြစ်သည့် အဆုံးအဖြတ်နှင့် အဆုံးအဖြတ်မရှိသော စက်များ၊ ပုံမှန်ဘာသာစကားများ၊ ဆက်စပ်အခမဲ့ ဂရမ်မာများနှင့် ဘာသာစကားသီအိုရီ၊ အလိုအလျောက်မာတာသီအိုရီ၊ Turing စက်များ၊ ပြဿနာများ၏ အဆုံးအဖြတ်နိုင်မှု၊ ပြန်ကောက်ချက်၊ ယုတ္တိဗေဒနှင့် ရှုပ်ထွေးသော အယ်လဂိုရစ်သမ်မစ်များသည် အောက်ပါဖွဲ့စည်းပုံအတွင်း အခြေခံကျသော လုံခြုံရေးအသုံးချမှုများအတွက်၊ ပြည့်စုံပြီး ဖွဲ့စည်းတည်ဆောက်ထားသည့် EITCI အသိအမှတ်ပြု သင်ရိုးညွှန်းတမ်းတွင် ကိုးကားထားသော အဖွင့်သုံးခွင့် ဗီဒီယိုကို သင်ကြားပြသပေးသည့် အကြောင်းအရာဖြင့် ပံ့ပိုးထားသော ပြည့်စုံသော၊ သက်ဆိုင်ရာ စာမေးပွဲကို ဖြေဆိုခြင်းဖြင့် EITC လက်မှတ်။
အယ်လဂိုရီသမ်တစ်ခု၏ တွက်ချက်မှုဆိုင်ရာ ရှုပ်ထွေးမှုသည် ၎င်းကိုလည်ပတ်ရန်အတွက် လိုအပ်သောအရင်းအမြစ်ပမာဏဖြစ်သည်။ အချိန်နှင့် မှတ်ဉာဏ်အရင်းအမြစ်များကို အထူးဂရုပြုပါသည်။ ပြဿနာတစ်ခု၏ ရှုပ်ထွေးမှုကို ဖြေရှင်းရန်အတွက် အကောင်းဆုံး algorithms ၏ ရှုပ်ထွေးမှုအဖြစ် သတ်မှတ်သည်။ အယ်လဂိုရီသမ်များကို ခွဲခြမ်းစိတ်ဖြာခြင်းသည် တိကျပြတ်သားသော ပေးထားသည့် အယ်ဂိုရီသမ်များ၏ ရှုပ်ထွေးမှုကို လေ့လာခြင်းဖြစ်ပြီး၊ တွက်ချက်မှုဆိုင်ရာ ရှုပ်ထွေးမှုသီအိုရီသည် လူသိများသော အယ်လဂိုရီသမ်များဖြင့် ပြဿနာဖြေရှင်းနည်းများ၏ ရှုပ်ထွေးမှုကို လေ့လာခြင်းဖြစ်သည်။ ဒိုမိန်းနှစ်ခုလုံးသည် algorithm ၏ရှုပ်ထွေးမှုသည် ၎င်းဖြေရှင်းသည့်ပြဿနာ၏ရှုပ်ထွေးမှုအပေါ် အမြဲတမ်း ကန့်သတ်ချုပ်ချယ်ထားသောကြောင့်ဖြစ်သည်။ ထို့အပြင်၊ ထိရောက်သော အယ်ဂိုရီသမ်များကို တည်ဆောက်စဉ်တွင် ဖြေရှင်းရမည့် ပြဿနာ၏ ရှုပ်ထွေးမှုနှင့် အချို့သော ရှုပ်ထွေးမှုများကို မကြာခဏ နှိုင်းယှဉ်ရန် လိုအပ်ပါသည်။ အခြေအနေအများစုတွင်၊ ပြဿနာတစ်ခု၏အခက်အခဲနှင့်ပတ်သက်၍ ရရှိနိုင်သောတစ်ခုတည်းသောအချက်အလက်မှာ အထိရောက်ဆုံးသိထားသောနည်းပညာများ၏ရှုပ်ထွေးမှုထက်နည်းပါသည်။ ရလဒ်အနေဖြင့်၊ algorithm ခွဲခြမ်းစိတ်ဖြာမှုနှင့် ရှုပ်ထွေးမှုသီအိုရီကြားတွင် ထပ်နေပါသည်။
ရှုပ်ထွေးမှုသီအိုရီသည် ကွန်ပျူတာသိပ္ပံအတွက် အခြေခံအဖြစ် ကွန်ပြူတာသိပ္ပံ၏အခြေခံအုတ်မြစ်တွင်သာမက ခေတ်မီကွန်ရက်များ အထူးသဖြင့် အင်တာနက်တွင်ကျယ်ကျယ်ပြန့်ပြန့်ပျံ့နှံ့နေသည့် classical asymmetric cryptography ( public-key cryptography) ၏အခြေခံအုတ်မြစ်များတွင်လည်း အရေးကြီးပါသည်။ အများသူငှာသော့ဖြင့် လျှို့ဝှက်ကုဒ်ဝှက်ခြင်းသည် အချို့သော အချိုးမညီသော သင်္ချာပြဿနာများ၏ တွက်ချက်မှုဆိုင်ရာ ခက်ခဲမှုအပေါ် အခြေခံထားခြင်းဖြစ်ပြီး ဥပမာအားဖြင့် ကိန်းဂဏန်းများကို ၎င်း၏အဓိကအချက်များအဖြစ် ခွဲထုတ်ခြင်းကဲ့သို့သော ခက်ခဲသောပြဿနာဖြစ်သည် (ဤလုပ်ဆောင်ချက်သည် ရှုပ်ထွေးမှုသီအိုရီအမျိုးအစားခွဲခြားခြင်းတွင် ခက်ခဲသောပြဿနာဖြစ်သည်၊ ဖြေရှင်းရန် ထိရောက်သော classical algorithms မရှိသောကြောင့်၊ မူလကိန်းဂဏန်းကြီးများကို ပေးဆောင်ရန် အလွန်ရိုးရှင်းသော ပြောင်းပြန်လုပ်ဆောင်ချက်နှင့် ဆန့်ကျင်ဘက်ဖြစ်သော ပြဿနာ၏ထည့်သွင်းမှုအရွယ်အစားကို တိုးခြင်းထက် ကိန်းဂဏန်းဖြင့် ကိန်းဂဏန်းဖြင့် ချဲ့ထွင်ခြင်းဖြင့် အရင်းအမြစ်များကို ချဲ့ထွင်ခြင်းဖြင့်၊ public-key cryptography ၏ ဗိသုကာတစ်ခုတွင် ဤ asymmetry ကိုအသုံးပြုခြင်း (အများပြည်သူသော့အကြား ကွန်ပြူတာအချိုးမညီသော ဆက်စပ်မှုကို သတ်မှတ်ခြင်းဖြင့်၊ လျှို့ဝှက်သော့မှ အလွယ်တကူ တွက်ချက်နိုင်သော၊ လျှို့ဝှက်သော့သည် အများသူငှာသော့မှ ကွန်ပြူတာမှ အလွယ်တကူ မဖြစ်နိုင်သော်လည်း၊ အများသူငှာ သိမြင်နိုင်သည် ။ အများသူငှာသော့ကို ကြေညာပြီး အခြားသော ဆက်သွယ်ရေး နှစ်ဖက်စလုံးမှ ဒေတာအချိုးမညီသော ကုဒ်ဝှက်ခြင်းအတွက် ၎င်းကို အသုံးပြုရန် ခွင့်ပြုထားပြီး၊ ထို့နောက် ပေါင်းစပ်လျှို့ဝှက်သော့ဖြင့်သာ စာဝှက်ထားနိုင်ကာ ပြင်ပအဖွဲ့အစည်းများအတွက် တွက်ချက်မရနိုင်သောကြောင့် ဆက်သွယ်ရေးကို လုံခြုံစေပါသည်။)
ကွန်ပြူတာဆိုင်ရာ ရှုပ်ထွေးမှုသီအိုရီကို ဒုတိယကမ္ဘာစစ်ကိုအနိုင်ရသည့် မဟာမိတ်များအတွက် လေးနက်သောအခန်းကဏ္ဍမှပါဝင်ခဲ့သည့် Alan Turing ကဲ့သို့သော ကွန်ပြူတာသိပ္ပံနှင့် အယ်လဂိုရီသမ်ဆိုင်ရာ ရှေ့ဆောင်များ၏ အောင်မြင်မှုများအပေါ်တွင် အဓိကအားဖြင့် တီထွင်ခဲ့ခြင်းဖြစ်သည်။ လျှို့ဝှက်အချက်အလက်များကို ဖော်ထုတ်ရန်အတွက် လျှို့ဝှက်ကုဒ်ဝှက်စနစ်များကို ချိုးဖောက်ကာ ကုဒ်ဝှက်ထားသော ဆက်သွယ်ရေး၏ အကြောင်းအရာများကို ဝင်ရောက်ကြည့်ရှုခွင့်ရရှိစေရန် ရည်ရွယ်၍ လျှို့ဝှက်ဝှက်ထားသော အချက်အလက်များကို ခွဲခြမ်းစိတ်ဖြာခြင်း (အဓိကအားဖြင့် ကုဒ်ဝှက်ထားသော ဆက်သွယ်ရေး) ၏ တွက်ချက်မှုဆိုင်ရာ လုပ်ငန်းစဉ်များကို အလိုအလျောက်ပြုလုပ်ရန် ရည်ရွယ်၍ လျှို့ဝှက်စာဝှက်ခြင်းစနစ်အား အသုံးပြုပါသည်။ ၎င်းသည် ပထမဆုံး ခေတ်မီကွန်ပြူတာများ၏ ဖွံ့ဖြိုးတိုးတက်မှုကို အထောက်အကူဖြစ်စေသော cryptanalysis (အစပိုင်းတွင် codebreaking ၏ မဟာဗျူဟာပန်းတိုင်သို့ အသုံးချခဲ့သည့်) ဖြစ်သည်။ British Colossus (ပထမဆုံး ခေတ်မီအီလက်ထရွန်နစ်နှင့် ပရိုဂရမ်ကွန်ပြူတာဟု ယူဆရသည့်) အား Enigma ciphers များကို ဖောက်ထွင်းရာတွင် အထောက်အကူဖြစ်စေရန် Marian Rejewski မှ ဒီဇိုင်းထုတ်ထားသည့် အီလက်ထရွန်နစ် ကွန်ပြူတာ ဗုံး (Bomb) ၏ ရှေ့တွင် တည်ရှိပြီး ပိုလန်ထောက်လှမ်းရေးမှ Great Britain သို့ လွှဲပြောင်းပေးအပ်ခဲ့သည်။ 1939 ခုနှစ်တွင် ပိုလန်အား ဂျာမနီမှ ကျူးကျော်ပြီးနောက် ဖမ်းမိထားသော German Enigma ကုဒ်ဝှက်ခြင်းစက်အား Alan Turing မှ အခြေခံ၍ German encrypted communication ကို အောင်မြင်စွာ ချိုးဖျက်နိုင်ခဲ့ပြီး နောက်ပိုင်းတွင် ခေတ်မီကွန်ပြူတာများအဖြစ် တီထွင်ထုတ်လုပ်ခဲ့သည်။
algorithm တစ်ခုလည်ပတ်ရန် လိုအပ်သော အရင်းအမြစ်ပမာဏ ပမာဏသည် input ၏ အရွယ်အစားနှင့် ကွဲပြားသောကြောင့်၊ ရှုပ်ထွေးမှုကို အများအားဖြင့် function f(n) အဖြစ် ဖော်ပြကြပြီး၊ n သည် input size ဖြစ်ပြီး f(n) သည် အဆိုးရွားဆုံး ရှုပ်ထွေးမှုဖြစ်နိုင်သည် ( size n ၏ သွင်းအားစုများအားလုံးတွင် လိုအပ်သော အရင်းအမြစ်အများဆုံးပမာဏ သို့မဟုတ် ပျမ်းမျှဖြစ်ရပ်မှန် ရှုပ်ထွေးမှု ( size n ၏ သွင်းအားစုအားလုံးထက် ပျမ်းမျှပမာဏ၏ အရင်းအမြစ်ပမာဏ)။ အရွယ်အစား n ၏ ထည့်သွင်းမှုတစ်ခုတွင် လိုအပ်သော အခြေခံလုပ်ဆောင်မှုအရေအတွက်ကို အချိန်ရှုပ်ထွေးမှုအဖြစ် ယေဘုယျအားဖြင့်ဖော်ပြထားပြီး မူလလုပ်ငန်းဆောင်တာများသည် ကွန်ပျူတာတစ်ခုပေါ်တွင် အချိန်အတိုင်းအတာတစ်ခုအထိကြာပြီး မတူညီသောစက်တစ်ခုပေါ်တွင် လုပ်ဆောင်သည့်အခါ အဆက်မပြတ်အချက်တစ်ချက်ဖြင့်သာ ပြောင်းလဲလေ့ရှိသည့် မူလလုပ်ငန်းဆောင်တာများကို အချိန်အတိုင်းအတာတစ်ခုအဖြစ် သတ်မှတ်ထားသည်။ size n တွင် ထည့်သွင်းသည့် algorithm တစ်ခုမှ လိုအပ်သော memory ပမာဏကို space complexity ဟုခေါ်သည်။
အချိန်သည် အများအားဖြင့် ယူဆသော အရင်းအမြစ်ဖြစ်သည်။ အရည်အချင်းသတ်မှတ်ချက်မပါဘဲ "ရှုပ်ထွေးမှု" ဟူသော ဝေါဟာရကို အသုံးပြုသောအခါ၊ အချိန်၏ ရှုပ်ထွေးမှုကို ရည်ညွှန်းလေ့ရှိသည်။
သမားရိုးကျ အချိန်ယူနစ်များ (စက္ကန့်၊ မိနစ်စသည်ဖြင့်) ကို ရှုပ်ထွေးမှုသီအိုရီတွင် အသုံးမချသောကြောင့် ၎င်းတို့သည် ကွန်ပျူတာရွေးချယ်မှုနှင့် နည်းပညာတိုးတက်မှုအပေါ် အလွန်အမင်း အားကိုးနေသောကြောင့် ဖြစ်သည်။ ဥပမာအားဖြင့်၊ ယနေ့ခေတ် ကွန်ပျူတာတစ်လုံးသည် 1960 ခုနှစ်များမှ ကွန်ပျူတာတစ်လုံးထက် များစွာမြန်ဆန်သော algorithm တစ်ခုကို လုပ်ဆောင်နိုင်သော်လည်း၊ ၎င်းသည် algorithm ၏ မွေးရာပါအရည်အသွေးထက် ကွန်ပျူတာ hardware တွင် နည်းပညာပိုင်းဆိုင်ရာ တိုးတက်မှုများကြောင့်ဖြစ်သည်။ ရှုပ်ထွေးမှုသီအိုရီ၏ ပန်းတိုင်မှာ အယ်လဂိုရီသမ်များ၏ မွေးရာပါအချိန်လိုအပ်ချက်များကို တွက်ချက်ရန် သို့မဟုတ် မည်သည့်ကွန်ပျူတာတွင်မဆို အယ်လဂိုရီသမ်တစ်ခုချမှတ်မည့် အခြေခံအချိန်ကန့်သတ်ချက်များကို တွက်ချက်ရန်ဖြစ်သည်။ တွက်ချက်မှုအတွင်း အခြေခံလုပ်ဆောင်မှု မည်မျှလုပ်ဆောင်သည်ကို ရေတွက်ခြင်းဖြင့် ၎င်းကို ပြီးမြောက်စေသည်။ ဤလုပ်ထုံးလုပ်နည်းများသည် စက်တစ်ခုတွင် အဆက်မပြတ်အချိန်ယူသည်ဟု ယူဆသောကြောင့် ၎င်းတို့ကို အဆင့်များဟု အများအားဖြင့် ရည်ညွှန်းသည် (ဆိုလိုသည်မှာ ၎င်းတို့သည် ထည့်သွင်းမှုပမာဏအားဖြင့် သက်ရောက်မှုမရှိပါ)။
နောက်ထပ်အရေးကြီးသောအရင်းအမြစ်မှာ algorithms လုပ်ဆောင်ရန်အတွက် ကွန်ပျူတာမှတ်ဉာဏ်ပမာဏဖြစ်သည်။
နောက်ထပ်အသုံးများသော အရင်းအမြစ်မှာ ဂဏန်းသင်္ချာလုပ်ငန်းဆောင်တာများဖြစ်သည်။ ဤအခြေအနေတွင်၊ "ဂဏန်းသင်္ချာရှုပ်ထွေးမှု" ဟူသော အသုံးအနှုန်းကို အသုံးပြုသည်။ အချိန်ရှုပ်ထွေးမှုသည် ယေဘူယျအားဖြင့် ကိန်းသေကိန်းဂဏန်းတစ်ခုဖြင့် ဂဏန်းသင်္ချာရှုပ်ထွေးမှု၏ ရလဒ်ဖြစ်သည်။
တွက်ချက်မှုတစ်ခုအတွင်း အသုံးပြုခဲ့သော ကိန်းပြည့်များ၏ အရွယ်အစားသည် နည်းလမ်းများစွာအတွက် ကန့်သတ်မထားဘဲ၊ ဂဏန်းသင်္ချာလုပ်ငန်းဆောင်တာများသည် သတ်မှတ်ထားသော အချိန်အတိုင်းအတာတစ်ခု လိုအပ်သည်ဟု ယူဆခြင်းသည် လက်တွေ့မကျပါ။ ရလဒ်အနေဖြင့်၊ bit complexity ဟုလည်းသိကြသော အချိန်ရှုပ်ထွေးမှုသည် ဂဏန်းသင်္ချာရှုပ်ထွေးမှုထက် သိသာစွာမြင့်မားနိုင်သည်။ ဥပမာအားဖြင့် nn integer matrix ၏ အဆုံးအဖြတ်ကို တွက်ချက်ရာတွင် ဂဏန်းသင်္ချာအခက်အခဲမှာ O(n^3) သည် စံနည်းပညာများ (Gaussian elimination) ဖြစ်သည်။ ကိန်းဂဏန်းများ၏ အရွယ်အစားသည် တွက်ချက်မှုအတွင်း အဆတိုးနိုင်သောကြောင့်၊ တူညီသောနည်းလမ်းများ၏ အနည်းငယ်ရှုပ်ထွေးမှုသည် n တွင် ကိန်းဂဏန်းများဖြစ်သည်။ ဤနည်းပညာများကို မော်ဂျူးဂဏန်းသင်္ချာပေါင်းများစွာနှင့် တွဲဖက်အသုံးပြုပါက၊ အနည်းငယ်ရှုပ်ထွေးမှုကို O(n^4) သို့ လျှော့ချနိုင်သည်။
bit complexity သည် algorithm တစ်ခုကို run ရန် လိုအပ်သော bit များဆိုင်ရာ လုပ်ဆောင်ချက် အရေအတွက်ကို ရည်ညွှန်းသည်။ ၎င်းသည် တွက်ချက်မှုဆိုင်ရာ ပရာဒိုင်းအများစုတွင် ကိန်းသေတစ်ခုအထိ ယာယီရှုပ်ထွေးမှုနှင့် ညီမျှသည်။ ကွန်ပြူတာများလိုအပ်သော စက်စကားလုံးများအတွက် လုပ်ဆောင်မှုအရေအတွက်သည် အနည်းငယ်ရှုပ်ထွေးမှုနှင့် အချိုးကျပါသည်။ လက်တွေ့ကျသော တွက်ချက်မှုပုံစံများအတွက်၊ အချိန်ရှုပ်ထွေးမှုနှင့် အနည်းငယ်ရှုပ်ထွေးမှုတို့သည် တူညီပါသည်။
စီစဥ်ခြင်းနှင့် ရှာဖွေခြင်းတွင် ထည့်သွင်းစဉ်းစားလေ့ရှိသော အရင်းအမြစ်မှာ ထည့်သွင်းမှုများ နှိုင်းယှဉ်မှုပမာဏဖြစ်သည်။ ဒေတာကို ကောင်းစွာစီစဉ်ထားပါက၊ ၎င်းသည် အချိန်ရှုပ်ထွေးမှု၏ ကောင်းသောညွှန်ပြချက်ဖြစ်သည်။
ဖြစ်နိုင်ချေရှိသော သွင်းအားစုများအားလုံးတွင်၊ algorithm တစ်ခုရှိ အဆင့်အရေအတွက်ကို ရေတွက်ရန် မဖြစ်နိုင်ပါ။ input တစ်ခု၏ ရှုပ်ထွေးမှုသည် ၎င်း၏ အရွယ်အစားနှင့် တိုးလာသောကြောင့် ၎င်းကို input ၏ size n (bits) ၏ function အဖြစ် ကိုယ်စားပြုပြီး ရှုပ်ထွေးမှုသည် n ၏ function တစ်ခုဖြစ်သည်။ အရွယ်အစားတူ သွင်းအားစုများအတွက်၊ အယ်လဂိုရီသမ်တစ်ခု၏ ရှုပ်ထွေးမှုသည် သိသိသာသာ ကွဲပြားနိုင်သည်။ ရလဒ်အနေဖြင့်၊ ရှုပ်ထွေးမှုအမျိုးမျိုးသော လုပ်ငန်းဆောင်တာများကို ပုံမှန်အသုံးပြုကြသည်။
အဆိုးဆုံးသော ရှုပ်ထွေးမှုသည် အရွယ်အစား n သွင်းအားစုအားလုံးအတွက် ရှုပ်ထွေးမှုအားလုံး၏ ပေါင်းစုဖြစ်ပြီး ပျမ်းမျှကိစ္စရပ်ရှုပ်ထွေးမှုသည် အရွယ်အစား n သွင်းအားစုအားလုံးအတွက် ရှုပ်ထွေးမှုအားလုံး၏ ပေါင်းလဒ်ဖြစ်သည် (၎င်းသည် ပေးထားသည့် အရွယ်အစား၏ ဖြစ်နိုင်ချေရှိသော သွင်းအားစုများ၏ အရေအတွက်ဖြစ်သောကြောင့်၊ ဆိုလိုသည်မှာ အဓိပ္ပာယ်မှာ၊ အကန့်အသတ်)။ “ရှုပ်ထွေးမှု” ဟူသောအသုံးအနှုန်းကို ထပ်မံမသတ်မှတ်ဘဲ အသုံးပြုသောအခါ၊ အဆိုးဆုံးအချိန်ရှုပ်ထွေးမှုကို ထည့်သွင်းစဉ်းစားသည်။
အဆိုးဆုံးနှင့် သာမန်ကိစ္စများ ရှုပ်ထွေးမှုသည် မှန်ကန်စွာ တွက်ချက်ရန် နာမည်ဆိုးဖြင့် ကျော်ကြားသည်။ ထို့အပြင်၊ စက် သို့မဟုတ် တွက်ချက်မှုဆိုင်ရာ ပါရာဒိုင်းတွင် ပြောင်းလဲမှုတိုင်းသည် ရှုပ်ထွေးမှုအနည်းငယ်ကွဲပြားနိုင်သောကြောင့် အဆိုပါအတိအကျတန်ဖိုးများသည် လက်တွေ့အသုံးချမှုအနည်းငယ်သာရှိသည်။ ထို့အပြင် n ၏သေးငယ်သောတန်ဖိုးများအတွက် အရင်းအမြစ်အသုံးပြုမှုသည် အရေးမကြီးပါ၊ ထို့ကြောင့် အကောင်အထည်ဖော်ရာတွင် လွယ်ကူမှုသည် n အသေးစားအတွက် ရှုပ်ထွေးမှုနည်းပါးသည်ထက် ပိုမိုနှစ်သက်ဖွယ်ကောင်းသည်။
ဤအကြောင်းများကြောင့်၊ n သည် အဆုံးမရှိချဉ်းကပ်လာသည်နှင့်အမျှ ၎င်း၏ asymptotic အပြုအမူသည် မြင့်မားသော ရှုပ်ထွေးမှုအတွက် အာရုံစိုက်မှုအများဆုံးဖြစ်သည်။ ရလဒ်အနေဖြင့် ကြီးမားသော O notation ကို ရှုပ်ထွေးမှုကို ဖော်ပြရန်အတွက် အများအားဖြင့် အသုံးပြုကြသည်။
ကွန်ပြူတာမော်ဒယ်များ
အချိန်ယူနစ်တစ်ခုအတွင်း လုပ်ဆောင်ရမည့် မရှိမဖြစ်လိုအပ်သော လုပ်ဆောင်ချက်များကို သတ်မှတ်ခြင်း ပါဝင်သော တွက်ချက်မှုပုံစံတစ်ခု၏ ရွေးချယ်မှုသည် ရှုပ်ထွေးမှုကို ဆုံးဖြတ်ရာတွင် အရေးကြီးပါသည်။ တွက်ချက်မှုဆိုင်ရာ ပါရာဒိုင်းကို အထူးတလည် မဖော်ပြထားသောအခါ ၎င်းကို multitape Turing machine ဟုခေါ်သည်။
အဆုံးအဖြတ်ပေးသော တွက်ချက်မှုပုံစံသည် စက်၏နောက်ဆက်တွဲအခြေအနေများနှင့် လုပ်ဆောင်ရမည့်လုပ်ဆောင်ချက်များကို ယခင်အခြေအနေက လုံးလုံးလျားလျားသတ်မှတ်ထားသည်။ Recursive functions၊ lambda calculus နှင့် Turing machines များသည် ပထမဆုံးသော အဆုံးအဖြတ်ပေးသော မော်ဒယ်များဖြစ်သည်။ Random-access machines (RAM-machines ဟုလည်းခေါ်သည်) သည် ကမ္ဘာပေါ်ရှိ ကွန်ပျူတာများကို အတုယူရန်အတွက် ရေပန်းစားသော ပါရာဒိုင်းတစ်ခုဖြစ်သည်။
တွက်ချက်မှုပုံစံကို မသတ်မှတ်ထားသောအခါ၊ တိပ် Turing စက်ကို အများအားဖြင့် ယူဆသည်။ Multitape Turing စက်များတွင်၊ အချိန်ရှုပ်ထွေးမှုသည် algorithms အများစုအတွက် RAM စက်များကဲ့သို့ပင်ဖြစ်ပြီး၊ ဤညီမျှမှုကိုရရှိရန် ဒေတာသိမ်းဆည်းပုံအား မှတ်ဉာဏ်တွင် မှတ်သားထားရန် လိုအပ်သော်လည်း များစွာအာရုံစိုက်နိုင်ပါသည်။
သတ်မှတ်ထားသောမဟုတ်သော Turing စက်များကဲ့သို့သော အဆုံးအဖြတ်မရှိသော တွက်ချက်မှုပုံစံတွင် တွက်ချက်မှုအဆင့်အချို့တွင် အမျိုးမျိုးသောရွေးချယ်မှုများကို ပြုလုပ်နိုင်သည်။ ရှုပ်ထွေးမှုသီအိုရီတွင်၊ ဖြစ်နိုင်ခြေရှိသော ရွေးချယ်မှုများအားလုံးကို တစ်ချိန်တည်းတွင် ထည့်သွင်းစဉ်းစားပြီး အကောင်းဆုံးရွေးချယ်မှုများ အမြဲတမ်းပြုလုပ်သောအခါတွင် သတ်မှတ်ပြဋ္ဌာန်းချက်မရှိသော အချိန်ရှုပ်ထွေးမှုသည် လိုအပ်သည့်အချိန်ပမာဏဖြစ်သည်။ အခြားနည်းဖြင့်ပြောရလျှင် လိုအပ်သလောက် (တူညီသော) ပရိုဆက်ဆာများပေါ်တွင် တွက်ချက်ခြင်းအား တစ်ပြိုင်နက်တည်း လုပ်ဆောင်ပြီး အဆုံးအဖြတ်မရှိသော တွက်ချက်မှုအချိန်သည် တွက်ချက်မှု အပြီးသတ်ရန် ပထမပရိုဆက်ဆာမှ ယူသောအချိန်ဖြစ်သည်။ ဥပမာအားဖြင့် Shor ၏သေးငယ်သော integers များကို အပိုင်းပိုင်းခွဲခြင်းကဲ့သို့သော အထူးပြုကွမ်တမ် အယ်လဂိုရီသမ်များကို လုပ်ဆောင်သောအခါတွင် မျဉ်းပြိုင်ဖြစ်နေသော ကွမ်တမ်ကွန်ပြူတာတွင် ဤမျဉ်းပြိုင်စနစ်ကို အသုံးပြုနိုင်သည်။
ဤကဲ့သို့သော တွက်ချက်မှုပုံစံကို လောလောဆယ် လက်တွေ့မလုပ်ဆောင်နိုင်သေးပါက၊ အထူးသဖြင့် P = NP ပြဿနာနှင့်စပ်လျဉ်း၍ ၎င်းတွင် သီအိုရီဆိုင်ရာ အရေးပါမှုရှိပြီး၊ "polynomial time" နှင့် "သတ်မှတ်မဟုတ်သော polynomial time" ကိုအသုံးပြုခြင်းဖြင့် ထုတ်လုပ်သော ရှုပ်ထွေးမှုအတန်းများကို အထက်ပိုင်းအဖြစ် မေးသော၊ ဘောင်တွေက အတူတူပါပဲ။ အဆုံးအဖြတ်ပေးသောကွန်ပြူတာတွင်၊ NP-algorithm ကို အတုယူရန် "exponential time" လိုအပ်သည်။ အလုပ်တစ်ခုအား အဆုံးအဖြတ်မရှိသောစနစ်တွင် ပေါလီအမည်အချိန်အတွင်း ဖြေရှင်းနိုင်လျှင် ၎င်းသည် NP ခက်ခဲမှုအတန်းအစားဖြစ်သည်။ ပြဿနာတစ်ခုသည် NP တွင်ရှိပြီး အခြား NP ပြဿနာထက် မလွယ်ကူပါက၊ ၎င်းသည် NP-ပြီးပြည့်စုံသည်ဟု ဆိုသည်။ Knapsack ပြဿနာ၊ ခရီးသွားအရောင်းသမား ပြဿနာနှင့် Boolean ကျေနပ်နိုင်မှု ပြဿနာတို့သည် NP-ပြီးပြည့်စုံသော ပေါင်းစပ်ပြဿနာများဖြစ်သည်။ လူသိအများဆုံး အယ်လဂိုရီသမ်တွင် ဤပြဿနာအားလုံးအတွက် ကိန်းဂဏန်း ရှုပ်ထွေးမှုရှိသည်။ အကယ်၍ ဤပြဿနာများထဲမှ တစ်ခုခုကို အဆုံးအဖြတ်စက်တစ်ခုပေါ်တွင် ပေါလီအမည်အချိန်အတွင်း ဖြေရှင်းနိုင်ပါက၊ NP ပြဿနာအားလုံးကို ပေါင်းကိန်းအချိန်အတွင်းလည်း ဖြေရှင်းနိုင်ပြီး P = NP ကို တည်ထောင်မည်ဖြစ်သည်။ 2017 ခုနှစ်အရ၊ NP ပြဿနာများ၏ အဆိုးဆုံးအခြေအနေများသည် ဖြေရှင်းရန်အခြေခံအားဖြင့် ခက်ခဲသည်ဟု ဆိုလိုသည်မှာ၊ စိတ်ဝင်စားစရာကောင်းသောထည့်သွင်းမှုအရှည်များပေးထားသော ဖြစ်နိုင်ချေရှိသော အချိန်ကာလ (ဆယ်စုနှစ်များ) ထက် ပိုမိုကြာမြင့်သည်ဟု XNUMX ခုနှစ်၌ ကျယ်ပြန့်စွာယူဆပါသည်။
မျဉ်းပြိုင်နှင့် ဖြန့်ဝေထားသော တွက်ချက်မှု
မျဉ်းပြိုင်နှင့် ဖြန့်ဝေထားသော တွက်ချက်မှုတွင် ပရိုဆက်ဆာများစွာကို တစ်ပြိုင်နက်တည်း လုပ်ဆောင်သည့် ပရိုဆက်ဆာအများအပြားကို ပိုင်းခြားခြင်းပါဝင်သည်။ မော်ဒယ်အမျိုးမျိုးအကြား အခြေခံကွဲပြားချက်မှာ ပရိုဆက်ဆာများကြားတွင် ဒေတာပေးပို့သည့်နည်းလမ်းဖြစ်သည်။ ပရိုဆက်ဆာများကြား ဒေတာပေးပို့ခြင်းသည် အများအားဖြင့် အပြိုင်ကွန်ပြူတာတွင် အလွန်လျင်မြန်သော်လည်း၊ ပရိုဆက်ဆာများအကြား ဖြန့်ဝေထားသော ကွန်ပြူတာတွင် ဒေတာလွှဲပြောင်းခြင်းမှာ ကွန်ရက်တစ်ခုပေါ်တွင် လုပ်ဆောင်ပြီးဖြစ်သောကြောင့် သိသိသာသာ နှေးကွေးပါသည်။
N ပရိုဆက်ဆာများတွင် တွက်ချက်မှုတစ်ခုသည် ပရိုဆက်ဆာတစ်ခုတည်းတွင်အသုံးပြုသည့်အချိန်၏ N မှ quotient ကို အနည်းဆုံးယူသည်။ လက်တွေ့တွင်၊ အချို့သောအလုပ်ခွဲများကို ပြိုင်တူမလုပ်ဆောင်နိုင်သောကြောင့် အချို့သောပရိုဆက်ဆာများသည် အခြားသောပရိုဆက်ဆာမှရလဒ်ကိုစောင့်ဆိုင်းရန် လိုအပ်နိုင်သောကြောင့်၊ ဤသီအိုရီအရ စံနမူနာထုပ်ပိုးခြင်းကို မည်သည့်အခါမျှ ရရှိနိုင်မည်မဟုတ်ပေ။
အဓိကရှုပ်ထွေးမှုပြဿနာမှာ ပရိုဆက်ဆာတစ်ခုတည်းတွင် တူညီသောတွက်ချက်မှုလုပ်ဆောင်ရန် လိုအပ်သည့်အချိန်နှင့် တွက်ချက်ချိန်ကိုက်သည့်အချိန်နှင့် ပရိုဆက်ဆာအရေအတွက်အလိုက် တွက်ချက်ခြင်း၏ထုတ်ကုန်ကို တတ်နိုင်သမျှနီးစပ်စေရန် အယ်လဂိုရီသမ်များကို တီထွင်ရန်ဖြစ်သည်။
ကွမ်တမ်တွက်ချက်မှု
ကွမ်တမ်ကွန်ပြူတာသည် ကွမ်တမ်မက္ကင်းနစ်ဆိုင်ရာ တွက်ချက်မှုပုံစံပါရှိသော ကွန်ပျူတာဖြစ်သည်။ Church-Turing thesis သည် ကွမ်တမ်ကွန်ပြူတာများအတွက် မှန်ကန်ကြောင်း အခိုင်အမာဆိုသည်၊ ကွမ်တမ်ကွန်ပြူတာသည် ဖြေရှင်းနိုင်သည့် မည်သည့်ပြဿနာကိုမဆို Turing စက်ဖြင့် ဖြေရှင်းနိုင်သည်ဟု ဆိုလိုသည်။ သို့သော်၊ အချို့သောအလုပ်များသည် သီအိုရီအရ သိသိသာသာနိမ့်ကျရှုပ်ထွေးမှုရှိသော ရှေးရိုးကွန်ပျူတာထက် ကွမ်တမ်ကွန်ပျူတာကို အသုံးပြု၍ ဖြေရှင်းနိုင်သည်။ လက်ရှိတွင်၊ လက်တွေ့ကျသော ကွမ်တမ်ကွန်ပြူတာအား မည်သို့တီထွင်ရမည်ကို မည်သူမျှ မသိသောကြောင့်၊ ၎င်းသည် သီအိုရီအရ တင်းကြပ်စွာ မှန်ကန်ပါသည်။
ကွမ်တမ်ကွန်ပြူတာများဖြင့် ဖြေရှင်းနိုင်သော မတူညီသောပြဿနာများကို စုံစမ်းစစ်ဆေးရန် ကွမ်တမ်ရှုပ်ထွေးမှုသီအိုရီကို ဖန်တီးခဲ့ခြင်းဖြစ်သည်။ ၎င်းကို ကွမ်တမ်ကွန်ပြူတာ တိုက်ခိုက်မှုများကို ခံနိုင်ရည်ရှိသော ကွမ်တမ်ကွန်ပြူတာ တိုက်ခိုက်မှုများကို ခံနိုင်ရည်ရှိသော ကွမ်တမ် ပရိုတိုကောများ ဖန်တီးခြင်း လုပ်ငန်းစဉ်ဖြစ်သည့် Post-quantum cryptography တွင် အသုံးပြုသည်။
ပြဿနာ၏ ရှုပ်ထွေးမှု (အောက်ခြေဘောင်များ)
မဖော်ထုတ်နိုင်သော နည်းပညာများ အပါအဝင် ပြဿနာကို ဖြေရှင်းနိုင်သည့် အယ်လဂိုရီသမ်များ၏ ရှုပ်ထွေးမှု အနိမ့်ဆုံးမှာ ပြဿနာ၏ ရှုပ်ထွေးမှုဖြစ်သည်။ ရလဒ်အနေဖြင့် ပြဿနာတစ်ခု၏ ရှုပ်ထွေးမှုသည် ၎င်းကိုဖြေရှင်းပေးသည့် မည်သည့် algorithm ၏ ရှုပ်ထွေးမှုနှင့် ညီမျှသည်။
ရလဒ်အနေဖြင့်၊ ကြီးမားသော O အမှတ်အသားတွင် ပေးထားသည့် ရှုပ်ထွေးမှုမှန်သမျှသည် အယ်လဂိုရီသမ်နှင့် ဆက်စပ်ပြဿနာနှစ်ခုစလုံး၏ ရှုပ်ထွေးမှုကို ကိုယ်စားပြုသည်။
အခြားတစ်ဖက်တွင်၊ ပြဿနာရှုပ်ထွေးမှုတွင် အသေးအဖွဲမဟုတ်သော အောက်ခြေနယ်နိမိတ်များကို ရယူရန်မှာ မကြာခဏ ခက်ခဲလေ့ရှိပြီး ထိုသို့ပြုလုပ်ရန်အတွက် နည်းဗျူဟာ အနည်းငယ်သာရှိသည်။
ပြဿနာအများစုကိုဖြေရှင်းရန်အတွက်၊ အချက်အလက်၏အတိုင်းအတာနှင့်အချိန်ယူ၍ ထည့်သွင်းထားသောဒေတာအားလုံးကိုဖတ်ရပါမည်။ ရလဒ်အနေဖြင့်၊ ထိုပြဿနာများသည် အနည်းဆုံး linear complexity သို့မဟုတ် Ω(n) ၏ ရှုပ်ထွေးမှုကြီးတွင် အိုမီဂါအမှတ်အသားတွင် ရှိသည်။
ကွန်ပျူတာ အက္ခရာသင်္ချာနှင့် တွက်ချက်မှုဆိုင်ရာ အက္ခရာသင်္ချာဂျီသြမေတြီကဲ့သို့သော အချို့ပြဿနာများသည် အလွန်ကြီးမားသော ဖြေရှင်းနည်းများရှိသည်။ အထွက်ကို ရေးရမည်ဖြစ်သောကြောင့်၊ အထွက်၏ အမြင့်ဆုံးအရွယ်အစားဖြင့် ရှုပ်ထွေးမှုကို ကန့်သတ်ထားသည်။
စီစဥ်သည့် အယ်လဂိုရီသမ်အတွက် လိုအပ်သော နှိုင်းယှဉ်မှုအရေအတွက်သည် Ω(nlogn) ၏ အောက်လိုင်းမဟုတ်သော ဘောင်တစ်ခုရှိသည်။ ရလဒ်အနေဖြင့်၊ ၎င်းတို့၏ ရှုပ်ထွေးမှုသည် O(nlogn) ဖြစ်သောကြောင့် အကောင်းဆုံး စီခြင်း အယ်လဂိုရီသမ်များသည် အထိရောက်ဆုံးဖြစ်သည်။ n ရှိပါတယ်ဆိုတဲ့အချက်ကို! n အရာများကို စုစည်းရန် နည်းလမ်းများသည် ဤအောက်ပိုင်းဘောင်သို့ ဦးတည်သည်။ နှိုင်းယှဉ်မှုတစ်ခုစီသည် ဤစုစည်းမှု n ကို ပိုင်းခြားထားသောကြောင့်ဖြစ်သည်။ အမှာစာများအားလုံးကို ပိုင်းခြားရန် လိုအပ်သော N နှိုင်းယှဉ်မှု အရေအတွက်သည် 2N > n! ဖြစ်ပြီး၊ Stirling ၏ဖော်မြူလာအရ O(nlogn) ကို ဆိုလိုသည်။
ပြဿနာတစ်ခုကို အခြားပြဿနာတစ်ခုသို့ လျှော့ချခြင်းသည် လျှော့ပေါ့ရှုပ်ထွေးမှု ကန့်သတ်ချက်များကို ရရှိရန် ဘုံဗျူဟာတစ်ခုဖြစ်သည်။
Algorithm ဖွံ့ဖြိုးတိုးတက်ရေး
အယ်လဂိုရီသမ်တစ်ခု၏ ရှုပ်ထွေးမှုကို အကဲဖြတ်ခြင်းသည် မျှော်လင့်နိုင်သည့် စွမ်းဆောင်ရည်နှင့်ပတ်သက်သော အသုံးဝင်သော အချက်အလက်များကို ပေးဆောင်သောကြောင့် ဒီဇိုင်းလုပ်ငန်းစဉ်၏ အရေးကြီးသောအစိတ်အပိုင်းတစ်ခုဖြစ်သည်။
ခေတ်မီကွန်ပြူတာပါဝါကြီးထွားမှုကို ခန့်မှန်းသည့် Moore ၏ဥပဒေကြောင့် ရှုပ်ထွေးသော အယ်လဂိုရီသမ်များကို အကဲဖြတ်ခြင်းသည် မကြာခဏနားလည်မှုလွဲမှားခြင်းတစ်ခုဖြစ်သည်။ တိုးမြှင့်ပါဝါသည် များပြားလှသော ဒေတာပမာဏ (ဒေတာကြီး) ကို လုပ်ဆောင်နိုင်သောကြောင့် ၎င်းသည် မမှန်ပါ။ ဥပမာအားဖြင့်၊ စာအုပ်တစ်အုပ်၏ bibliography ကဲ့သို့သော ရာနှင့်ချီသော entry များစာရင်းကို အက္ခရာစဉ်အလိုက်စီထားသောအခါ မည်သည့် algorithm မဆို ကောင်းမွန်စွာလုပ်ဆောင်နိုင်မည်ဖြစ်သည်။ အခြားတစ်ဖက်တွင်၊ ထည့်သွင်းမှုတစ်သန်း (ဥပမာ၊ မြို့ကြီးတစ်ခု၏ ဖုန်းနံပါတ်များ) အတွက် O(n2) နှိုင်းယှဉ်မှုများ လိုအပ်သည့် အခြေခံ algorithms သည် ထရီလျံနှိုင်းယှဉ်မှုများကို လုပ်ဆောင်ရမည်ဖြစ်ပြီး 10 အမြန်နှုန်းဖြင့် သုံးနာရီကြာမည်ဖြစ်သည်။ တစ်စက္ကန့်လျှင် သန်းနှိုင်းယှဥ်မှု။ အခြားတစ်ဖက်တွင်၊ Quicksort နှင့် ပေါင်းစည်းခြင်းအမျိုးအစားသည် nlogn နှိုင်းယှဉ်မှုများသာ လိုအပ်သည် (ယခင်အတွက် ပျမ်းမျှဖြစ်ရပ်မှန်ရှုပ်ထွေးမှု၊ နောက်တစ်ခုအတွက် အဆိုးဆုံးသောရှုပ်ထွေးမှုအဖြစ်)။ ၎င်းသည် n = 30,000,000 အတွက် နှိုင်းယှဉ်မှု 1,000,000 ဝန်းကျင်ကို ထုတ်ပေးမည်ဖြစ်ပြီး၊ တစ်စက္ကန့်လျှင် နှိုင်းယှဉ်မှု 3 သန်းတွင် 10 စက္ကန့်သာ ကြာမည်ဖြစ်သည်။
ရလဒ်အနေဖြင့်၊ ရှုပ်ထွေးမှုကို အကဲဖြတ်ခြင်းသည် အကောင်အထည်မဖော်မီ ထိရောက်မှုမရှိသော အယ်လဂိုရီသမ်များစွာကို ဖယ်ရှားနိုင်မည်ဖြစ်သည်။ ဖြစ်နိုင်ချေရှိသော မူကွဲအားလုံးကို စမ်းသပ်စရာမလိုဘဲ ရှုပ်ထွေးသော အယ်လဂိုရီသမ်များကို ကောင်းစွာချိန်ညှိရန်အတွက်လည်း ၎င်းကို အသုံးပြုနိုင်သည်။ ရှုပ်ထွေးမှုကို လေ့လာခြင်းသည် ရှုပ်ထွေးသော အယ်လဂိုရီသမ်တစ်ခု၏ ကုန်ကျစရိတ်အများဆုံးအဆင့်များကို ဆုံးဖြတ်ခြင်းဖြင့် အကောင်အထည်ဖော်မှုတစ်ခု၏ ထိရောက်မှုကို တိုးမြှင့်ရန် အားထုတ်မှုကို အာရုံစိုက်နိုင်စေသည်။
အောင်လက်မှတ် သင်ရိုးညွှန်းတမ်းနှင့် အသေးစိတ် သိစေရန်အတွက် အောက်ပါဇယားကို ချဲ့ထွင်ပြီး ခွဲခြမ်းစိတ်ဖြာနိုင်ပါသည်။
EITC/IS/CCTF Computational Complexity Theory Fundamentals Certification Curriculum သည် open-access didactic ပစ္စည်းများကို ဗီဒီယိုပုံစံဖြင့် ကိုးကားပါသည်။ သင်ယူမှုလုပ်ငန်းစဉ်အား သက်ဆိုင်ရာ သင်ရိုးအပိုင်းများကို အကျုံးဝင်သော အဆင့်ဆင့်ဖွဲ့စည်းပုံ (ပရိုဂရမ်များ -> သင်ခန်းစာများ -> ခေါင်းစဉ်များ) ဖြင့် ပိုင်းခြားထားပါသည်။ ပါဝင်သူများသည် လက်ရှိတိုးတက်နေသော EITC ပရိုဂရမ်သင်ရိုးညွှန်းတမ်းခေါင်းစဉ်အောက်ရှိ e-learning interface ၏ အမေးအဖြေကဏ္ဍတွင် အဖြေများကို ဝင်ရောက်ကြည့်ရှုနိုင်ပြီး ပိုမိုသက်ဆိုင်သည့်မေးခွန်းများကို မေးမြန်းနိုင်ပါသည်။ ဒိုမိန်းကျွမ်းကျင်သူများနှင့် တိုက်ရိုက် အကန့်အသတ်မရှိ အကြံပေးခြင်းအား ပေါင်းစပ်ထားသော အွန်လိုင်းစာတိုပေးပို့ခြင်းစနစ်အပြင် အဆက်အသွယ်ပုံစံမှတစ်ဆင့်လည်း ရယူနိုင်ပါသည်။
Certification လုပ်ထုံးလုပ်နည်းအသေးစိတ်အတွက် စစ်ဆေးပါ။ ဘယ်လိုအလုပ်လုပ်လဲ.
မူလတန်း အထောက်အကူပြု သင်ရိုးညွှန်းတမ်း ဖတ်ရှုခြင်း ပစ္စည်းများ
S. Arora၊ B. Barak၊ တွက်ချက်မှုဆိုင်ရာ ရှုပ်ထွေးမှု- ခေတ်မီချဉ်းကပ်နည်း
https://theory.cs.princeton.edu/complexity/book.pdf
အလယ်တန်း သင်ရိုးညွှန်းတမ်းဖတ်ခြင်းဆိုင်ရာ အထောက်အကူပစ္စည်းများ
O. Goldreich၊ ရှုပ်ထွေးမှုသီအိုရီနိဒါန်း-
https://www.wisdom.weizmann.ac.il/~oded/cc99.html
သီးခြားသင်္ချာဘာသာရပ်အတွက် အထောက်အကူဖြစ်စေသော သင်ရိုးညွှန်းတမ်းဖတ်ခြင်းဆိုင်ရာပစ္စည်းများ
J. Aspnes၊ သီးခြားသင်္ချာဆိုင်ရာ မှတ်စုများ
https://www.cs.yale.edu/homes/aspnes/classes/202/notes.pdf
ဂရပ်သီအိုရီတွင် အထောက်အကူဖြစ်စေသော သင်ရိုးညွှန်းတမ်းဖတ်ခြင်းဆိုင်ရာပစ္စည်းများ
R. Diestel၊ ဂရပ်ဖစ်သီအိုရီ-
https://diestel-graph-theory.com/
EITC/IS/CCTF Computational Computational Complexity Theory Fundamentals ပရိုဂရမ်အတွက် အော့ဖ်လိုင်းကိုယ်ပိုင်သင်ယူမှုဆိုင်ရာ အပြည့်အစုံကို PDF ဖိုင်တွင် ဒေါင်းလုဒ်လုပ်ပါ။
EITC/IS/CCTF ကြိုတင်ပြင်ဆင်ပစ္စည်းများ - စံဗားရှင်း
EITC/IS/CCTF ကြိုတင်ပြင်ဆင်ပစ္စည်းများ – ပြန်လည်သုံးသပ်မေးခွန်းများဖြင့် တိုးချဲ့ဗားရှင်း