ایا په PSPACE کې ستونزې شتون لري د کوم لپاره چې د NP الګوریتم پیژندل شوی نه دی؟
د کمپیوټري پیچلتیا تیوري په ساحه کې، په ځانګړې توګه کله چې د ځای پیچلتیا ټولګي معاینه کوي، د PSPACE او NP ترمنځ اړیکه د پام وړ ګټو ده. د پوښتنې په مستقیم ډول حل کولو لپاره: هو، په PSPACE کې ستونزې شتون لري د کوم لپاره چې د NP الګوریتم پیژندل شوی نه دی. دا ادعا د دې پیچلتیا ټولګیو ترمنځ په تعریفونو او اړیکو کې ریښه لري.
PSPACE د پریکړو د ستونزو ټولګي ده چې د ټورینګ ماشین په واسطه د پولینومیل ځای په کارولو سره حل کیدی شي. په بل عبارت، ستونزه په PSPACE کې ده که چیرې یو الګوریتم شتون ولري چې کولی شي دا د حافظې مقدار په کارولو سره حل کړي چې د ان پټ په اندازې کې پولینومیل وي. په دې ټولګي کې ډیری ستونزې شاملې دي، چې ځینې یې خورا پیچلي دي او پیچلي کمپیوټري پروسې پکې شاملې دي.
له بلې خوا، NP، د پریکړې د ستونزو ټولګي ده چې د وړاندیز شوي حل لپاره د ټاکل شوي تورینګ ماشین لخوا په پولینومیل وخت کې تایید کیدی شي. دا پدې مانا ده چې که څوک تاسو ته په NP کې د یوې ستونزې لپاره د نوماند حل وړاندې کوي، تاسو کولی شئ د دې حل سموالی په چټکۍ سره وګورئ، په ځانګړې توګه د انپټ اندازې په پرتله په پولینومیل وخت کې.
د دې دوو ټولګیو ترمنځ اړیکه داسې ده چې NP د PSPACE فرعي سیټ دی. دا ځکه چې کومه ستونزه چې په پولینومیل وخت کې تایید کیدی شي په پولینومیل ځای کې هم حل کیدی شي. د پوهیدو لپاره چې ولې، په پام کې ونیسئ چې د پولینومیال وخت تصدیق کونکی کولی شي یوازې د انپټ بټونو او وړاندیز شوي حلونو څو څو اړخیز شمیر ولولي. له همدې امله، دا د پولینیم - سپیس ماشین لخوا سمول کیدی شي کوم چې هغه موقعیتونه تعقیبوي چې دا لوستل شوي او هغه عملیات چې ترسره کړي.
په هرصورت، خبرې اترې ریښتیا نه پوهیږي؛ دا چې دا معلومه نده چې ایا PSPACE د NP فرعي سیټ دی. په حقیقت کې، دا په پراخه کچه باور لري چې PSPACE هغه ستونزې لري چې په NP کې ندي، که څه هم دا په رسمي توګه ثابت شوي ندي. دا باور په PSPACE کې د ستونزو د شتون پر بنسټ والړ دی چې داسې ښکاري چې د حل کولو لپاره د پولینومیال وخت څخه ډیر وخت ته اړتیا لري، که څه هم دوی د پولینیم ځای سره حل کیدی شي.
په PSPACE کې د ستونزې یوه کانونیکي مثال چې په NP کې نه پیژندل کیږي د Quantified Boolean Formula (QBF) ستونزه ده. QBF د بولین اطمیناني ستونزې (SAT) عمومي کول دي، کوم چې NP بشپړ دی. پداسې حال کې چې SAT پوښتنه کوي چې ایا د متغیرونو لپاره د ریښتیني ارزښتونو دنده شتون لري چې د بولین فورمول ریښتیا کوي، QBF د متغیرونو په اړه نیسټ شوي مقدارونه شاملوي، لکه "د ټولو x لپاره، داسې شتون شتون لري چې فورمول ریښتیا وي." د دې مقدار کونکي شتون QBF د پام وړ ډیر پیچلی کوي. QBF PSPACE بشپړ دی، پدې معنی چې دا په PSPACE کې د کومې ستونزې په څیر سخت دی. که چیرې د QBF لپاره د NP الګوریتم شتون ولري، نو دا به د دې معنی ولري چې NP د PSPACE سره مساوي وي، یوه پایله به د پام وړ وي او په پراخه کچه احتمال نه ګڼل کیږي.
بله بیلګه په عمومي ډول لوبو کې د ګټونکي ټاکلو ستونزه ده، لکه د شطرنج یا ګو عمومي نسخې چې په N x N بورډ کې لوبیږي. دا ستونزې په احتمالي ډول د حرکتونو او تشکیلاتو احتمالي شمیرې شاملې دي، مګر دوی کولی شي په سیستماتیک ډول د ټولو ممکنه لوبې حالتونو سپړلو سره د پولینومیل ځای په کارولو سره پریکړه وشي. دا ستونزې هم د PSPACE بشپړې دي، نور په PSPACE کې د ستونزو شتون وړاندیز کوي چې په NP کې شتون نلري.
د دې لپاره چې په PSPACE کې ځینې ستونزې د NP څخه بهر وي د ژورې توضیح کولو لپاره، د وخت پورې تړلې محاسبې په پرتله د ځای محدودیت طبیعت ته پام وکړئ. پولینومیل ځای د احتمالي احتمالي شمیرې محاسبې مرحلو ته اجازه ورکوي ، تر هغه چې کارول شوي ځای په پولی نومي ډول محدود وي. دا د NP سره په بشپړ ډول مخالف دی، چیرې چې وخت په پولي نوم پورې تړلی دی. د پولینومیلیل ځای لخوا اجازه ورکړل شوي احتمالي وخت د ستونزو حل کولو لپاره کارول کیدی شي چې په پراخه کچه لوی ځایونو کې پراخه لټونونه پکې شامل وي ، لکه هغه چې په QBF او عمومي لوبو کې ورسره مخ شوي.
سربیره پردې، پیچلي نظري جوړښتونه شتون لري چې د PSPACE او NP ترمنځ توپیر نور هم ملاتړ کوي. د مثال په توګه، د بدیل مفهوم، چې د چندرا، کوزین او سټاکمایر لخوا معرفي شوی، غیر متمرکزیت عمومي کوي او د AP ټولګي (د پولینومیل وخت بدیل) ته لار هواروي. دا وښودل شوه چې AP د PSPACE سره مساوي دی، په دې توګه د پولینومیلیل ځای کمپیوټرونو ځواک په اړه مختلف لید وړاندې کوي. په بدیل کې د موجود او نړیوال مقدارونو لړۍ شامله ده، د QBF جوړښت منعکس کوي، او د PSPACE ستونزو کې موجود پیچلتیا ښیې.
دا هم د یادولو وړ ده چې د پیچلتیا ټولګیو جلا کول په تیوریکي کمپیوټر ساینس کې یو بنسټیز خلاص پوښتنه ده. د مشهور P vs NP ستونزه د دې پراخې څیړنې یوه ځانګړې قضیه ده. په ورته ډول، دا پوښتنه چې ایا NP د PSPACE سره مساوي دی ناحل پاتې دی. په هرصورت، په ساحه کې توافق، د پراخې مطالعې او د پیژندل شویو ستونزو د نوعیت پر بنسټ، دا دی چې PSPACE احتمالي ستونزې لري چې په NP کې شتون نلري.
په PSPACE کې د ستونزو شتون د کوم لپاره چې هیڅ پیژندل شوي NP الګوریتم شتون نلري د دې پیچلتیا ټولګیو ترمنځ د تعریفونو او اړیکو لخوا مالتړ کیږي، او همدارنګه د کانکریټ مثالونو لکه QBF او عمومي لوبې ستونزې. دا مثالونه پیچلي او احتمالي احتمالي محاسبې پروسې په ګوته کوي چې په پولینومیال ځای کې اداره کیدی شي مګر امکان نلري چې په پولینومیل وخت پورې محدود وي ، پدې توګه دوی د NP له ساحې بهر ځای په ځای کوي.
په اړه نورې وروستۍ پوښتنې او ځوابونه پیچلتیا:
- ایا د PSPACE ټولګي د EXPSPACE ټولګي سره مساوي ندي؟
- ایا د P پیچلتیا ټولګي د PSPACE ټولګي فرعي سیټ دی؟
- ایا موږ کولی شو ثابته کړو چې د Np او P ټولګي یو شان دي د یوې ټاکونکي TM په اړه د هرې NP بشپړې ستونزې لپاره د مؤثره پولینیم حل په موندلو سره؟
- ایا د NP ټولګي د EXPTIME ټولګي سره مساوي کیدی شي؟
- ایا د SAT ستونزه د NP بشپړه ستونزه کیدی شي؟
- ایا ستونزه د NP پیچلتیا ټولګي کې کیدی شي که چیرې یو غیر متقابل تورینګ ماشین شتون ولري چې دا به په پولینومیل وخت کې حل کړي
- NP د ژبو ټولګي ده چې د پولینومیل وخت تصدیق کونکي لري
- ایا P او NP واقعیا د ورته پیچلتیا ټولګي دي؟
- ایا د P پیچلتیا ټولګي کې هر شرایط وړیا ژبه ده؟
- ایا د NP تعریف د ټولګي په توګه د پریکړو ستونزو د ټولګي په توګه د پولینیمیل وخت تصدیق کونکو سره تضاد شتون لري او دا حقیقت چې په ټولګي P کې ستونزې هم د پولینومیل وخت تصدیق کونکي لري؟
په پیچلتیا کې نورې پوښتنې او ځوابونه وګورئ