polynomial အချိန်အတွင်း ဖြေရှင်းပေးမည့် အဆုံးအဖြတ်မရှိသော turing machine တစ်ခုရှိလျှင် NP complexity class တွင် ပြဿနာရှိနိုင်ပါသလား။

/ / Published in ပြည်တွင်းသတင်း ဆိုက်ဘာလုံခြုံရေး, EITC/IS/CCTF တွက်ချက်မှုဆိုင်ရာ ရှုပ်ထွေးမှုသီအိုရီ အခြေခံအချက်များ, ရှုပ်ထွေး, NP နှင့် polynomial စစ်ဆေးနိုင်မှုအဓိပ္ပါယ်ဖွင့်ဆိုချက်

မေးခွန်းက "ပိုလီnomial အချိန်အတွင်း ဖြေရှင်းပေးမယ့် Turing စက်မရှိရင် NP complexity class မှာ ပြဿနာရှိနိုင်မလား။" ကွန်ပြူတာဆိုင်ရာ ရှုပ်ထွေးမှုသီအိုရီရှိ အခြေခံသဘောတရားများအပေါ် သက်ရောက်သည်။ ဤမေးခွန်းကို ကျယ်ကျယ်ပြန့်ပြန့်ဖြေရှင်းရန်၊ ကျွန်ုပ်တို့သည် NP ရှုပ်ထွေးမှုအတန်းအစား၏ အဓိပ္ပါယ်ဖွင့်ဆိုချက်များနှင့် ဝိသေသလက္ခဏာများနှင့် သတ်မှတ်ထားသောမဟုတ်သော Turing စက်များ (NDTMs) တို့၏ အခန်းကဏ္ဍကို ထည့်သွင်းစဉ်းစားရမည်ဖြစ်သည်။

NP ၏အဓိပ္ပါယ်

အတန်းအစား NP (သတ်မှတ်မဟုတ်သော ပိုလီအမည်အချိန်) တွင် ပေးထားသောအဖြေကို အဆုံးအဖြတ်ပေးသော Turing စက် (DTM) ဖြင့် ပိုလီအမည်အချိန်အတွင်း မှန်ကန်သည် သို့မဟုတ် မမှန်ကြောင်း အတည်ပြုနိုင်သည့် ဆုံးဖြတ်ချက်ပြဿနာများ ပါဝင်သည်။ တရားဝင်အားဖြင့်၊ ပြဿနာ၏ ဥပမာအတွက် ပေးထားသော လက်မှတ် (သို့မဟုတ် သက်သေ) ၏ မှန်ကန်မှုကို စစ်ဆေးနိုင်သည့် များပြားသော အချိန်-အတည်ပြုခြင်းဆိုင်ရာ အယ်လဂိုရီသမ်တစ်ခု ရှိလျှင် ဆုံးဖြတ်ချက်ပြဿနာသည် NP တွင် ရှိနေပါသည်။

သတ်မှတ်မဟုတ်သော Turing စက်များ

အဆုံးအဖြတ်မရှိသော Turing စက်သည် အဆုံးအဖြတ်ပေးသော Turing စက်၏ စွမ်းရည်များကို တိုးချဲ့ပေးသည့် သီအိုရီဆိုင်ရာ တွက်ချက်မှုပုံစံတစ်ခုဖြစ်သည်။ ၎င်း၏အကူးအပြောင်းလုပ်ဆောင်ချက်က သတ်မှတ်ထားသော တစ်ခုတည်းသော တွက်ချက်မှုလမ်းကြောင်းကို လိုက်နာသည့် DTM နှင့်မတူဘဲ၊ NDTM တစ်ခုသည် တွက်ချက်မှုလမ်းကြောင်းများစွာကို တစ်ပြိုင်နက်တည်း လိုက်နိုင်မည်ဖြစ်သည်။ အဆင့်တစ်ဆင့်ချင်းစီတွင်၊ NDTM သည် ဖြစ်နိုင်ချေရှိသော အကူးအပြောင်းအစုတစ်ခုမှ "ရွေးချယ်" နိုင်ပြီး၊ ဖြစ်နိုင်ချေရှိသော တွက်ချက်မှုများကို ပြိုင်တူရှာဖွေနိုင်မည်ဖြစ်သည်။

NDTMs မှ Polynomial-Time Solvability

input ၏အရွယ်အစားတွင် polynomial ဖြစ်သည့် အဆင့်များစွာအတွင်း ပြဿနာအတွက် အဖြေကိုရှာနိုင်သည့် အဆုံးအဖြတ်မဟုတ်သော algorithm တစ်ခုရှိလျှင် NDTM သည် polynomial time တွင် ဖြေရှင်းနိုင်သည်ဟု ဆိုသည်။ ဆိုလိုသည်မှာ ပြဿနာ၏ မည်သည့်ဥပမာအတွက်မဆို၊ NDTM သည် ပေါင်းကိန်းအချိန်အတွင်း အဖြေတစ်ခုဆီသို့ ဦးတည်သည့် တွက်ချက်မှုလမ်းကြောင်းကို စူးစမ်းလေ့လာနိုင်သည်။

NP နှင့် NDTMs အကြား ဆက်စပ်မှု

အတန်း NP ကို ​​NDTM ၏စည်းကမ်းချက်များ၌ တူညီစွာသတ်မှတ်နိုင်သည်။ အတိအကျပြောရလျှင်၊ ဆုံးဖြတ်ချက်ပြဿနာတစ်ခုသည် NP တွင် ပြဿနာကိုဖြေရှင်းနိုင်သော NDTM တစ်ခုရှိမှသာလျှင်ဖြစ်သည်။ ဤညီမျှမှုသည် NDTM သည် လက်မှတ်တစ်ခုကို အဆုံးအဖြတ်မရှိ ခန့်မှန်းနိုင်ပြီး ပေါင်းကိန်းအချိန်အတွင်း ၎င်းကို အဆုံးအဖြတ်ပေးနိုင်သည့်အချက်မှ ထွက်ပေါ်လာခြင်းဖြစ်သည်။

၎င်းကို ဥပမာတစ်ခုဖြင့် ဥပမာပြရန်၊ နာမည်ကြီး NP-ပြီးပြည့်စုံသော ပြဿနာ၊ Boolean ကျေနပ်နိုင်မှုပြဿနာ (SAT) ကို သုံးသပ်ကြည့်ပါ။ ပေါင်းစပ်ပုံမှန်ပုံစံ (CNF) တွင် Boolean ဖော်မြူလာကို ပေးထားသည့် အလုပ်မှာ ဖော်မြူလာကို အမှန်တကယ်ဖြစ်စေသော ကိန်းရှင်များအတွက် အမှန်တရားတန်ဖိုးများ ပေးအပ်ထားခြင်းရှိမရှိ ဆုံးဖြတ်ရန်ဖြစ်သည်။ NDTM သည် တာဝန်တစ်ခု၏ အမှန်တရားတန်ဖိုးများကို အဆုံးအဖြတ်မရှိ မှန်းဆပြီး ဖော်မြူလာအား ကျေနပ်မှုရှိမရှိ အဆုံးအဖြတ်ပေးခြင်းဖြင့် SAT ကို ဖြေရှင်းနိုင်သည် ။ မှန်းဆထားသော တာဝန်အောက်တွင် ဖော်မြူလာကို အကဲဖြတ်ခြင်း ပါ၀င်သော အတည်ပြုခြင်းအဆင့်သည် ပေါင်းကိန်းအချိန်အတွင်း လုပ်ဆောင်နိုင်ပါသည်။

NDTMs မှ Polynomial-Time Solvability ၏သက်ရောက်မှုများ

အထက်ဖော်ပြပါ အဓိပ္ပါယ်ဖွင့်ဆိုချက်များနှင့် NDTMs မှ NP နှင့် polynomial-time solvability အကြား ညီမျှမှုအား ပေးဆောင်ထားသောကြောင့်၊ polynomial time တွင် ပြဿနာတစ်ခုကို ဖြေရှင်းနိုင်သော NDTM တစ်ခုရှိလျှင် ပြဿနာသည် အမှန်ပင် NP တွင်ဖြစ်ကြောင်း ကျွန်ုပ်တို့ ကောက်ချက်ချနိုင်ပါသည်။ ထိုသို့သော NDTM တည်ရှိနေခြင်းသည် ပြဿနာအတွက် များစွာသောအချိန်စစ်ဆေးခြင်းဆိုင်ရာ အယ်လဂိုရီသမ်ရှိနေသည်ဟု ဆိုလိုသောကြောင့်ဖြစ်သည်။ NDTM ၏ အဆုံးအဖြတ်မဟုတ်သော မှန်းဆခြင်းအဆင့်သည် လက်မှတ်တစ်ခု၏ မျိုးဆက်နှင့် သက်ဆိုင်ပြီး အဆုံးအဖြတ်စိစစ်သည့်အဆင့်သည် ပေါင်းကိန်း-အချိန် အတည်ပြုခြင်းဆိုင်ရာ အယ်လဂိုရီသမ်နှင့် သက်ဆိုင်သည်။

နောက်ထပ် ထည့်သွင်းစဉ်းစားမှုများနှင့် ဥပမာများ

ဤသဘောတရားကို ပိုမိုရှင်းလင်းစေရန်၊ NP တွင် ပြဿနာများနှင့် NDTM များနှင့် ၎င်းတို့၏ ဆက်ဆံရေး၏ နောက်ထပ်ဥပမာများကို သုံးသပ်ကြည့်ကြစို့။

1. Hamiltonian လမ်းကြောင်းပြဿနာ− ဂရပ်တစ်ခုပေးထားသည့် Hamiltonian Path ပြဿနာသည် vertex တစ်ခုစီကို တစ်ကြိမ်တိတိလည်ပတ်သည့်လမ်းကြောင်းရှိမရှိ မေးသည်။ NDTM တစ်ခုသည် ကိန်းဂဏန်းတစ်ခုအား အဆုံးအဖြတ်မရှိ မှန်းဆပြီး ကိန်းဂဏန်းသည် မှန်ကန်သော Hamiltonian လမ်းကြောင်းဖြစ်မဖြစ် စစ်ဆေးခြင်းဖြင့် ဤပြဿနာကို ဖြေရှင်းနိုင်သည်။ အတည်ပြုခြင်းအဆင့်တွင် တစ်ဆက်တည်းရှိသော ဒေါင်လိုက်များ၏ ကပ်လျက်ကို စစ်ဆေးခြင်းနှင့် ဆုံမှတ်တစ်ခုစီကို တစ်ကြိမ်တိတိ တစ်ကြိမ်ရောက်ရှိကြောင်း သေချာစေခြင်း၊ နှစ်ခုစလုံးကို ပေါင်းကိန်းအချိန်အတွင်း လုပ်ဆောင်နိုင်သည်။

2. အစုခွဲ ပေါင်းလဒ် ပြဿနာ: ကိန်းပြည့်အစုတစ်ခုနှင့် ပစ်မှတ်ပေါင်းလဒ်ကို ပေးထားသည့် အစုခွဲပေါင်းစုပြဿနာသည် ပစ်မှတ်သို့ ပေါင်းသည့် ကိန်းပြည့်၏ အစုခွဲတစ်ခု ရှိမရှိ မေးမြန်းသည်။ NDTM သည် ကိန်းပြည့်၏ အစုခွဲတစ်ခုအား အဆုံးအဖြတ်မရှိ မှန်းဆပြီး အစုခွဲ၏ ပေါင်းလဒ်သည် ပစ်မှတ်နှင့် ညီမျှခြင်းရှိမရှိ စစ်ဆေးခြင်းဖြင့် ဤပြဿနာကို ဖြေရှင်းနိုင်သည်။ အတည်ပြုခြင်းအဆင့်တွင် မှန်းဆထားသော အစုခွဲ၏ အစိတ်အပိုင်းများကို ပေါင်းစည်းခြင်းပါဝင်ပြီး၊ ပေါင်းကိန်းအချိန်အတွင်း လုပ်ဆောင်နိုင်ပါသည်။

3. ဂရပ်ဖစ် အရောင်ခြယ်ခြင်း ပြဿနာ− ဂရပ်တစ်ခုနှင့် အရောင်များစွာကို ပေးထားသည့် Graph Coloring ပြဿနာသည် ကပ်လျက် ဒေါင်လိုက်နှစ်ခုကို တစ်ရောင်တည်းမတူညီသော ဂရပ်၏ ဒေါင်လိုက်များကို အရောင်ခြယ်ရန် ဖြစ်နိုင်ချေရှိမရှိ မေးမြန်းသည်။ NDTM သည် ဤပြဿနာကို ထောင့်စွန်းများသို့ အရောင်များသတ်မှတ်ခြင်းမပြုဘဲ အဆုံးအဖြတ်မပေးဘဲ အရောင်ခြယ်ခြင်းမှန်ကန်မှုရှိမရှိ စစ်ဆေးခြင်းဖြင့် ဤပြဿနာကို ဖြေရှင်းနိုင်ပါသည်။ အတည်ပြုခြင်းအဆင့်တွင် ကပ်လျက်ထောင့်စွန်းများ၏ အရောင်များကို စစ်ဆေးခြင်းပါဝင်ပြီး၊ ပေါင်းကိန်းအချိန်အတွင်း လုပ်ဆောင်နိုင်ပါသည်။

ကောက်ချက်

ပေးထားသော အဓိပ္ပါယ်ဖွင့်ဆိုချက်များနှင့် ဥပမာများကိုထောက်၍ polynomial time တွင်ဖြေရှင်းပေးမည့် Turing machine ရှိပါက ပြဿနာတစ်ခုသည် NP complexity class တွင် အမှန်ပင်ရှိနေနိုင်သည်ကို ရှင်းပါသည်။ ဤဆက်နွယ်မှုသည် တွက်ချက်မှုဆိုင်ရာ ရှုပ်ထွေးမှုသီအိုရီ၏ အခြေခံအုတ်မြစ်ဖြစ်ပြီး NDTMs ၏ polynomial-time solvability နှင့် NP အတန်းတွင်အသင်းဝင်မှုကြား ညီမျှမှုကို အလေးပေးဖော်ပြသည်။

အခြား လတ်တလောမေးခွန်းများနှင့် အဖြေများ NP နှင့် polynomial စစ်ဆေးနိုင်မှုအဓိပ္ပါယ်ဖွင့်ဆိုချက်:

နောက်ထပ်မေးခွန်းများနှင့် အဖြေများ-

အောက်တွင် tag လုပ်ခဲ့သည် , , , , ,