Ma her çarçoveyek zimanek azad e di pola tevliheviya P de?
Pirsa ka gelo her zimanek bê kontekst (CFL) di nav pola tevliheviya P de dimîne mijarek balkêş e di teoriya tevliheviya hesabkirinê de. Ji bo çareserkirina vê pirsê bi berfirehî, pêdivî ye ku meriv pênaseyên zimanên bê kontekst, çîna P-ya tevliheviyê, û têkiliya di navbera van têgehan de binirxîne.
Zimanek bê kontekst celebek zimanê fermî ye ku dikare ji hêla rêzimanek bê kontekst (CFG) ve were çêkirin. CFG komek rêzikên hilberînê ye ku hemî rêzikên gengaz bi zimanek fermî diyar dike. Her qaîdeyek di CFG de sembolek ne-termînalê bi rêzek sembolên ne-termînalê û termînalê diguhezîne. Zimanên bê navber di zanistiya komputerê de girîng in ji ber ku ew dikarin hevoksaziya piraniya zimanên bernamesaziyê diyar bikin û ji hêla otomatên pushdown ve têne nas kirin.
Dersa tevliheviyê P ji pirsgirêkên biryarê pêk tê ku dikarin di dema pirnomîal de bi makîneya Turing a diyarker ve werin çareser kirin. Dema pirnomî, wekî O(n^k) tê binavkirin ku n mezinahiya têketinê ye û k jî sabît e, li ser tevliheviya demê ya algorîtmê sînorek jorîn nîşan dide. Pirsgirêkên di P-ê de bi bandor têne çareser kirin têne hesibandin ji ber ku dema ku ji bo çareserkirina wan hewce dike bi rêjeyek rêveberî mezin dibe her ku mezinahiya têketinê zêde dibe.
Ji bo ku em diyar bikin ka her zimanek bê kontekst bi P-yê ye, divê em çavkaniyên jimartinê yên ku ji bo biryardana endametiya zimanek bê kontekst hewce ne lêkolîn bikin. Pirsgirêka biryarê ya ji bo zimanek bê kontekst bi gelemperî wiha tê destnîşan kirin: xêzek w û rêzimanek G-ya bê kontekst tê dayîn, diyar bikin ka w dikare ji hêla G ve were çêkirin.
Algorîtmaya standard a ji bo biryardana endametiya zimanek bê kontekst algorîtmaya CYK (Cocke-Younger-Kasami) ye, ku algorîtmayek bernamesaziya dînamîkî ye. Algorîtmaya CYK di dema O(n^3) de dixebite, ku n dirêjahiya rêzika têketinê ye. Ev tevliheviya dema kûp çêdibe ji ber ku algorîtm tabloyek parsek çêdike ku pîvanên wê bi dirêjahiya rêzika têketinê û hejmara sembolên ne-termînalê di rêzimanê de ne.
Ji ber ku algorîtmaya CYK di dema polînomî de dixebite, ji ber vê yekê pirsgirêka endametiyê ji bo zimanên bê kontekst dikare di dema pirnomî de were çareser kirin. Ji ber vê yekê, zimanên bê kontekst bi rastî jî di nav çîna P-ya tevliheviyê de ne. Ev encam girîng e ji ber ku ew destnîşan dike ku zimanên bê kontekst, yên ku ji zimanên birêkûpêk diyarkertir in, hîn jî dikarin bi bandor bêne biryardan.
Ji bo ronîkirina vê, zimanê bê kontekst L = {a^nb^n | n ≥ 0}, ku ji rêzikên bi jimareke wekhev a 'a'yê li pey jimareke wekhev a 'b'yê pêk tê. Rêzimaneke bê kontekst ji bo vî zimanî dikare wiha were pênase kirin:
S → aSb | e
Li vir, S sembola destpêkê ye, û ε rêzika vala temsîl dike. Algorîtmaya CYK dikare were bikar anîn da ku diyar bike ka rêzika w ya diyarkirî ya L ye yan na. Mînakî, ji ber rêzika w = "aaabbb", algorîtmaya CYK dê tabloyek parsek çêbike da ku verast bike ku w dikare ji hêla rêzimanê ve were çêkirin.
Wekî din, hêjayî gotinê ye ku hin zimanên bê kontekst dikarin ji tevliheviya dema gelemperî ya O(n^3) ya algorîtmaya CYK-ê jî bi bandortir biryar bidin. Mînakî, zimanên bê çarenûsa diyarker, ku binekomek zimanên bê kontekst in ku ji hêla otomatên determînîstîk ve têne naskirin, pir caran dikarin di dema O(n) de bêne biryardan. Ev tevliheviya dema xêzikî çêdibe ji ber ku otomatên determînîstîk ên pushdown-ê xwedan modelek hesabkerî ya bisînorkirî ne, ku rê dide algorîtmayên parskirinê yên bikêrtir ên wekî parserên LR(k) an LL(k) yên ku di sêwirana berhevkar de têne bikar anîn.
Pirsgirêka endametiyê ji bo zimanên bê kontekst bi karanîna algorîtmayên wekî algorîtmaya CYK-ê di dema pirnomî de dikare were çareser kirin, zimanên bê kontekst di nav çîna tevliheviyê P de bi cih bike. minasib ji bo sepanên di analîza hevoksaziya zimanê bernamesaziyê de û deverên din ên ku naskirina zimanê fermî lê hewce ye.
Pirs û bersivên din ên vê dawiyê di derbarê Tevlîheviyê:
- Ma pola PSPACE ne bi pola EXPSPACE re wekhev e?
- Ma pola tevliheviya P binkomek pola PSPACE ye?
- Ma em dikarin îsbat bikin ku çîna Np û P yek in bi dîtina çareseriyek polînomî ya bikêr ji bo her pirsgirêkek bêkêmasî ya NP li ser TM-ya diyarker?
- Ma pola NP dikare bi çîna EXPTIME re wekhev be?
- Di PSPACE de pirsgirêk hene ku ji bo wan algorîtmaya NP-ya naskirî tune?
- Ma pirsgirêkek SAT dikare bibe pirsgirêkek tevahî NP?
- Ma dibe ku pirsgirêk di pola tevliheviya NP de be heke makîneyek ziravî ya ne diyarker hebe ku dê di dema pirnomî de wê çareser bike
- NP çîna zimanên ku xwedan verastkerên dema pirnomî ne
- Ma P û NP bi rastî heman çîna tevliheviyê ne?
- Ma nakokî di navbera pênasekirina NP-ê de wekî çînek pirsgirêkên biryarê yên bi verastkerên polînomî-dem-ê re û rastiya ku pirsgirêkên di pola P-yê de verastkerên dema pirnomî jî hene?
Pir pirs û bersivan di Complexity de bibînin