Ці кожная кантэкстна-свабодная мова ў класе складанасці P?
Пытанне аб тым, ці кожная кантэкстна-свабодная мова (CFL) знаходзіцца ў класе складанасці P, з'яўляецца захапляльнай тэмай у тэорыі складанасці вылічэнняў. Для комплекснага вырашэння гэтага пытання важна разгледзець вызначэнні кантэкстна-свабодных моў, клас складанасці P і сувязь паміж гэтымі паняццямі.
Кантэкстна-свабодная мова - гэта тып фармальнай мовы, які можа быць згенераваны кантэкстна-свабоднай граматыкай (CFG). CFG - гэта набор правілаў вытворчасці, якія апісваюць усе магчымыя радкі на дадзенай фармальнай мове. Кожнае правіла ў CFG замяняе адзін нетэрмінальны сімвал радком нетэрмінальных і тэрмінальных сімвалаў. Кантэкстна-свабодныя мовы маюць важнае значэнне ў інфарматыцы, таму што яны могуць апісаць сінтаксіс большасці моў праграмавання і распазнаюцца аўтаматамі ўніз.
Клас складанасці P складаецца з задач рашэння, якія могуць быць вырашаны дэтэрмінаванай машынай Цьюрынга за палінаміяльны час. Паліномны час, які пазначаецца як O(n^k), дзе n - памер уводу, а k - канстанта, уяўляе сабой верхнюю мяжу часавай складанасці алгарытму. Праблемы ў P лічацца эфектыўна вырашальнымі, таму што час, неабходны для іх рашэння, расце з кіраванай хуткасцю па меры павелічэння памеру ўводу.
Каб вызначыць, ці кожная кантэкстна-свабодная мова знаходзіцца ў P, мы павінны вывучыць вылічальныя рэсурсы, неабходныя для прыналежнасці да кантэкстна-свабоднай мовы. Праблема прыняцця рашэння для кантэкстна-свабоднай мовы звычайна фармулюецца наступным чынам: улічваючы радок w і кантэкстна-свабодную граматыку G, вызначыць, ці можа w быць згенераваны G.
Стандартным алгарытмам вызначэння прыналежнасці да кантэкстна-свабоднай мовы з'яўляецца алгарытм CYK (Коке-Янгера-Касамі), які з'яўляецца алгарытмам дынамічнага праграмавання. Алгарытм CYK працуе за час O(n^3), дзе n - даўжыня ўваходнага радка. Гэтая складанасць кубічнага часу ўзнікае з-за таго, што алгарытм стварае табліцу разбору, памеры якой прапарцыйныя даўжыні ўваходнага радка і колькасці нетэрмінальных сімвалаў у граматыцы.
Улічваючы, што алгарытм CYK працуе ў палінаміальным часе, вынікае, што праблема прыналежнасці для кантэкстна-свабодных моў можа быць вырашана ў палінаміальны час. Такім чынам, кантэкстна-свабодныя мовы сапраўды ўваходзяць у клас складанасці P. Гэты вынік важны, таму што ён паказвае, што кантэкстна-свабодныя мовы, якія з'яўляюцца больш выразнымі, чым звычайныя мовы, усё яшчэ могуць быць вырашаны эфектыўна.
Каб праілюстраваць гэта, разгледзім кантэкстна-свабодную мову L = {a^nb^n | n ≥ 0}, які складаецца з радкоў з роўнай колькасцю 'a', за якімі ідзе роўная колькасць 'b'. Кантэкстна-свабодная граматыка для гэтай мовы можа быць вызначана наступным чынам:
S → aSb | ε
Тут S - сімвал пачатку, а ε - пусты радок. Алгарытм CYK можа быць выкарыстаны, каб вызначыць, ці належыць дадзены радок w да L. Напрыклад, калі радок w = "aaabbb", алгарытм CYK пабудуе табліцу аналізу, каб праверыць, што w можа быць згенеравана граматыкай.
Акрамя таго, варта адзначыць, што некаторыя кантэкстна-свабодныя мовы могуць быць вырашаны нават больш эфектыўна, чым агульная часовая складанасць O(n^3) алгарытму CYK. Напрыклад, дэтэрмінаваныя кантэкстна-свабодныя мовы, якія ўяўляюць сабой падмноства кантэкстна-свабодных моў, якія распазнаюцца дэтэрмінаванымі аўтаматамі, часта могуць быць вырашаны за O(n) часу. Гэтая лінейная часовая складанасць узнікае з-за таго, што дэтэрмінаваныя аўтаматы ўніз маюць больш абмежаваную вылічальную мадэль, што дазваляе выкарыстоўваць больш эфектыўныя алгарытмы аналізу, такія як парсеры LR(k) або LL(k), якія выкарыстоўваюцца ў распрацоўцы кампілятара.
Праблема прыналежнасці для кантэкстна-свабодных моў можа быць вырашана за палінаміяльны час з выкарыстаннем такіх алгарытмаў, як алгарытм CYK, змяшчаючы кантэкстна-свабодныя мовы ў клас складанасці P. Гэты вынік падкрэслівае эфектыўнасць, з якой кантэкстна-свабодныя мовы могуць апрацоўвацца, робячы іх падыходзіць для прымянення ў аналізе сінтаксісу мовы праграмавання і іншых галінах, дзе патрабуецца фармальнае распазнаванне мовы.
Іншыя апошнія пытанні і адказы адносна складанасць:
- Клас PSPACE не роўны класу EXPSPACE?
- Ці з'яўляецца клас складанасці P падмноствам класа PSPACE?
- Ці можам мы даказаць, што класы Np і P аднолькавыя, знайшоўшы эфектыўнае паліномнае рашэнне для любой поўнай задачы NP на дэтэрмінаванай TM?
- Ці можа клас NP быць роўны класу EXPTIME?
- Ці ёсць у PSPACE праблемы, для якіх не вядомы алгарытм NP?
- Ці можа праблема SAT быць поўнай праблемай NP?
- Ці можа праблема знаходзіцца ў класе складанасці NP, калі існуе недэтэрмінаваная машына Цьюрынга, якая вырашыць яе за паліномны час
- NP - гэта клас моў, якія маюць паліномныя праверкі часу
- Ці аднолькавы клас складанасці P і NP?
- Ці існуе супярэчнасць паміж вызначэннем NP як класа задач рашэння з праверкамі паліномнага часу і тым фактам, што задачы ў класе P таксама маюць праверкі паліномнага часу?
Больш пытанняў і адказаў глядзіце ў Complexity