သာတူညီမျှအချိန်ကိုအတည်ပြုခြင်းအား ညီမျှသောသတ်မှတ်မဟုတ်သော Turing စက်အဖြစ်သို့ မည်သို့ပြောင်းလဲနိုင်မည်နည်း။

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

သက်သေခံလက်မှတ်ကို ခန့်မှန်းပြီး ပေါင်းကိန်းအချိန်အတွင်း အတည်ပြုနိုင်သော စက်ကိုတည်ဆောက်ခြင်းဖြင့် သာတူညီမျှအချိန်စစ်ဆေးခြင်းအား ညီမျှသောသတ်မှတ်မဟုတ်သော Turing စက်အဖြစ်သို့ ပြောင်းလဲနိုင်သည်။ ဤပြောင်းလဲခြင်းသည် စက်အား ဖြစ်နိုင်သည့်လမ်းကြောင်းအားလုံးကို တစ်ပြိုင်နက်စူးစမ်းခွင့်ပြုသည့် အဆုံးအဖြတ်မဟုတ်သောတွက်ချက်မှုသဘောတရားအပေါ် အခြေခံထားသည်။

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

ယခု၊ သာတူညီမျှအချိန်စစ်ဆေးစနစ်ကို ညီမျှသော-အဆုံးအဖြတ်မရှိသော Turing စက်အဖြစ်သို့ ပြောင်းလဲရန်၊ ကျွန်ုပ်တို့သည် အဆုံးအဖြတ်မဟုတ်သော တွက်ချက်မှု၏ ဂုဏ်သတ္တိများကို ထည့်သွင်းစဉ်းစားရန် လိုအပ်ပါသည်။ အဆုံးအဖြတ်မရှိသော Turing စက်တွင်၊ အဆင့်တစ်ခုစီတွင်၊ စက်သည် များစွာသောပြည်နယ်များရှိနိုင်ပြီး ပြည်နယ်အများအပြားသို့ တစ်ပြိုင်နက်ကူးပြောင်းနိုင်သည်။ ၎င်းသည် စက်အား ဖြစ်နိုင်ချေရှိသော တွက်ချက်မှုလမ်းကြောင်းအားလုံးကို အပြိုင်စူးစမ်းနိုင်စေပါသည်။

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

ဒါကို ဥပမာတစ်ခုနဲ့ ဥပမာပြကြည့်ရအောင်။ ဂရပ်ရောင်ခြယ်ခြင်းပြဿနာအတွက် ကျွန်ုပ်တို့တွင် များပြားလှသောအချိန်ကို အတည်ပြုနိုင်သည်ဆိုပါစို့။ Verticer သည် ဂရပ်တစ်ခုနှင့် ၎င်း၏ ဒေါင်လိုက်များကို အရောင်ခြယ်ခြင်းအဖြစ် ယူဆောင်ပြီး ၎င်းသည် ကပ်လျက်ရှိသော ဒေါင်လိုက်များသည် အရောင်တူညီခြင်းမရှိကြောင်း အတည်ပြုခြင်းဖြင့် အရောင်ခြယ်ခြင်းမှန်ကန်ခြင်းရှိမရှိ စစ်ဆေးပေးပါသည်။

ဤအတည်ပြုစနစ်ကို အဆုံးအဖြတ်မရှိသော Turing စက်အဖြစ်သို့ ပြောင်းလဲရန်၊ ကျွန်ုပ်တို့သည် အရောင်အသွေးကို ခန့်မှန်းနိုင်သော စက်တစ်ခုကို တည်ဆောက်ကာ ဖြစ်နိုင်သည့်အရောင်အားလုံးကို တစ်ပြိုင်နက်တည်းတွင် စစ်မှန်ကြောင်းကို အတုယူပါသည်။ အရောင်ခြယ်ခြင်းမှ ကန့်သတ်ချက်များကို ကျေနပ်ပါက၊ သတ်မှတ်မဟုတ်သော စက်က လက်ခံသည်။ မဟုတ်ရင် ငြင်းတယ်။

ဤဥပမာတွင်၊ အဆုံးအဖြတ်မရှိသောစက်သည် မျဉ်းပြိုင်များကို ဒေါင်လိုက်သို့အရောင်များသတ်မှတ်ပေးခြင်းဖြင့် အရောင်ခြယ်ခြင်းကို ခန့်မှန်းပေးမည်ဖြစ်သည်။ ထို့နောက် ၎င်းသည် ဖြစ်နိုင်သည့်အရောင်တစ်ခုစီတွင် verifier ကို အတုယူကာ ရောင်စုံမှန်ကန်မှုရှိမရှိ စစ်ဆေးမည်ဖြစ်သည်။ ပုံသဏ္ဍာန်တစ်ခုခုကို လက်ခံပါက၊ အဆုံးအဖြတ်မရှိသော စက်က လက်ခံသည်။

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

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

အခြား လတ်တလောမေးခွန်းများနှင့် အဖြေများ စာမေးပွဲသုံးသပ်ချက်:

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

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