د پولینیومیال وخت غیر متقابل تورینګ ماشین څخه د پولینومیل وخت تصدیق کونکي رامینځته کولو پروسه تشریح کړئ.
د پولینیومیال وخت تصدیق کونکی د یو سیستماتیک پروسې په تعقیب د پولینومیل وخت غیر متقابل تورینګ ماشین (NTM) څخه جوړ کیدی شي. د دې پروسې د پوهیدو لپاره، دا اړینه ده چې د پیچلتیا تیورۍ مفکورې، په ځانګړې توګه د P او NP ټولګیو، او د پولینومیل تصدیق کولو مفکورې روښانه پوهه ولري.
د کمپیوټري پیچلتیا په تیوري کې، P د پریکړې ستونزې طبقې ته اشاره کوي چې په پولینومیل وخت کې د تعییناتي تورینګ ماشین لخوا حل کیدی شي. له بلې خوا، NP د پریکړې ستونزو ټولګي ته اشاره کوي د کوم لپاره چې حل د ټاکل شوي تورینګ ماشین لخوا په پولینومیل وخت کې تایید کیدی شي. د دې دوو ټولګیو ترمنځ کلیدي توپیر دا دی چې P هغه ستونزې څرګندوي چې په اغیزمنه توګه حل کیدی شي، پداسې حال کې چې NP هغه ستونزې استازیتوب کوي چې په اغیزمنه توګه تایید کیدی شي.
د پولینومیال وخت تصدیق کونکی یو ټاکونکی تورینګ ماشین دی چې کولی شي په پولینومیل وخت کې د NP ستونزې د حل سمتیا تصدیق کړي. د پولینومیال وخت NTM څخه د داسې تصدیق کونکي رامینځته کولو پروسه لاندې مرحلې لري:
1. د NP ستونزې ته په پام سره، راځئ چې ستونزه X ووایو، موږ فرض کوو چې د پولینیم وخت NTM M شتون لري چې کولی شي X حل کړي. دا NTM M د محاسبې څو څانګې لري، هر یو د مختلف ممکنه اجرا کولو لاره استازیتوب کوي.
2. موږ د NTM M چلند په انډول کولو سره د ستونزې X لپاره د پولینومیل وخت تصدیق کونکی V جوړوو. تصدیق کونکی V دوه آخذې اخلي: د ستونزې حل او یو سند. سند د دې ثبوت دی چې حل سم دی.
3. تصدیق کونکی V لومړی ګوري چې ایا سند معتبره بڼه لري. دا ګام په پولینومیال وخت کې ترسره کیدی شي ځکه چې تصدیق کونکی د سند متوقع جوړښت پیژني.
4. بیا، تصدیق کونکی V د ورکړل شوي حل او سند په اړه د NTM M چلند انډول کوي. دا د M د محاسبې ټولې ممکنه څانګې اجرا کوي، دا ګوري چې آیا کومه څانګه ان پټ مني. دا سمول په پولینومیل وخت کې ترسره کیدی شي ځکه چې NTM M په پولینومیل وخت کې تیریږي.
5. که چیرې تصدیق کونکی V د محاسبې لږترلږه یوه منل شوې څانګه ومومي، دا ان پټ مني. دا پدې مانا ده چې د حل حل تایید شوی ترڅو د ستونزې X لپاره سم وي. که نه نو، که چیرې هیڅ څانګه ونه مني، تصدیق کوونکی داخل ردوي.
د پولینومیل وخت تصدیق کونکي جوړولو ترشا کلیدي نظر دا دی چې NTM M کولی شي په پولینومیل وخت کې سم سند اټکل کړي. د M د چلند سمولو او د ټولو ممکنه څانګو په چک کولو سره، تصدیق کونکی V کولی شي په اغیزمنه توګه د حل درستیت تصدیق کړي.
راځئ چې د دې پروسې د روښانه کولو لپاره یو مثال واخلو. د دې معلومولو ستونزه په پام کې ونیسئ چې ایا ورکړل شوی ګراف د هامیلتونین دورې لري، کوم چې د NP بشپړ ستونزه ده. موږ ګومان کوو چې د پولینومیل وخت NTM M شتون کولی شي دا ستونزه حل کړي.
د دې ستونزې لپاره د پولینومیل وخت تصدیق کونکي V رامینځته کولو لپاره ، موږ په ورکړل شوي ګراف او سند کې د M چلند انډول کوو. تصدیق کونکی چک کوي چې ایا سند د اعتبار وړ هامیلتونین دورې استازیتوب کوي د دې تصدیق کولو سره چې دا په دقیق ډول یو ځل هر عمودی لیدنه کوي او دوره جوړوي.
د M د محاسبې د ټولو ممکنه څانګو په بشپړ ډول سمولو سره، تصدیق کوونکی کولی شي په اغیزمنه توګه معلومه کړي چې آیا ورکړل شوی ګراف د هامیلتونین دورې لري. که لږترلږه د M یوه څانګه داخله ومني، تصدیق کوونکی د اعتبار وړ هیملټونیان دورې په توګه ان پټ مني. که نه نو، دا ننوت ردوي.
د پولینومیال وخت NTM څخه د پولینومیل وخت تصدیق کونکي رامینځته کول د NTM چلند سمول کول او د محاسبې ټولې ممکنه څانګې چیک کول شامل دي. دا پروسه د NP ستونزو لپاره د حلونو اغیزمن تایید ته اجازه ورکوي. د دې ډول تصدیق کونکو په جوړولو سره، موږ کولی شو ستونزې په پولینومیل وخت کې د دوی د تصدیق کولو پراساس طبقه بندي کړو.
په اړه نورې وروستۍ پوښتنې او ځوابونه پیچلتیا:
- ایا د PSPACE ټولګي د EXPSPACE ټولګي سره مساوي ندي؟
- ایا د P پیچلتیا ټولګي د PSPACE ټولګي فرعي سیټ دی؟
- ایا موږ کولی شو ثابته کړو چې د Np او P ټولګي یو شان دي د یوې ټاکونکي TM په اړه د هرې NP بشپړې ستونزې لپاره د مؤثره پولینیم حل په موندلو سره؟
- ایا د NP ټولګي د EXPTIME ټولګي سره مساوي کیدی شي؟
- ایا په PSPACE کې ستونزې شتون لري د کوم لپاره چې د NP الګوریتم پیژندل شوی نه دی؟
- ایا د SAT ستونزه د NP بشپړه ستونزه کیدی شي؟
- ایا ستونزه د NP پیچلتیا ټولګي کې کیدی شي که چیرې یو غیر متقابل تورینګ ماشین شتون ولري چې دا به په پولینومیل وخت کې حل کړي
- NP د ژبو ټولګي ده چې د پولینومیل وخت تصدیق کونکي لري
- ایا P او NP واقعیا د ورته پیچلتیا ټولګي دي؟
- ایا د P پیچلتیا ټولګي کې هر شرایط وړیا ژبه ده؟
په پیچلتیا کې نورې پوښتنې او ځوابونه وګورئ