NP د ژبو ټولګي ده چې د پولینومیل وخت تصدیق کونکي لري
د NP ټولګي، چې د "غیر ارادي پولینومیل وخت" لپاره ولاړ دی، د کمپیوټري پیچلتیا تیوري کې یو بنسټیز مفهوم دی، د تیوري کمپیوټر ساینس فرعي ساحه. د NP د پوهیدو لپاره، یو څوک باید لومړی د پریکړې ستونزو مفکوره درک کړي، کوم چې د هو یا نه ځواب سره پوښتنې دي. په دې شرایطو کې یوه ژبه د ځینې الفبا په اوږدو کې د تارونو سیټ ته اشاره کوي، چیرې چې هر تار د پریکړې ستونزې یوه بیلګه کوډ کوي.
یوه ژبه (L) ته ویل کیږي چې په NP کې وي که چیرې د (L) لپاره د پولینومیل وخت تصدیق کونکی شتون ولري. یو تصدیق کونکی یو ټاکونکی الګوریتم (V) دی چې دوه انډولونه اخلي: یو مثال (x) او یو سند (y). سند (y) د "شاهد" یا "ثبوت" په نوم هم پیژندل کیږي. تصدیق کونکی (V) ګوري چې ایا سند (y) تاییدوي چې (x) د ژبې (L) پورې اړه لري. په رسمی توګه، یوه ژبه (L) په NP کې ده که چیرې د پولینیم وخت الګوریتم (V) او یو پولی نومیال (p (n)) شتون ولري لکه د هر تار (x په L کې) لپاره، د (y) سره یو تار شتون لري. |y| leq p(|x|)) او (V(x, y) = 1). برعکس، د هر تار (x notin L) لپاره، هیڅ تار (y) شتون نلري لکه (V (x، y) = 1).
د دې مفکورې د روښانه کولو لپاره، د "بولین اطمینان" (SAT) مشهوره ستونزه په پام کې ونیسئ. د SAT ستونزه پوښتنه کوي چې آیا په ټاکل شوي بولین فورمول کې متغیرونو ته د ریښتیني ارزښتونو ګمارنه شتون لري لکه فورمول ریښتیني ارزوي. د SAT ستونزه په NP کې ده ځکه چې د بولین فورمول ( phi ) او د هغه متغیرونو ته د ریښتیني ارزښتونو یوه دنده ( الفا ) په پام کې نیولو سره، یو څوک کولی شي په پولینومیل وخت کې تصدیق کړي چې ایا ( الفا ) ( phi ) راضي کوي. دلته، مثال ( x ) د بولین فورمول ( phi ) دی، او سند ( y ) دنده ( الفا ) ده. تصدیق کوونکی (V) ګوري چې آیا (alpha) (phi) ریښتیا کوي، کوم چې د (phi) د اندازې په پام کې نیولو سره په پولینومیل وخت کې ترسره کیدی شي.
بله بیلګه یې د "همیلتونین لار" ستونزه ده. دا ستونزه پوښتنه کوي چې ایا په ورکړل شوي ګراف کې داسې لاره شتون لري چې په دقیق ډول یو ځل د هرې برخې څخه لیدنه کوي. د هامیلتونین لار ستونزه په NP کې هم ده ځکه چې د ګراف (G) او د عمودی ترتیب (P) په پام کې نیولو سره، یو څوک کولی شي په پولینومیال وخت کې تصدیق کړي چې ایا (P) په (G) کې د هامیلتونین لاره ده. په دې حالت کې، مثال (x) ګراف (G) دی، او سند (y) د عمودی ترتیب (P) دی. تصدیق کونکی (V) ګوري چې ایا (P) د هامیلتونین لاره جوړوي، کوم چې د (G) د اندازې په پام کې نیولو سره په پولینومیال وخت کې ترسره کیدی شي.
د پولینومیل وخت تصدیق کولو مفهوم خورا مهم دی ځکه چې دا د ستونزو مشخص کولو لپاره یوه لاره چمتو کوي کوم چې په مؤثره توګه د چک کولو وړ دي، حتی که د حل موندل ممکن په کمپیوټري توګه ناممکن وي. دا د مشهورې پوښتنې لامل کیږي چې ایا (P = NP) ، کوم چې پوښتنه کوي چې ایا هره ستونزه چې حل یې په پولینومیل وخت کې تایید کیدی شي په پولینومیل وخت کې هم حل کیدی شي. ټولګي (P) د تصمیم نیولو ستونزو څخه جوړه ده چې د ټاکل شوي تورینګ ماشین په واسطه په پولینومیل وخت کې حل کیدی شي. که ( P = NP ) ، نو دا به پدې معنی وي چې هره ستونزه د پولینومیل وخت تصدیق کونکي سره هم د پولینومیل وخت حل کونکی لري. دا پوښتنه د کمپیوټر ساینس کې یو له خورا مهم خلاص ستونزو څخه پاتې کیږي.
د NP یو له مهمو ځانګړتیاو څخه دا دی چې دا د پولینومیل وخت کمولو لاندې تړل کیږي. د یوې ژبې (L_1) څخه ژبې (L_2) ته د پولینومیال وخت کمول د پولینومیال وخت محاسبه وړ فعالیت (f) دی لکه (x په L_1 کې) که چیرې او یوازې که (f(x) په L_2 کې). که چیرې د (L_1) څخه (L_2) ته د پولینیم وخت کمښت شتون ولري او (L_2) په NP کې وي، نو (L_1) هم په NP کې دی. دا ملکیت د NP بشپړتیا په مطالعې کې مهم دی، کوم چې په NP کې "سخت" ستونزې پیژني. یوه ستونزه NP - بشپړه ده که چیرې دا په NP کې وي او په NP کې هره ستونزه په پولینومیل وخت کې کم کیدی شي. د SAT ستونزه لومړۍ ستونزه وه چې د NP بشپړتیا ثابته شوې، او دا د نورو ستونزو د NP بشپړتیا ثابتولو لپاره د اساس په توګه کار کوي.
د پولینومیال وخت تصدیق کولو مفکورې روښانه کولو لپاره، د "سب سیٹ سم" ستونزه په پام کې ونیسئ. دا ستونزه پوښتنه کوي چې ایا د ورکړل شوي بشپړو سیټ یوه فرعي سیټ شتون لري چې د ټاکل شوي هدف ارزښت سره سمون لري. د سبسیټ مجموعه ستونزه په NP کې ده ځکه چې د عددونو سیټ (S) ، د هدف ارزښت (t) ، او د (S) فرعي سیټ (S') په پام کې نیولو سره ، یو څوک کولی شي په پولینومیل وخت کې تصدیق کړي چې ایا د عناصرو مجموعه (s') مساوي (t). دلته مثال ( x ) جوړه ده ( ( S , t ) ، او سند ( y ) د ( S ' ). تصدیق کونکی (V) ګوري چې ایا په (S') کې د عناصرو مجموعه د (t) سره مساوي ده، کوم چې د (S) د اندازې په پام کې نیولو سره په پولینومیل وخت کې ترسره کیدی شي.
د پولینومیلیل وخت تصدیق کولو اهمیت د نظریاتي ملاحظاتو هاخوا پراخیږي. په عملي شرایطو کې، دا پدې مانا ده چې په NP کې د ستونزو لپاره، که وړاندیز شوی حل (سند) چمتو شي، دا په اغیزمنه توګه معاینه کیدی شي. دا د کریپټوګرافیک پروتوکولونو لپاره د پام وړ اغیزې لري، د اصلاح کولو ستونزې، او مختلف برخو کې چیرې چې د حل درستیت تایید کول مهم دي.
د لنډیز کولو لپاره، ټولګي NP د پریکړې ستونزې لري چې د هغې لپاره وړاندیز شوی حل په پولینومیال وخت کې د یو تعییناتي الګوریتم لخوا تایید کیدی شي. دا مفهوم د کمپیوټري پیچلتیا تیوري کې بنسټیز دی او د کمپیوټر ساینس دواړو نظري او عملي اړخونو لپاره ژورې اغیزې لري. د NP مطالعه، د پولینومیل وخت تصدیق، او اړونده مفکورې لکه د NP بشپړتیا د څیړنې یوه فعاله او مهمه برخه ده.
په اړه نورې وروستۍ پوښتنې او ځوابونه پیچلتیا:
- ایا د PSPACE ټولګي د EXPSPACE ټولګي سره مساوي ندي؟
- ایا د P پیچلتیا ټولګي د PSPACE ټولګي فرعي سیټ دی؟
- ایا موږ کولی شو ثابته کړو چې د Np او P ټولګي یو شان دي د یوې ټاکونکي TM په اړه د هرې NP بشپړې ستونزې لپاره د مؤثره پولینیم حل په موندلو سره؟
- ایا د NP ټولګي د EXPTIME ټولګي سره مساوي کیدی شي؟
- ایا په PSPACE کې ستونزې شتون لري د کوم لپاره چې د NP الګوریتم پیژندل شوی نه دی؟
- ایا د SAT ستونزه د NP بشپړه ستونزه کیدی شي؟
- ایا ستونزه د NP پیچلتیا ټولګي کې کیدی شي که چیرې یو غیر متقابل تورینګ ماشین شتون ولري چې دا به په پولینومیل وخت کې حل کړي
- ایا P او NP واقعیا د ورته پیچلتیا ټولګي دي؟
- ایا د P پیچلتیا ټولګي کې هر شرایط وړیا ژبه ده؟
- ایا د NP تعریف د ټولګي په توګه د پریکړو ستونزو د ټولګي په توګه د پولینیمیل وخت تصدیق کونکو سره تضاد شتون لري او دا حقیقت چې په ټولګي P کې ستونزې هم د پولینومیل وخت تصدیق کونکي لري؟
په پیچلتیا کې نورې پوښتنې او ځوابونه وګورئ