အများကိန်း-အချိန်စိစစ်မှုများဆိုင်ရာ ဆုံးဖြတ်ချက်ပြဿနာများဆိုင်ရာ အတန်းအစားတစ်ခုအဖြစ် NP ၏ အဓိပ္ပါယ်ဖွင့်ဆိုချက်နှင့် အတန်း P တွင် ပြဿနာများသည် များပြားလှသော-အချိန်စိစစ်မှုများလည်း ရှိသည်ဟူသောအချက်ကြားတွင် ကွဲလွဲမှုရှိပါသလား။
အတန်းအစား 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 တွင် ဖြေရှင်းနိုင်သည်ဆိုသည်ကို အမြဲမသိနိုင်ပါ။
အခြား လတ်တလောမေးခွန်းများနှင့် အဖြေများ NP နှင့် polynomial စစ်ဆေးနိုင်မှုအဓိပ္ပါယ်ဖွင့်ဆိုချက်:
- polynomial အချိန်အတွင်း ဖြေရှင်းပေးမည့် အဆုံးအဖြတ်မရှိသော turing machine တစ်ခုရှိလျှင် NP complexity class တွင် ပြဿနာရှိနိုင်ပါသလား။
- NP သည် polynomial time verifiers များပါရှိသော ဘာသာစကားများ၏ အတန်းအစားဖြစ်သည်။
- class P polynomial အတွက် verifier ရှိပါသလား။
- တွက်ချက်မှုဆိုင်ရာ ရှုပ်ထွေးမှုသီအိုရီတွင် အတန်း P နှင့် NP အကြား ကွာခြားချက်မှာ အဘယ်နည်း၊ ၎င်းတို့သည် ဘာသာစကားဖြင့် အဖွဲ့ဝင်ခြင်းကို ဆုံးဖြတ်ခြင်းနှင့် အတည်ပြုခြင်းဆိုင်ရာ သဘောတရားများနှင့် မည်သို့ဆက်စပ်နေသနည်း။
- သတ်မှတ်မဟုတ်သော Turing စက်တစ်ခုမှ ပေါလီnomial time verifier ကို တည်ဆောက်ခြင်း လုပ်ငန်းစဉ်ကို ဖော်ပြပါ။
- သာတူညီမျှအချိန်ကိုအတည်ပြုခြင်းအား ညီမျှသောသတ်မှတ်မဟုတ်သော Turing စက်အဖြစ်သို့ မည်သို့ပြောင်းလဲနိုင်မည်နည်း။
- အတန်း NP ၏ တူညီသော အဓိပ္ပါယ်ဖွင့်ဆိုချက်နှစ်ခုနှင့် ၎င်းတို့သည် များပြားလှသော အချိန်ကို စစ်ဆေးခြင်းနှင့် အဆုံးအဖြတ်မရှိသော Turing စက်များနှင့် မည်သို့သက်ဆိုင်ကြောင်း ရှင်းပြပါ။
- polynomial verifiability ဆိုတာ ဘာလဲ၊ ၎င်းသည် class NP နှင့် မည်သို့ဆက်စပ်နေသနည်း။