မသိသော NP algorithm မရှိသည့်အတွက် PSPACE တွင် ပြဿနာများရှိပါသလား။
ကွန်ပြူတာဆိုင်ရာ ရှုပ်ထွေးမှုသီအိုရီ၏နယ်ပယ်တွင်၊ အထူးသဖြင့် အာကာသရှုပ်ထွေးမှုအတန်းများကို စစ်ဆေးသောအခါတွင်၊ PSPACE နှင့် NP အကြားဆက်နွယ်မှုသည် သိသာထင်ရှားသောစိတ်ဝင်စားဖွယ်ဖြစ်သည်။ မေးခွန်းကိုတိုက်ရိုက်ဖြေရှင်းရန်- ဟုတ်ကဲ့၊ PSPACE တွင် NP algorithm မပါရှိသည့်အတွက် ပြဿနာများရှိပါသည်။ ဤပြောဆိုချက်သည် ဤရှုပ်ထွေးမှုအတန်းများကြားတွင် အဓိပ္ပါယ်ဖွင့်ဆိုချက်များနှင့် ဆက်နွယ်မှုများတွင် အမြစ်တွယ်နေပါသည်။
PSPACE သည် များပြားလှသော နေရာပမာဏကို အသုံးပြု၍ Turing စက်ဖြင့် ဖြေရှင်းနိုင်သော ဆုံးဖြတ်ချက်ပြဿနာများ အတန်းအစားဖြစ်သည်။ တစ်နည်းဆိုရသော်၊ input ၏အရွယ်အစားတွင် polynomial ဖြစ်သော memory ပမာဏကို အသုံးပြု၍ ဖြေရှင်းနိုင်သော algorithm တစ်ခုရှိလျှင် PSPACE တွင် ပြဿနာတစ်ခုရှိသည်။ ဤအတန်းတွင် ပြဿနာမျိုးစုံကို လွှမ်းခြုံထားပြီး အချို့မှာ အလွန်ရှုပ်ထွေးပြီး ရှုပ်ထွေးသော တွက်ချက်မှုဆိုင်ရာ လုပ်ငန်းစဉ်များ ပါဝင်ပါသည်။
အခြားတစ်ဖက်တွင်မူ NP သည် အဆိုပြုထားသောအဖြေကို အဆုံးအဖြတ်ပေးသော Turing စက်ဖြင့် ပေါင်းကိန်းအချိန်အတွင်း အတည်ပြုနိုင်သည့် ဆုံးဖြတ်ချက်ပြဿနာများ အမျိုးအစားဖြစ်သည်။ ဆိုလိုသည်မှာ တစ်စုံတစ်ဦးသည် NP တွင် ပြဿနာတစ်ခုအတွက် ကိုယ်စားလှယ်လောင်းတစ်ဦးကို သင့်အား ပေးဆောင်ပါက၊ အထူးသဖြင့် ထည့်သွင်းမှုအရွယ်အစားနှင့် ဆက်စပ်သော polynomial time တွင် အဆိုပါဖြေရှင်းချက်၏မှန်ကန်မှုကို လျင်မြန်စွာစစ်ဆေးနိုင်သည်။
ဤအတန်းနှစ်ခုကြားရှိ ဆက်စပ်မှုသည် NP သည် PSPACE ၏ အခွဲတစ်ခုဖြစ်သည်။ အကြောင်းမှာ polynomial time တွင် စစ်ဆေးနိုင်သည့် ပြဿနာမှန်သမျှကို polynomial space တွင်လည်း ဖြေရှင်းနိုင်သောကြောင့်ဖြစ်သည်။ အဘယ်ကြောင့်ဆိုသော် နားလည်ရန်၊ ပေါင်းကူး-အချိန်-စိစစ်သူသည် ထည့်သွင်းမှု၏ ပေါင်းကိန်းဘစ်အရေအတွက်နှင့် အဆိုပြုထားသော အဖြေကိုသာ ဖတ်နိုင်သည်ဟု သုံးသပ်ပါ။ ထို့ကြောင့် ၎င်းကို ဖတ်ပြီးသော ရာထူးများနှင့် ၎င်းလုပ်ဆောင်ခဲ့သည့် လုပ်ဆောင်ချက်များကို ခြေရာခံသည့် ပေါလီအမည်-အာကာသစက်ဖြင့် တုပနိုင်သည်။
သို့သော် စကားဝိုင်းသည် မှန်ကန်သည်ဟု မသိပါ။ ဆိုလိုသည်မှာ PSPACE သည် NP ၏ အစုခွဲတစ်ခု ဟုတ်မဟုတ် မသိပါ။ အမှန်မှာ၊ PSPACE တွင် NP တွင်မဟုတ်သောပြဿနာများပါရှိသည်၊ ၎င်းကိုတရားဝင်သက်သေမပြရသေးသော်လည်း၊ ဤယုံကြည်ချက်သည် များပြားလှသောနေရာဖြင့် ဖြေရှင်းနိုင်သော်လည်း ဖြေရှင်းရန် polynomial အချိန်ထက်ပို၍ လိုအပ်ပုံရသော PSPACE တွင် ပြဿနာများတည်ရှိမှုအပေါ် အခြေခံထားသည်။
NP တွင်ရှိဟုမသိရသော PSPACE ရှိ ပြဿနာတစ်ခု၏ canonical ဥပမာများထဲမှတစ်ခုမှာ Quantified Boolean Formula (QBF) ပြဿနာဖြစ်သည်။ QBF သည် NP-ပြီးပြည့်စုံသော Boolean ကျေနပ်မှုပြဿနာ (SAT) ၏ ယေဘုယျဖော်ပြချက်တစ်ခုဖြစ်သည်။ SAT သည် ပေးထားသော Boolean ဖော်မြူလာကို အမှန်ဖြစ်စေသည့် variable များအတွက် အမှန်တရားတန်ဖိုးများကို assignment များ ရှိမရှိ မေးနေသော်လည်း QBF သည် "x အားလုံးအတွက်၊ ဖော်မြူလာမှန်သည်" ကဲ့သို့သော variable များပေါ်တွင် nested quantifiers များပါ၀င်သည် ။ ဤအရေအတွက်ပမာဏများရှိနေခြင်းသည် QBF ကို သိသိသာသာ ပိုမိုရှုပ်ထွေးစေသည်။ QBF သည် PSPACE-ပြီးပြည့်စုံသည်၊ ဆိုလိုသည်မှာ PSPACE တွင် မည်သည့်ပြဿနာမဆို ခက်ခဲသည်။ QBF အတွက် NP အယ်လဂိုရီသမ်တစ်ခုရှိလျှင် NP သည် PSPACE နှင့် ညီမျှသည်ဟု အဓိပ္ပာယ်ဖွင့်ဆိုနိုင်သည်၊ ၎င်းသည် အထစ်အငေါ့ဖြစ်ပြီး ကျယ်ပြန့်စွာ ယူဆနိုင်ဖွယ်မရှိသည့် ရလဒ်ဖြစ်သည်။
နောက်ထပ်ဥပမာတစ်ခုကတော့ N x N ဘုတ်ပေါ်မှာ ကစားခဲ့တဲ့ စစ်တုရင် ဒါမှမဟုတ် Go လိုမျိုး ယေဘုယျပုံစံဂိမ်းတွေမှာ အနိုင်ရသူကို အဆုံးအဖြတ်ပေးမယ့် ပြဿနာပါ။ ဤပြဿနာများတွင် ဖြစ်နိုင်ချေရှိသော ရွေ့လျားမှုများနှင့် ဖွဲ့စည်းတည်ဆောက်ပုံများ ကိန်းဂဏန်းများ ပါဝင်သော်လည်း ဖြစ်နိုင်ချေရှိသော ဂိမ်းပြည်နယ်အားလုံးကို စနစ်တကျရှာဖွေခြင်းဖြင့် ပေါလီnomial space ကို အသုံးပြု၍ ဆုံးဖြတ်နိုင်ပါသည်။ ဤပြဿနာများသည် NP တွင်မရှိသော PSPACE တွင် ပြဿနာများရှိနေခြင်းကို ထပ်လောင်းညွှန်ပြနေပါသည်။
PSPACE အတွင်းရှိ အချို့သောပြဿနာများသည် NP အပြင်ဘက်ဟု ယူဆရသည့် အကြောင်းရင်းကို ပိုမိုနက်ရှိုင်းစွာ နက်ရှိုင်းစွာ စူးစမ်းလေ့လာရန်၊ အာကာသ-ဘောင်ခတ်ထားသော နှင့် အချိန်ကန့်သတ်ထားသော တွက်ချက်မှုများ၏ သဘောသဘာဝကို သုံးသပ်ကြည့်ပါ။ အသုံးပြုထားသောနေရာသည် ပေါလီnomially ကန့်သတ်ထားသရွေ့ Polynomial space သည် ဖြစ်နိုင်ချေရှိသော exponential အရေအတွက်ကို တွက်ချက်နိုင်သော အဆင့်များကို ခွင့်ပြုသည်။ ၎င်းသည် အချိန်ကို အများကိန်းဖြင့် ကန့်သတ်ထားသည့် NP နှင့် လုံးဝဆန့်ကျင်ဘက်ဖြစ်သည်။ QBF နှင့် ယေဘူယျအားဖြင့် ဂိမ်းများကဲ့သို့သော ကိန်းဂဏန်းကြီးမားသော နေရာများပေါ်တွင် ကျယ်ကျယ်ပြန့်ပြန့်ရှာဖွေမှုများပါ၀င်သည့် ပြဿနာများကို ဖြေရှင်းရန်အတွက် ကိန်းဂဏန်းအချိန်ကို အသုံးချနိုင်သည်။
ထို့အပြင်၊ PSPACE နှင့် NP အကြားခြားနားချက်ကို ပိုမိုပံ့ပိုးပေးသည့် ရှုပ်ထွေးသောသီအိုရီတည်ဆောက်မှုများလည်းရှိသည်။ ဥပမာအားဖြင့်၊ Chandra၊ Kozen နှင့် Stockmeyer မှ မိတ်ဆက်ထားသော အလှည့်အပြောင်းအယူအဆသည် အဆုံးအဖြတ်မဟုတ်သောဝါဒကို ယေဘူယျဖော်ပြပြီး အတန်း AP (အလှည့်အပြောင်း polynomial time) သို့ ဦးတည်သည်။ AP သည် PSPACE နှင့် ညီမျှကြောင်းပြသခဲ့ပြီး၊ ထို့ကြောင့် များပြားလှသော အာကာသတွက်ချက်မှုများ၏ စွမ်းအားအပေါ် ကွဲပြားသောရှုထောင့်ကို ပေးဆောင်သည်။ Alternation တွင် ဖြစ်တည်မှု နှင့် universal quantifiers ၏ အစီအစဥ် ပါဝင်သည်၊ QBF ၏ ဖွဲ့စည်းပုံကို ထင်ဟပ်ပြပြီး PSPACE ပြဿနာများတွင် မွေးရာပါ ရှုပ်ထွေးမှုကို ပြသသည်။
ရှုပ်ထွေးမှု အတန်းများကို ခွဲထုတ်ခြင်းသည် သီအိုရီ ကွန်ပြူတာသိပ္ပံတွင် အခြေခံဖွင့်ထားသော မေးခွန်းဖြစ်သည်ကိုလည်း သတိပြုသင့်သည်။ ကျော်ကြားသော P နှင့် NP ပြဿနာသည် ဤပိုမိုကျယ်ပြန့်သော စုံစမ်းစစ်ဆေးမှု၏ အထူးကိစ္စရပ်ဖြစ်သည်။ အလားတူပင်၊ NP သည် PSPACE နှင့် ညီမျှခြင်း ရှိ၊ မရှိ မေးခွန်းကို မဖြေရှင်းနိုင်သေးပါ။ သို့သော်လည်း ကျယ်ပြန့်သောလေ့လာမှုနှင့် သိထားသောပြဿနာများ၏ သဘောသဘာဝကို အခြေခံ၍ နယ်ပယ်အတွင်းရှိ သဘောတူညီမှုသည် PSPACE တွင် NP တွင်မဟုတ်သော ပြဿနာများပါ၀င်နေနိုင်ဖွယ်ရှိသည်။
PSPACE တွင် လူသိများသော NP အယ်လဂိုရီသမ်မရှိသည့် ပြဿနာများတည်ရှိမှုကို ဤရှုပ်ထွေးမှုအတန်းများကြားတွင် အဓိပ္ပါယ်ဖွင့်ဆိုမှုများနှင့် ဆက်စပ်မှုများအပြင် QBF နှင့် ယေဘုယျအားဖြင့် ဂိမ်းပြဿနာများကဲ့သို့ ခိုင်မာသောဥပမာများဖြင့် ပံ့ပိုးပေးထားသည်။ ဤနမူနာများသည် များပြားလှသောနေရာအတွင်း စီမံခန့်ခွဲနိုင်သော ရှုပ်ထွေးပြီး ဖြစ်နိုင်ချေရှိသော ကိန်းဂဏန်းတွက်ချက်မှုဆိုင်ရာ လုပ်ငန်းစဉ်များကို မီးမောင်းထိုးပြသော်လည်း များပြားလှသောအချိန်နှင့် ကန့်သတ်ထားရန် မဖြစ်နိုင်သောကြောင့် ၎င်းတို့ကို NP နယ်ပယ်အပြင်ဘက်တွင် ထားခြင်းဖြစ်သည်။
အခြား လတ်တလောမေးခွန်းများနှင့် အဖြေများ ရှုပ်ထွေး:
- PSPACE အတန်းသည် EXPSPACE အတန်းနှင့် မညီမျှပါသလား။
- P ရှုပ်ထွေးမှု အတန်းသည် PSPACE အတန်း၏ အစုခွဲတစ်ခုလား။
- အဆုံးအဖြတ်ပေးသော TM တွင် မည်သည့် NP ပြီးပြည့်စုံသော ပြဿနာအတွက် ထိရောက်သော polynomial ဖြေရှင်းချက်ကို ရှာဖွေခြင်းဖြင့် Np နှင့် P အတန်းသည် တူညီကြောင်း သက်သေပြနိုင်မလား။
- NP အတန်းသည် EXPTIME အတန်းနှင့် ညီမျှနိုင်ပါသလား။
- SAT ပြဿနာသည် NP ပြီးပြည့်စုံသောပြဿနာ ဖြစ်နိုင်ပါသလား။
- polynomial အချိန်အတွင်း ဖြေရှင်းပေးမည့် အဆုံးအဖြတ်မရှိသော turing machine တစ်ခုရှိလျှင် NP complexity class တွင် ပြဿနာရှိနိုင်ပါသလား။
- NP သည် polynomial time verifiers များပါရှိသော ဘာသာစကားများ၏ အတန်းအစားဖြစ်သည်။
- P နှင့် NP တို့သည် အမှန်တကယ် တူညီသော ရှုပ်ထွေးမှု အတန်းများ ဖြစ်ပါသလား။
- P complexity class ရှိ ဆက်စပ်ဘာသာစကားတိုင်းသည် အခမဲ့ဖြစ်ပါသလား။
- အများကိန်း-အချိန်စိစစ်မှုများဆိုင်ရာ ဆုံးဖြတ်ချက်ပြဿနာများဆိုင်ရာ အတန်းအစားတစ်ခုအဖြစ် NP ၏ အဓိပ္ပါယ်ဖွင့်ဆိုချက်နှင့် အတန်း P တွင် ပြဿနာများသည် များပြားလှသော-အချိန်စိစစ်မှုများလည်း ရှိသည်ဟူသောအချက်ကြားတွင် ကွဲလွဲမှုရှိပါသလား။
Complexity တွင် နောက်ထပ်မေးခွန်းများနှင့် အဖြေများကို ကြည့်ပါ။