Ці ёсць у PSPACE праблемы, для якіх не вядомы алгарытм NP?
У сферы тэорыі складанасці вылічэнняў, асабліва пры вывучэнні класаў касмічнай складанасці, сувязь паміж PSPACE і NP уяўляе вялікую цікавасць. Каб звярнуцца да пытання непасрэдна: так, у PSPACE ёсць праблемы, для якіх не існуе вядомага алгарытму NP. Гэта сцвярджэнне караніцца ў азначэннях і адносінах паміж гэтымі класамі складанасці.
PSPACE - гэта клас задач прыняцця рашэнняў, якія могуць быць вырашаны машынай Цьюрынга з выкарыстаннем паліномнай прасторы. Іншымі словамі, праблема знаходзіцца ў PSPACE, калі існуе алгарытм, які можа яе вырашыць, выкарыстоўваючы аб'ём памяці, палінаміальны па памеры ўводу. Гэты клас ахоплівае шырокі спектр праблем, некаторыя з якіх даволі складаныя і ўключаюць складаныя вылічальныя працэсы.
NP, з іншага боку, - гэта клас задач рашэння, для якіх прапанаванае рашэнне можа быць праверана за палінаміяльны час дэтэрмінаванай машынай Цьюрынга. Гэта азначае, што калі нехта прапануе вам варыянт рашэння задачы ў NP, вы можаце хутка праверыць правільнасць гэтага рашэння, у прыватнасці, за паліномны час адносна памеру ўваходных дадзеных.
Адносіны паміж гэтымі двума класамі такія, што NP з'яўляецца падмноствам PSPACE. Гэта адбываецца таму, што любая задача, якую можна праверыць за паліномны час, таксама можа быць вырашана ў паліномнай прасторы. Каб зразумець чаму, улічыце, што верыфікатар паліномнага часу можа счытваць толькі шматчленную колькасць бітаў уваходных дадзеных і прапанаванага рашэння. Такім чынам, гэта можа быць змадэлявана машынай паліномнай прасторы, якая адсочвае пазіцыі, якія яна прачытала, і аперацыі, якія яна выканала.
Аднак адваротнае не вядома; гэта значыць, невядома, ці з'яўляецца PSPACE падмноствам NP. На самай справе, шырока распаўсюджана меркаванне, што PSPACE змяшчае праблемы, якіх няма ў NP, хоць гэта не было фармальна даказана. Гэта перакананне заснавана на існаванні задач у PSPACE, для рашэння якіх патрабуецца больш часу, чым паліном, нават калі яны могуць быць вырашаны з дапамогай паліномнай прасторы.
Адным з кананічных прыкладаў праблемы ў PSPACE, якая, як вядома, не знаходзіцца ў NP, з'яўляецца задача колькаснай лагічнай формулы (QBF). QBF з'яўляецца абагульненнем лагічнай задачы выканальнасці (SAT), якая з'яўляецца NP-поўнай. У той час як SAT пытаецца, ці існуе прысваенне значэнняў праўдзівасці зменным, якое робіць дадзеную лагічную формулу праўдзівай, QBF уключае ўкладзеныя квантары над зменнымі, напрыклад, "для ўсіх x існуе такое ay, што формула праўдзівая". Наяўнасць гэтых квантыфікатараў робіць QBF значна больш складаным. QBF поўны PSPACE, што азначае, што ён такі ж складаны, як і любая праблема ў PSPACE. Калі б існаваў алгарытм NP для QBF, гэта азначала б, што NP роўна PSPACE, вынік, які быў бы наватарскім і шырока лічыцца малаверагодным.
Іншым паказальным прыкладам з'яўляецца праблема вызначэння пераможцы ў абагульненых гульнях, такіх як абагульненыя версіі шахмат або го, якія гуляюць на дошцы N x N. Гэтыя праблемы ўключаюць у сябе патэнцыйна экспанентную колькасць хадоў і канфігурацый, але іх можна вырашыць з дапамогай паліномнай прасторы шляхам сістэматычнага вывучэння ўсіх магчымых станаў гульні. Гэтыя праблемы таксама з'яўляюцца поўнымі для PSPACE, што сведчыць аб існаванні праблем у PSPACE, якіх няма ў NP.
Каб паглыбіцца ў тое, чаму пэўныя праблемы ў PSPACE лічацца па-за межамі NP, разгледзім прыроду абмежаваных прасторай у параўнанні з абмежаванымі ў часе вылічэннямі. Паліномная прастора дазваляе выкарыстоўваць патэнцыйна экспанентную колькасць вылічальных крокаў, пакуль выкарыстоўваная прастора застаецца паліномна абмежаванай. Гэта рэзка кантрастуе з NP, дзе час паліномна абмежаваны. Экспанентны час, дазволены паліномнай прасторай, можа быць выкарыстаны для вырашэння задач, якія ўключаюць вычарпальны пошук у экспаненцыяльна вялікіх прасторах, такіх як тыя, што сустракаюцца ў QBF і абагульненых гульнях.
Больш за тое, існуюць складаныя тэарэтычныя канструкцыі, якія дадаткова пацвярджаюць адрозненне паміж PSPACE і NP. Напрыклад, канцэпцыя альтэрнацыі, уведзеная Чандрай, Козенам і Стокмайерам, абагульняе недэтэрмінізм і вядзе да класа AP (альтэрнатыўны паліномны час). Было паказана, што AP роўна PSPACE, што забяспечвае іншы погляд на магутнасць вылічэнняў паліномнай прасторы. Чаргаванне ўключае паслядоўнасць экзістэнцыяльных і універсальных квантараў, якія адлюстроўваюць структуру QBF, і дэманструюць складанасць, уласцівую праблемам PSPACE.
Варта таксама адзначыць, што падзел класаў складанасці з'яўляецца фундаментальным адкрытым пытаннем у тэарэтычнай інфарматыцы. Знакамітая праблема P супраць NP з'яўляецца прыватным выпадкам гэтага больш шырокага даследавання. Аналагічным чынам застаецца нявырашаным пытанне аб тым, ці роўна NP PSPACE. Аднак кансенсус у гэтай галіне, заснаваны на шырокіх даследаваннях і характары вядомых праблем, заключаецца ў тым, што PSPACE, верагодна, змяшчае праблемы, якіх няма ў NP.
Існаванне праблем у PSPACE, для якіх не існуе вядомага алгарытму NP, пацвярджаецца азначэннямі і сувязямі паміж гэтымі класамі складанасці, а таксама канкрэтнымі прыкладамі, такімі як QBF і абагульненыя гульнявыя задачы. Гэтыя прыклады падкрэсліваюць складаныя і патэнцыйна экспанентныя вылічальныя працэсы, якімі можна кіраваць у полінаміяльнай прасторы, але наўрад ці будуць абмежаваныя палінаміальным часам, такім чынам, выводзячы іх за межы сферы NP.
Іншыя апошнія пытанні і адказы адносна складанасць:
- Клас PSPACE не роўны класу EXPSPACE?
- Ці з'яўляецца клас складанасці P падмноствам класа PSPACE?
- Ці можам мы даказаць, што класы Np і P аднолькавыя, знайшоўшы эфектыўнае паліномнае рашэнне для любой поўнай задачы NP на дэтэрмінаванай TM?
- Ці можа клас NP быць роўны класу EXPTIME?
- Ці можа праблема SAT быць поўнай праблемай NP?
- Ці можа праблема знаходзіцца ў класе складанасці NP, калі існуе недэтэрмінаваная машына Цьюрынга, якая вырашыць яе за паліномны час
- NP - гэта клас моў, якія маюць паліномныя праверкі часу
- Ці аднолькавы клас складанасці P і NP?
- Ці кожная кантэкстна-свабодная мова ў класе складанасці P?
- Ці існуе супярэчнасць паміж вызначэннем NP як класа задач рашэння з праверкамі паліномнага часу і тым фактам, што задачы ў класе P таксама маюць праверкі паліномнага часу?
Больш пытанняў і адказаў глядзіце ў Complexity