အတန်းအစား NP သည် အဆုံးအဖြတ်မဟုတ်သော Polynomial အချိန်အတွက် ရပ်တည်နေသည်၊ သည် တွက်ချက်မှုဆိုင်ရာ ရှုပ်ထွေးမှုသီအိုရီအတွက် အဓိကဖြစ်ပြီး ပေါင်းစည်း-အချိန်အတည်ပြုမှုဆိုင်ရာ ဆုံးဖြတ်ချက်ပြဿနာများကို လွှမ်းခြုံထားသည်။ ဆုံးဖြတ်ချက်ပြဿနာသည် ဟုတ်သည် သို့မဟုတ် မဟုတ်သည့် အဖြေတစ်ခု လိုအပ်ပြီး ဤအခြေအနေတွင် အတည်ပြုသူသည် ပေးထားသော အဖြေတစ်ခု၏ မှန်ကန်မှုကို စစ်ဆေးသည့် အယ်လဂိုရီသမ်တစ်ခုဖြစ်သည်။
ပြဿနာတစ်ခုဖြေရှင်းခြင်း (တွက်ချက်မှု) နှင့်အဖြေတစ်ခုစစ်ဆေးခြင်း (အတည်ပြုခြင်း) အကြားခွဲခြားရန်အရေးကြီးသည်။ NP တွင်၊ အဖြေတစ်ခု၏မှန်ကန်မှုကိုအတည်ပြုနိုင်သည့် polynomial-time verifier ရှိမရှိအပေါ်အာရုံစိုက်သည်။
Polynomial အချိန်ကိုကိုယ်စားပြုသည့် class P တွင်၊ polynomial time အတွင်း အဆုံးအဖြတ်ပေးသော Turing machine မှ ဖြေရှင်းနိုင်သော ဆုံးဖြတ်ချက်ပြဿနာများ ပါဝင်သည်။ ထို့ကြောင့် P တွင်ရှိသော ပြဿနာတိုင်းအတွက်၊ အဖြေတစ်ခုရှာဖွေရန် polynomial-time algorithm ရှိရုံသာမက အဖြေတစ်ခုအား အတည်ပြုရန် polynomial-time algorithm လည်းရှိသည်။
ကွဲလွဲပုံရသည်မှာ P တွင်ရှိသော ပြဿနာတိုင်းတွင် မွေးရာပါ ပေါလီnomial-time solving algorithm ပါရှိသည့် polynomial-time verifier လည်း ပိုင်ဆိုင်ကြောင်း သတိပြုမိပါသည်။ သို့သော်၊ ၎င်းသည် NP ၏အဓိပ္ပါယ်ကိုဆန့်ကျင်ခြင်းမရှိပါ။ NP ၏ အဓိပ္ပါယ်ဖွင့်ဆိုချက်မှာ အဖြေကိုရှာရန် အချိန်မည်မျှကြာမည်ကို မဆိုဘဲ ပေါလီnomial-time verifier ၏တည်ရှိမှုဖြစ်သည်။ ဤသည်မှာ P တွင်ရှိသော ပြဿနာအားလုံးသည် NP တွင်ရှိနေသည်ဆိုလိုသည်မှာ ၎င်းတို့၏ဖြေရှင်းချက်များကို အများကိန်းအချိန်များတွင် စစ်ဆေးနိုင်သောကြောင့်ဖြစ်သည်။
ဥပမာအားဖြင့်၊ အဓိကနံပါတ်စမ်းသပ်ခြင်းပြဿနာကို သုံးသပ်ကြည့်ပါ။ ဤပြဿနာကို နည်းလမ်းနှစ်မျိုးဖြင့် ဘောင်ခတ်ထားနိုင်သည်- အဓိကနံပါတ်များထုတ်ပေးခြင်းနှင့် ပေးထားသောနံပါတ်သည် အဓိကဖြစ်မဖြစ် စစ်ဆေးခြင်း။ Eratosthenes ၏ Sieve သည် သတ်မှတ်ထားသော ကန့်သတ်ချက်တစ်ခုအထိ ကိန်းဂဏန်းများအားလုံးကို အဓိကထုတ်လုပ်ရန် အယ်လဂိုရီသမ်တစ်ခုဖြစ်ပြီး ထိရောက်စွာလုပ်ဆောင်နိုင်သော်လည်း ၎င်း၏အချိန်ရှုပ်ထွေးမှုသည် တွက်ချက်မှုဆိုင်ရာရှုပ်ထွေးမှုသီအိုရီတွင်အသုံးပြုသည့် တင်းကျပ်သောသဘောဖြင့် ပေါင်း၍မဟုတ်ပေ။ P ၏ အဓိပ္ပါယ်ဖွင့်ဆိုချက်အရ မျဉ်းကြောင်းထက် ပိုကောင်းသော်လည်း O(n log log n) ဟု မကြာခဏ ရည်ညွှန်းလေ့ရှိပါသည်။ အခြားတစ်ဖက်တွင်၊ ပေးထားသောနံပါတ်သည် prime (prime number testing) ဖြစ်သည်၊ မတူညီသောအလုပ်တစ်ခု။ AKS primality test ကဲ့သို့သော ထိရောက်သော အယ်လဂိုရီသမ်များသည် သာမာန်အချိန်အတွင်း အတည်ပြုခြင်းအတွက် ခွင့်ပြုသည်။ ထို့ကြောင့်၊ ကိန်းဂဏန်းစမ်းသပ်ခြင်းပြဿနာသည် အတည်ပြုခြင်း၏အခြေအနေတွင်၊ အတန်းအစား P နှင့် NP တွင် ကျရောက်နေသည်၊ အကြောင်းမှာ အဖြေတစ်ခု (နံပါတ်တစ်ခုသည် အချုပ်အနှောင်ရှိမရှိ) ကို ပေါင်းကူးအမည်အချိန်အတွင်း အတည်ပြုနိုင်သောကြောင့် ဖြစ်သည်။ ယင်းက နံပါတ်စဉ်မျိုးဆက်နှင့် ပထမနံပါတ်စမ်းသပ်ခြင်းတို့သည် ဆက်စပ်နေသော်လည်း ၎င်းတို့တွင် တွက်ချက်မှုဆိုင်ရာ ရှုပ်ထွေးမှုဆိုင်ရာ ကွဲပြားသော ထည့်သွင်းစဉ်းစားမှုများ ပါဝင်ကြောင်း သက်သေပြနေသည်။
နိဂုံးချုပ်အားဖြင့်၊ NP ၏ အဓိပ္ပါယ်ဖွင့်ဆိုချက်သည် P ၏ သဘောသဘာဝနှင့် ကိုက်ညီနေပါသည်။ ခြားနားချက်သည် စိစစ်ခြင်းအဆင့်တွင် မဟုတ်ဘဲ အဖြေများရှာဖွေသည့် လုပ်ငန်းစဉ်တွင်ဖြစ်သည်- P ပြဿနာများသည် များပြားလှသောအချိန်များတွင် ဖြေရှင်း၍ရနိုင်သည်၊ NP ပြဿနာများရှိနေချိန်တွင်၊ polynomial time တွင် အတည်ပြုနိုင်သော်လည်း၊ ၎င်းတို့ကို polynomial time တွင် ဖြေရှင်းနိုင်သည်ဆိုသည်ကို အမြဲမသိနိုင်ပါ။
အခြား လတ်တလောမေးခွန်းများနှင့် အဖြေများ ရှုပ်ထွေး:
- PSPACE အတန်းသည် EXPSPACE အတန်းနှင့် မညီမျှပါသလား။
- P ရှုပ်ထွေးမှု အတန်းသည် PSPACE အတန်း၏ အစုခွဲတစ်ခုလား။
- အဆုံးအဖြတ်ပေးသော TM တွင် မည်သည့် NP ပြီးပြည့်စုံသော ပြဿနာအတွက် ထိရောက်သော polynomial ဖြေရှင်းချက်ကို ရှာဖွေခြင်းဖြင့် Np နှင့် P အတန်းသည် တူညီကြောင်း သက်သေပြနိုင်မလား။
- NP အတန်းသည် EXPTIME အတန်းနှင့် ညီမျှနိုင်ပါသလား။
- မသိသော NP algorithm မရှိသည့်အတွက် PSPACE တွင် ပြဿနာများရှိပါသလား။
- SAT ပြဿနာသည် NP ပြီးပြည့်စုံသောပြဿနာ ဖြစ်နိုင်ပါသလား။
- polynomial အချိန်အတွင်း ဖြေရှင်းပေးမည့် အဆုံးအဖြတ်မရှိသော turing machine တစ်ခုရှိလျှင် NP complexity class တွင် ပြဿနာရှိနိုင်ပါသလား။
- NP သည် polynomial time verifiers များပါရှိသော ဘာသာစကားများ၏ အတန်းအစားဖြစ်သည်။
- P နှင့် NP တို့သည် အမှန်တကယ် တူညီသော ရှုပ်ထွေးမှု အတန်းများ ဖြစ်ပါသလား။
- P complexity class ရှိ ဆက်စပ်ဘာသာစကားတိုင်းသည် အခမဲ့ဖြစ်ပါသလား။
Complexity တွင် နောက်ထပ်မေးခွန်းများနှင့် အဖြေများကို ကြည့်ပါ။