NP သည် polynomial time verifiers များပါရှိသော ဘာသာစကားများ၏ အတန်းအစားဖြစ်သည်။

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

အတန်းအစား NP သည် "သတ်မှတ်မဟုတ်သော ပေါင်းကူးမျဥ်းအချိန်" ကို ကိုယ်စားပြုသည့် အတန်းအစား NP သည် တွက်ချက်မှုဆိုင်ရာ ရှုပ်ထွေးမှုသီအိုရီတွင် အခြေခံသဘောတရားတစ်ခုဖြစ်ပြီး သီအိုရီကွန်ပြူတာသိပ္ပံ၏နယ်ပယ်ခွဲတစ်ခုဖြစ်သည်။ NP ကိုနားလည်ရန်၊ Yes-or-no အဖြေရှိသော မေးခွန်းများဖြစ်သည့် ဆုံးဖြတ်ချက်ပြဿနာများ၏ သဘောတရားကို ဦးစွာနားလည်ရမည်ဖြစ်သည်။ ဤအကြောင်းအရာရှိ ဘာသာစကားတစ်ခုသည် အချို့သောအက္ခရာများပေါ်ရှိ စာကြောင်းတစ်အုပ်ကို ရည်ညွှန်းပြီး၊

(L) အတွက် polynomial-time verifier တစ်ခုရှိလျှင် ဘာသာစကား (L) သည် NP တွင်ရှိသည်ဟုဆိုသည်။ Verifier သည် instance (x) နှင့် certificate (y) နှစ်ခုကို ယူဆောင်သည့် အဆုံးအဖြတ်ပေးသည့် အယ်လဂိုရီသမ် (V) ဖြစ်သည်။ လက်မှတ် (y) ကို "သက်သေ" သို့မဟုတ် "အထောက်အထား" ဟုလည်း ခေါ်သည်။ အတည်ပြုသူ (V) သည် လက်မှတ် (y) သည် (x) သည် ဘာသာစကား (L) နှင့် သက်ဆိုင်ကြောင်း အတည်ပြုခြင်းရှိမရှိ စစ်ဆေးသည်။ ပုံမှန်အားဖြင့်၊ ဘာသာစကားတစ်ခု (L) သည် များစွာသောအချိန်ဆိုင်ရာ အယ်လဂိုရီသမ် (V) နှင့် polynomial (p(n)) ရှိလျှင် NP တွင်ရှိပြီး string တစ်ခုစီတွင် (x) တွင် (y) ပါရှိသည့် ( |y|။ leq p(|x|)) နှင့် (V(x၊ y) = 1)။ အပြန်အလှန်အားဖြင့်၊ string (x notin L) တိုင်းအတွက် (V(x၊ y) = 1) ဟူသော string (y) မရှိပါ။

ဤသဘောတရားကို ရှင်းလင်းရန်၊ "Boolean ကျေနပ်နိုင်မှု" (SAT) ၏ လူသိများသော ပြဿနာကို သုံးသပ်ကြည့်ပါ။ SAT ပြဿနာသည် ပေးထားသော Boolean ဖော်မြူလာတွင် ကိန်းရှင်များအတွက် အမှန်တရားတန်ဖိုးများ သတ်မှတ်ပေးထားသော ကိန်းရှင်များ ရှိမရှိ မေးမြန်းသည်။ SAT ပြဿနာသည် NP တွင်ရှိပြီး၊ Boolean ဖော်မြူလာ ( phi ) နှင့် ၎င်း၏ကိန်းရှင်များအတွက် အမှန်တရားတန်ဖိုးများ ( alpha ) ကိုပေးထားသောကြောင့် ( alpha ) ကျေနပ်သည်ဖြစ်စေ ( phi ) ကို ပေါင်း၍စစ်ဆေးနိုင်သည်။ ဤတွင်၊ ဥပမာ (x) သည် Boolean ဖော်မြူလာ ( phi ) ဖြစ်ပြီး လက်မှတ် ( y ) သည် တာဝန် ( alpha ) ဖြစ်သည်။ Verifier (V ) သည် ( alpha ) သည် ( phi ) ကို အမှန်ဟုတ်မဟုတ် စစ်ဆေးသည်၊ ၎င်းသည် ( phi ) အရွယ်အစားနှင့်စပ်လျဉ်း၍ ပေါင်းကိန်းအချိန်အတွင်း လုပ်ဆောင်နိုင်သည်။

နောက်ထပ်ဥပမာတစ်ခုကတော့ "Hamiltonian Path" ပြဿနာ။ ဤပြဿနာသည် ပေးထားသည့်ဂရပ်တစ်ခုတွင် လမ်းကြောင်းတစ်ခုရှိမရှိ ဒေါင်လိုက်တစ်ခုစီကို တစ်ကြိမ်တိတိသွားရောက်ကြည့်ရှုသည်။ Hamiltonian Path ပြဿနာသည် NP တွင်လည်း ရှိနေသောကြောင့်၊ ဂရပ် (G) နှင့် ဒေါင်လိုက်အစီအစဥ် (P) ကို ပေးထားသည့်အတွက် (P) သည် (G) ရှိ ဟာမီလ်တိုနီယန်လမ်းကြောင်းဟုတ်မဟုတ်ကို ပေါလီnomial အချိန်အတွင်း အတည်ပြုနိုင်သည်။ ဤကိစ္စတွင်၊ ဥပမာ (x) သည် ဂရပ် ( G ) ဖြစ်ပြီး လက်မှတ် ( y ) သည် ဒေါင်လိုက် ( P ) ၏ အစီစဉ်ဖြစ်သည်။ Verifier ( V ) သည် ( P ) သည် ( G ) အရွယ်အစားနှင့်စပ်လျဉ်း၍ ပေါလီnomial အချိန်အတွင်း လုပ်ဆောင်နိုင်သည့် Hamiltonian လမ်းကြောင်းကို ဖွဲ့ထားခြင်းရှိမရှိ စစ်ဆေးပေးသည်။

အဖြေကို တွက်ချက်၍မရနိုင်သော်လည်း ထိရောက်စွာ စစ်ဆေးနိုင်သော ပြဿနာများကို လက္ခဏာရပ်ပြရန် နည်းလမ်းတစ်ခု ပံ့ပိုးပေးသောကြောင့် များစွာသောအချိန်-အတည်ပြုနိုင်မှုသဘောတရားသည် အရေးကြီးပါသည်။ ဤသည်မှာ ( P = NP ) ဟူသော ကျော်ကြားသောမေးခွန်းကို ပေါလီnomial time တွင် စစ်ဆေးနိုင်သည့် ပြဿနာတိုင်းကို ပေါင်းကိန်းအချိန်အတွင်း ဖြေရှင်းနိုင်မလား။ အတန်း (P) တွင် အဆုံးအဖြတ်ပေးသော Turing စက်ဖြင့် polynomial time တွင် ဖြေရှင်းနိုင်သော ဆုံးဖြတ်ချက်ပြဿနာများ ပါဝင်သည်။ အကယ်၍ ( P = NP ) ၊ ပေါင်း၍ ကိန်းဂဏန်း-အချိန် စစ်ဆေးသည့် ပြဿနာတိုင်းတွင် ပေါင်းကိန်း-အချိန် ဖြေရှင်းသူလည်း ရှိသည်ဟု ဆိုလိုပါသည်။ ဤမေးခွန်းသည် ကွန်ပြူတာသိပ္ပံတွင် အရေးအကြီးဆုံးသော ပွင့်လင်းသော ပြဿနာများထဲမှ တစ်ခုအဖြစ် ကျန်ရှိနေပါသေးသည်။

NP ၏အဓိကဂုဏ်သတ္တိများထဲမှတစ်ခုမှာ၎င်းကို polynomial-time လျှော့ချမှုများအောက်တွင်ပိတ်ထားသည်။ ဘာသာစကား ( L_1 ) မှ ဘာသာစကား ( L_2 ) သို့ ပေါလီnomial-time လျှော့ချခြင်းသည် ( f ( x ) တွင် L_1 တွင်ဖြစ်လျှင် ( x ) တွင်သာ ၊ f ( x ) ၊ ပေါင်းကိန်းအချိန်တွက်ချက်နိုင်သောလုပ်ဆောင်ချက် ( f ) ဖြစ်သည်။ ( L_2 ) မှ ( L_1 ) သို့ နှင့် ( L_2 ) သည် NP တွင်ရှိနေပါက ( L_2 ) သည် NP တွင်လည်းရှိနေပါသည်။ ဤပိုင်ဆိုင်မှုသည် NP ရှိ "အခက်ခဲဆုံး" ပြဿနာများကို ဖော်ထုတ်ပေးသည့် NP-ပြီးပြည့်စုံမှုကို လေ့လာရာတွင် အရေးပါပါသည်။ ပြဿနာတစ်ခုသည် NP တွင်ရှိနေပါက NP-ပြီးမြောက်ပြီး NP ရှိပြဿနာတိုင်းကို ပေါင်းကိန်းအချိန်အတွင်း လျှော့ချနိုင်သည်။ SAT ပြဿနာသည် NP-ပြီးပြည့်စုံကြောင်း သက်သေပြခဲ့သည့် ပထမဆုံးပြဿနာဖြစ်ပြီး ၎င်းသည် အခြားပြဿနာများ၏ NP-ပြီးပြည့်စုံမှုကို သက်သေပြရန်အတွက် အခြေခံတစ်ခုဖြစ်သည်။

ကိန်းဂဏန်း-အချိန် အတည်ပြုနိုင်မှု သဘောတရားကို ထပ်လောင်းသရုပ်ဖော်ရန်၊ "Subset Sum" ပြဿနာကို ထည့်သွင်းစဉ်းစားပါ။ ဤပြဿနာသည် သတ်မှတ်ထားသော ပစ်မှတ်တန်ဖိုးသို့ ပေါင်းထားသော ပေးထားသော ကိန်းပြည့်အစု၏ အခွဲတစ်ခု ရှိမရှိ မေးသည်။ Subset Sum ပြဿနာသည် NP တွင်ရှိနေသောကြောင့်၊ ကိန်းပြည့်အစု (S)၊ ပစ်မှတ်တန်ဖိုး (t) နှင့် (S) ၏ခွဲခွဲ (S) တို့အား ကိန်းပြည့်အချိန်အတွင်း အတည်ပြုနိုင်သောကြောင့်၊ (၎) သည် (t) နှင့် ညီမျှသည်။ ဤတွင်၊ ဥပမာ (x) သည် အတွဲ ( (S, t) ) ဖြစ်ပြီး လက်မှတ် ( y ) သည် အတွဲ ( S ) ဖြစ်သည်။ Verifier ( V ) သည် ( S ) ရှိ ဒြပ်စင်များ၏ ပေါင်းလဒ် ( t ) နှင့် ညီမျှခြင်း ရှိ၊

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

အနှစ်ချုပ်ရရန်၊ class NP သည် အဆိုပြုထားသော အဖြေကို အဆုံးအဖြတ် algorithm ဖြင့် ပေါင်း၍အမည်အဖြစ် အတည်ပြုနိုင်သည့် ဆုံးဖြတ်ချက်ပြဿနာများကို လွှမ်းခြုံထားသည်။ ဤအယူအဆသည် ကွန်ပြူတာဆိုင်ရာ ရှုပ်ထွေးမှုသီအိုရီတွင် အခြေခံအကျဆုံးဖြစ်ပြီး ကွန်ပြူတာသိပ္ပံ၏ သီအိုရီနှင့် လက်တွေ့ကဏ္ဍနှစ်ခုစလုံးအတွက် လေးနက်သောသက်ရောက်မှုများရှိသည်။ NP ၏လေ့လာမှု၊ များစွာသောအချိန်အတည်ပြုနိုင်မှုနှင့် NP-ပြည့်စုံမှုကဲ့သို့သောဆက်စပ်အယူအဆများသည် တက်ကြွပြီး အရေးကြီးသော သုတေသနနယ်ပယ်တစ်ခုအဖြစ် ဆက်လက်တည်ရှိနေပါသည်။

အခြား လတ်တလောမေးခွန်းများနှင့် အဖြေများ ရှုပ်ထွေး:

Complexity တွင် နောက်ထပ်မေးခွန်းများနှင့် အဖြေများကို ကြည့်ပါ။

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

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