Ці з'яўляецца клас складанасці P падмноствам класа PSPACE?
У галіне тэорыі складанасці вылічэнняў ўзаемасувязь паміж класамі складанасці P і PSPACE з'яўляецца фундаментальнай тэмай вывучэння. Каб вырашыць пытанне аб тым, ці з'яўляецца клас складанасці P падмноствам класа PSPACE або абодва класы аднолькавыя, вельмі важна разгледзець азначэнні і ўласцівасці гэтых класаў і прааналізаваць іх узаемасувязі.
Клас складанасці P (Polynomial Time) складаецца з задач рашэння, якія могуць быць вырашаны дэтэрмінаванай машынай Цьюрынга за палінаміальны час. Фармальна мова L належыць да P, калі існуе дэтэрмінаваная машына Цьюрынга M і мнагачлен p(n), такі што для кожнага радка x, M вырашае, ці належыць x да L, не больш чым за p(|x|) крокаў, дзе | х| пазначае даўжыню радка x. Прасцей кажучы, задачы ў P могуць быць вырашаны эфектыўна, прычым неабходны час расце не больш чым паліномна з памерам уваходных дадзеных.
З іншага боку, PSPACE (палінаміальная прастора) ахоплівае задачы рашэння, якія могуць быць вырашаны машынай Цьюрынга з выкарыстаннем палінаміальнай колькасці прасторы. Мова L знаходзіцца ў PSPACE, калі існуе машына Цьюрынга M і мнагачлен p(n), такі што для кожнага радка x, M вырашае, ці належыць x L, выкарыстоўваючы не больш за p(|x|) прасторы. Характэрна, што час, неабходны для вылічэнняў, не абмежаваны мнагачленам; ёсць толькі прастора.
Каб зразумець сувязь паміж P і PSPACE, звярніце ўвагу на наступныя моманты:
1. Уключэнне P у PSPACE: Любая задача, якую можна вырашыць за паліномны час, таксама можа быць вырашана ў паліномнай прасторы. Гэта тлумачыцца тым, што дэтэрмінаваная машына Цьюрынга, якая вырашае задачу за паліномны час, будзе выкарыстоўваць не больш за шматчленнай прасторы, паколькі яна не можа выкарыстоўваць больш месца, чым колькасць крокаў, якія яна прымае. Такім чынам, P з'яўляецца падмноствам PSPACE. Фармальна P ⊆ PSPACE.
2. Патэнцыйная роўнасць P і PSPACE: Пытанне аб тым, ці роўна P PSPACE (P = PSPACE), з'яўляецца адной з асноўных адкрытых праблем у тэорыі складанасці вылічэнняў. Калі б P было роўна PSPACE, гэта азначала б, што ўсе задачы, якія можна вырашыць з дапамогай паліномнай прасторы, таксама можна вырашыць за палінамінальны час. Аднак у цяперашні час няма доказаў, якія б пацвярджалі або абвяргалі гэтую роўнасць. Большасць прыхільнікаў тэорыі складанасці лічаць, што P строга змяшчаецца ў PSPACE (P ⊊ PSPACE), што азначае, што ў PSPACE ёсць праблемы, якіх няма ў P.
3. Прыклады і наступствы: Разгледзім праблему вызначэння, ці з'яўляецца дадзеная колькасна вызначаная лагічная формула (QBF). Гэтая праблема, вядомая як TQBF (True Quantified Boolean Formula), з'яўляецца кананічнай задачай, поўнай PSPACE. Праблема з'яўляецца PSPACE-поўнай, калі яна знаходзіцца ў PSPACE, і кожная задача ў PSPACE можа быць зведзена да яе з дапамогай паліномнага скарачэння часу. Мяркуецца, што TQBF не знаходзіцца ў P, бо патрабуе ацэнкі ўсіх магчымых прызначэнняў праўдзівасці зменным, што звычайна немагчыма зрабіць за паліномны час. Аднак яе можна вырашыць з дапамогай паліномнай прасторы шляхам рэкурсіўнага вылічэння падформул.
4. Іерархія класаў складанасці: Адносіны паміж P і PSPACE можна лепш зразумець, разглядаючы больш шырокі кантэкст класаў складанасці. Клас NP (недэтэрмінаваны паліномны час) складаецца з задач рашэння, для якіх рашэнне можа быць праверана за паліномны час. Вядома, што P ⊆ NP ⊆ PПРАСТОРА. Аднак дакладныя адносіны паміж гэтымі класамі (напрыклад, P = NP або NP = PSPACE) застаюцца нявырашанымі.
5. Тэарэма Савіча: Важным вынікам у тэорыі складанасці з'яўляецца тэарэма Сэвіча, якая сцвярджае, што любая задача, вырашальная ў недэтэрмінаванай паліномнай прасторы (NPSPACE), таксама можа быць вырашана ў дэтэрмінаванай паліномнай прасторы. Фармальна NPSPACE = PSPACE. Гэтая тэарэма падкрэслівае трываласць класа PSPACE і падкрэслівае, што недэтэрмінізм не забяспечвае дадатковай вылічальнай магутнасці з пункту гледжання складанасці прасторы.
6. Практычныя наступствы: Разуменне ўзаемасувязі паміж P і PSPACE мае значныя наступствы для практычных вылічэнняў. Праблемы ў P лічацца эфектыўна вырашальнымі і падыходзяць для прыкладанняў у рэжыме рэальнага часу. Наадварот, праблемы ў PSPACE, хоць і вырашальныя з паліномнай прасторай, могуць патрабаваць экспанентнага часу, што робіць іх непрактычнымі для вялікіх уваходных дадзеных. Вызначэнне таго, ці ляжыць праблема ў P або PSPACE, дапамагае ў вызначэнні магчымасці пошуку эфектыўных алгарытмаў для рэальных прыкладанняў.
7. Кірункі даследаванняў: Вывучэнне пытання P супраць PSPACE працягвае заставацца актыўнай сферай даследаванняў. Дасягненні ў гэтай галіне могуць прывесці да прарыву ў разуменні фундаментальных межаў вылічэнняў. Даследчыкі вывучаюць розныя метады, такія як складанасць схем, інтэрактыўныя доказы і алгебраічныя метады, каб атрымаць уяўленне аб адносінах паміж класамі складанасці.
Клас складанасці P сапраўды з'яўляецца падмноствам PSPACE, бо любая задача, вырашальная за паліномны час, таксама можа быць вырашана ў паліномнай прасторы. Аднак, ці роўна P PSPACE, застаецца адкрытым пытаннем у тэорыі складанасці вылічэнняў. Пераважае меркаванне, што P строга змяшчаецца ў PSPACE, што паказвае на тое, што ў PSPACE ёсць праблемы, якія не ўваходзяць у P. Гэтая ўзаемасувязь мае глыбокія наступствы як для тэарэтычных, так і для практычных аспектаў вылічэнняў, накіроўваючы даследчыкаў у іх пошуках зразумець сапраўдную прыроду вылічальная складанасць.
Іншыя апошнія пытанні і адказы адносна складанасць:
- Клас PSPACE не роўны класу EXPSPACE?
- Ці можам мы даказаць, што класы Np і P аднолькавыя, знайшоўшы эфектыўнае паліномнае рашэнне для любой поўнай задачы NP на дэтэрмінаванай TM?
- Ці можа клас NP быць роўны класу EXPTIME?
- Ці ёсць у PSPACE праблемы, для якіх не вядомы алгарытм NP?
- Ці можа праблема SAT быць поўнай праблемай NP?
- Ці можа праблема знаходзіцца ў класе складанасці NP, калі існуе недэтэрмінаваная машына Цьюрынга, якая вырашыць яе за паліномны час
- NP - гэта клас моў, якія маюць паліномныя праверкі часу
- Ці аднолькавы клас складанасці P і NP?
- Ці кожная кантэкстна-свабодная мова ў класе складанасці P?
- Ці існуе супярэчнасць паміж вызначэннем NP як класа задач рашэння з праверкамі паліномнага часу і тым фактам, што задачы ў класе P таксама маюць праверкі паліномнага часу?
Больш пытанняў і адказаў глядзіце ў Complexity