ایا د شرایطو سره حساس ژبې د تورینګ ماشین لخوا پیژندل کیدی شي؟
د متن حساس ژبې (CSLs) د رسمي ژبو ټولګي دي چې د شرایطو حساس ګرامرونو لخوا تعریف شوي. دا ګرامرونه د شرایطو څخه پاک ګرامرونو عمومي کول دي، د تولید قواعدو ته اجازه ورکوي چې کولی شي یو تار د بل تار سره بدل کړي، په دې شرط چې بدیل په ځانګړي شرایطو کې واقع شي. د ژبو دا طبقه په کمپیوټري تیوري کې د پام وړ ده ځکه چې دا ډیر دی
- خپور شوی د سایبرسنیت, EITC/IS/CCTF د کمپیوټري پیچلتیا تیوري اساسات, د تورو ماشینونه, د ټورینګ ماشینونو معرفي کول
ایا د PSPACE ټولګي د EXPSPACE ټولګي سره مساوي ندي؟
دا پوښتنه چې ایا د PSPACE ټولګي د EXPSPACE ټولګي سره مساوي ندي د کمپیوټري پیچلتیا تیوري کې یوه اساسي او نه حل شوې ستونزه ده. د هراړخیز پوهاوي چمتو کولو لپاره، دا اړینه ده چې د دې پیچلتیا ټولګیو تعریفونه، ملکیتونه، او اغیزې په پام کې ونیول شي، او همدارنګه د ځای پیچلتیا پراخه شرایط. تعریفونه او بنسټیز
ایا د P پیچلتیا ټولګي د PSPACE ټولګي فرعي سیټ دی؟
د کمپیوټري پیچلتیا تیوري په ساحه کې، د پیچلتیا ټولګیو P او PSPACE ترمنځ اړیکه د مطالعې بنسټیز موضوع ده. د دې پوښتنې د حل لپاره چې ایا د P پیچلتیا ټولګي د PSPACE ټولګي فرعي سیټ دی یا که دواړه ټولګي ورته وي، دا اړینه ده چې تعریفونه او ملکیتونه په پام کې ونیول شي.
ایا په PSPACE کې ستونزې شتون لري د کوم لپاره چې د NP الګوریتم پیژندل شوی نه دی؟
د کمپیوټري پیچلتیا تیوري په ساحه کې، په ځانګړې توګه کله چې د ځای پیچلتیا ټولګي معاینه کوي، د PSPACE او NP ترمنځ اړیکه د پام وړ ګټو ده. د پوښتنې په مستقیم ډول حل کولو لپاره: هو، په PSPACE کې ستونزې شتون لري د کوم لپاره چې د NP الګوریتم پیژندل شوی نه دی. دا ادعا د دې پیچلتیا ټولګیو ترمنځ په تعریفونو او اړیکو کې ریښه لري.