Клас PSPACE не роўны класу EXPSPACE?
Пытанне аб тым, ці клас PSPACE не роўны класу EXPSPACE, з'яўляецца фундаментальнай і нявырашанай праблемай у тэорыі складанасці вылічэнняў. Каб забяспечыць поўнае разуменне, вельмі важна ўлічваць азначэнні, уласцівасці і наступствы гэтых класаў складанасці, а таксама больш шырокі кантэкст касмічнай складанасці.
Азначэнні і асноўныя ўласцівасці
PSPACE: Клас PSPACE складаецца з усіх праблем рашэнняў, якія могуць быць вырашаны машынай Цьюрынга з выкарыстаннем паліномнай колькасці прасторы. Фармальна мова L знаходзіцца ў PSPACE, калі існуе машына Цьюрынга M і мнагачленная функцыя p(n), такая што для кожнага ўводу x машына M вырашае, ці знаходзіцца x у L, выкарыстоўваючы не больш за p(|x|) прасторы. PSPACE ахоплівае шырокі спектр праблем, у тым ліку тыя, якія вырашаюцца за палінаміяльны час (P), і тыя, якія поўныя для PSPACE, такія як задача колькаснай лагічнай формулы (QBF).
EXPSPACE: Клас EXPSPACE уключае ўсе задачы рашэння, якія могуць быць вырашаны машынай Цьюрынга з выкарыстаннем экспанентнай колькасці прасторы. У прыватнасці, мова L знаходзіцца ў EXPSPACE, калі існуе машына Цьюрынга M і экспанентная функцыя f(n), такая што для кожнага ўводу x машына M вырашае, ці знаходзіцца x у L, выкарыстоўваючы не больш за 2^f(|x|) прасторы. EXPSPACE з'яўляецца больш шырокім класам, чым PSPACE, паколькі ён дазваляе займаць экспанентна больш месца, дазваляючы вырашаць больш шырокі спектр задач.
Адносіны паміж PSPACE і EXPSPACE
Каб зразумець сувязь паміж PSPACE і EXPSPACE, важна прызнаць іерархію класаў касмічнай складанасці. Па вызначэнні, PSPACE змяшчаецца ў EXPSPACE, таму што любую праблему, якую можна вырашыць з дапамогай паліномнай прасторы, таксама можна вырашыць з дапамогай экспанентнай прасторы. Фармальна 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 супраць NP з'яўляецца цэнтральным адкрытым пытаннем у гэтай галіне. Адносіны ўтрымлівання паміж гэтымі класамі рэзюмуюцца наступным чынам:
– P ⊆ NP ⊆ PSPACE ⊆ EXPSPACE
У дадатак да гэтых класаў існуюць іншыя важныя класы складанасці прасторы, такія як L (лагарыфмічная прастора) і NL (недэтэрмінаваная лагарыфмічная прастора), якія з'яўляюцца падмноствамі PSPACE. Адносіны паміж гэтымі класамі дадаткова ілюструюць іерархію вылічальнай складанасці, заснаваную на патрабаваннях да прасторы.
Пытанне аб тым, ці не роўны PSPACE і EXPSPACE, з'яўляецца фундаментальнай і нявырашанай праблемай у тэорыі складанасці вылічэнняў. У той час як тэарэма прасторавай іерархіі дае важкія доказы таго, што PSPACE строга ўтрымліваецца ў EXPSPACE, фармальны доказ строгай няроўнасці PSPACE ≠ EXPSPACE застаецца няўлоўным. Даследаванне гэтага пытання пралівае святло на больш шырокі ландшафт класаў складанасці і неад'емныя праблемы доказу падзелу паміж імі.
Іншыя апошнія пытанні і адказы адносна складанасць:
- Ці з'яўляецца клас складанасці P падмноствам класа PSPACE?
- Ці можам мы даказаць, што класы Np і P аднолькавыя, знайшоўшы эфектыўнае паліномнае рашэнне для любой поўнай задачы NP на дэтэрмінаванай TM?
- Ці можа клас NP быць роўны класу EXPTIME?
- Ці ёсць у PSPACE праблемы, для якіх не вядомы алгарытм NP?
- Ці можа праблема SAT быць поўнай праблемай NP?
- Ці можа праблема знаходзіцца ў класе складанасці NP, калі існуе недэтэрмінаваная машына Цьюрынга, якая вырашыць яе за паліномны час
- NP - гэта клас моў, якія маюць паліномныя праверкі часу
- Ці аднолькавы клас складанасці P і NP?
- Ці кожная кантэкстна-свабодная мова ў класе складанасці P?
- Ці існуе супярэчнасць паміж вызначэннем NP як класа задач рашэння з праверкамі паліномнага часу і тым фактам, што задачы ў класе P таксама маюць праверкі паліномнага часу?
Больш пытанняў і адказаў глядзіце ў Complexity