ایا د PSPACE ټولګي د EXPSPACE ټولګي سره مساوي ندي؟
دا پوښتنه چې ایا د PSPACE ټولګي د EXPSPACE ټولګي سره مساوي ندي د کمپیوټري پیچلتیا تیوري کې یوه اساسي او نه حل شوې ستونزه ده. د هراړخیز پوهاوي چمتو کولو لپاره، دا اړینه ده چې د دې پیچلتیا ټولګیو تعریفونه، ملکیتونه، او اغیزې په پام کې ونیول شي، او همدارنګه د ځای پیچلتیا پراخه شرایط.
تعریفونه او بنسټیز ملکیتونه
PSPACE: د PSPACE ټولګي د پریکړې ټولې ستونزې لري چې د ټورینګ ماشین لخوا د پولینومیال مقدار ځای په کارولو سره حل کیدی شي. په رسمی توګه، L ژبه په PSPACE کې ده که چیرې د تورینګ ماشین M او یو پولینیم فنکشن p(n) شتون ولري لکه د هر انپټ x لپاره، ماشین M پریکړه کوي چې آیا x په L کې په ډیری p(|x|) ځای کې کارول کیږي. PSPACE د ستونزو پراخه لړۍ پوښي، پشمول هغه ستونزې چې په پولینومیل وخت (P) کې د حل وړ دي او هغه چې د PSPACE لپاره بشپړ دي، لکه د Quantified Boolean Formula (QBF) ستونزه.
EXPSPACE: د EXPSPACE ټولګي کې ټولې پریکړې ستونزې شاملې دي چې د تورینګ ماشین لخوا د ځای په ځای کولو سره حل کیدی شي. په ځانګړې توګه، یوه ژبه L په EXPSPACE کې ده که چیرې د تورینګ ماشین M او د exponential فنکشن f(n) شتون ولري لکه د هر ان پټ x لپاره، ماشین M پریکړه کوي چې ایا x په L کې دی د 2^f(|x|) په کارولو سره. ځای EXPSPACE د PSPACE په پرتله لوی ټولګی دی، ځکه چې دا په چټکۍ سره ډیر ځای ته اجازه ورکوي، د پراخو ستونزو حل کولو توان ورکوي.
د PSPACE او EXPSPACE ترمنځ اړیکه
د PSPACE او EXPSPACE ترمنځ د اړیکو د پوهیدو لپاره، دا مهمه ده چې د ځای پیچلتیا ټولګیو درجه بندي پیژني. د تعریف له مخې، PSPACE په EXPSPACE کې شتون لري ځکه چې کومه ستونزه چې د پولینومیال ځای په کارولو سره حل کیدی شي د exponential space په کارولو سره حل کیدی شي. په رسمی توګه، PSPACE ⊆ EXPSPACE. په هرصورت، خبرې اترې اړین ندي چې ریښتیا وي؛ دا په پراخه توګه باور لري چې EXPSPACE هغه ستونزې لري چې د پولینومیل ځای په کارولو سره نشي حل کیدی، پدې معنی چې PSPACE ≠ EXPSPACE.
مثالونه او اغیزې
د QBF ستونزه په پام کې ونیسئ، کوم چې PSPACE بشپړ دی. پدې مسله کې د مقدار شوي بولین فارمول حقیقت معلومول شامل دي ، او دا د پولینومیل ځای په کارولو سره حل کیدی شي. څرنګه چې QBF PSPACE-بشپړ دی، په PSPACE کې کومه ستونزه په پولینومیال وخت کې QBF ته راټیټه کیدی شي. له بلې خوا، په EXPSPACE کې د ستونزې یوه بیلګه مګر په PSPACE کې اړینه نه ده چې د توزیع شوي ځای حدونو سره د تورینګ ماشینونو بدیل لپاره د لاسرسي ستونزه ده. دا ستونزه په ګړندۍ توګه ډیری تشکیلاتو تعقیب ته اړتیا لري ، کوم چې د پولینومیل ځای سره د امکان وړ ندي.
د فضا د درجې نظریه
د فضا د درجې نظریه د دې باور لپاره رسمي اساس چمتو کوي چې PSPACE په کلکه په EXPSPACE کې شتون لري. دا تیورم وايي چې د هر ډول فضا جوړونکي فنکشن f(n) لپاره، یوه ژبه شتون لري چې په خلا f (n) کې پریکړه کیدی شي مګر په خلا o (f (n) کې نه وي. د دې تیورم د f(n) = 2^n سره په تطبیق سره، موږ ترلاسه کوو چې په کفایتي ځای کې د حل وړ ستونزې شتون لري چې په هیڅ فرعي اکسپونینشل ځای کې نه شي حل کیدی، په شمول د پولینومیل ځای. له همدې امله، د فضا درجه بندي تیورم پدې معنی دی چې PSPACE په کلکه په EXPSPACE کې شامل دی، د بیلګې په توګه، PSPACE ⊂ EXPSPACE.
د PSPACE نه حل شوی نوعیت ≠ EXPSPACE
سره له دې چې د سپیس هیرارچي تیورم لخوا چمتو شوي قوي شواهدو سره، دا پوښتنه چې ایا PSPACE د EXPSPACE سره مساوي نه دی حل شوی پاتې دی. دا ځکه چې د سخت نابرابرۍ ثابتول PSPACE ≠ EXPSPACE به په EXPSPACE کې د یوې ځانګړې ستونزې شتون څرګندولو ته اړتیا ولري چې په PSPACE کې نشي حل کیدی، کوم چې تر اوسه نه دی بشپړ شوی. مشکل د پیچلتیا ټولګیو ترمنځ د جلا کیدو ثابتولو په اصلي ننګونو کې دی، د کمپیوټري پیچلتیا تیوري کې یو عام موضوع.
پراخ شرایط او اړوند پیچلتیا ټولګي
د PSPACE او EXPSPACE ترمنځ اړیکه د پیچلتیا ټولګیو په پراخه منظره کې متناسب کیدی شي. د مثال په توګه، د P ټولګي (ستونزې په پولي نومي وخت کې د حل وړ دي) د PSPACE فرعي سیټ دی، او په پراخه توګه باور کیږي چې P ≠ PSPACE. په ورته ډول، د ټولګي NP (غیر ټاکلي پولی نومیال وخت) هم په PSPACE کې شتون لري، او د مشهور P vs. NP ستونزه په ساحه کې مرکزي پرانیستې پوښتنه ده. د دې ټولګیو ترمنځ د کنټرول اړیکې په لاندې ډول لنډیز شوي دي:
– P ⊆ NP ⊆ PSPACE ⊆ EXPSPACE
د دې ټولګیو برسیره، د خلا د پیچلتیا نور مهم ټولګي شتون لري، لکه L (لوګاریتمیک ځای) او NL (غیر ټاکل شوي لوګاریتمیک ځای)، چې د PSPACE فرعي سیټونه دي. د دې ټولګیو ترمنځ اړیکې د ځای اړتیاوو پر بنسټ د کمپیوټري پیچلتیا درجه بندي نوره هم روښانه کوي.
دا پوښتنه چې ایا PSPACE د EXPSPACE سره مساوي نه دی د کمپیوټري پیچلتیا تیوري کې یوه اساسي او نه حل شوې ستونزه ده. په داسې حال کې چې د فضا د درجې تیوري قوي شواهد وړاندې کوي چې PSPACE په کلکه په EXPSPACE کې شتون لري، د PSPACE ≠ EXPSPACE د سخت نابرابرۍ رسمي ثبوت پټ پاتې دی. د دې پوښتنې سپړنه د پیچلتیا ټولګیو پراخه منظره او د دوی ترمینځ د جلا کیدو ثابتولو اصلي ننګونو باندې رڼا اچوي.
په اړه نورې وروستۍ پوښتنې او ځوابونه پیچلتیا:
- ایا د P پیچلتیا ټولګي د PSPACE ټولګي فرعي سیټ دی؟
- ایا موږ کولی شو ثابته کړو چې د Np او P ټولګي یو شان دي د یوې ټاکونکي TM په اړه د هرې NP بشپړې ستونزې لپاره د مؤثره پولینیم حل په موندلو سره؟
- ایا د NP ټولګي د EXPTIME ټولګي سره مساوي کیدی شي؟
- ایا په PSPACE کې ستونزې شتون لري د کوم لپاره چې د NP الګوریتم پیژندل شوی نه دی؟
- ایا د SAT ستونزه د NP بشپړه ستونزه کیدی شي؟
- ایا ستونزه د NP پیچلتیا ټولګي کې کیدی شي که چیرې یو غیر متقابل تورینګ ماشین شتون ولري چې دا به په پولینومیل وخت کې حل کړي
- NP د ژبو ټولګي ده چې د پولینومیل وخت تصدیق کونکي لري
- ایا P او NP واقعیا د ورته پیچلتیا ټولګي دي؟
- ایا د P پیچلتیا ټولګي کې هر شرایط وړیا ژبه ده؟
- ایا د NP تعریف د ټولګي په توګه د پریکړو ستونزو د ټولګي په توګه د پولینیمیل وخت تصدیق کونکو سره تضاد شتون لري او دا حقیقت چې په ټولګي P کې ستونزې هم د پولینومیل وخت تصدیق کونکي لري؟
په پیچلتیا کې نورې پوښتنې او ځوابونه وګورئ