Di warê teoriya tevliheviya hesabkerî de, têkiliya di navbera çînên tevliheviyê P û PSPACE de mijarek bingehîn a lêkolînê ye. Ji bo çareserkirina pirsê di derbarê ka pola tevliheviya P-ê ji çîna PSPACE-ê ye an her du çîn yek in, pêdivî ye ku meriv pênas û taybetmendiyên van çînan bihesibîne û girêdanên wan analîz bike.
Çîna tevlîheviyê P (Dema Polynomial) ji pirsgirêkên biryargirtinê pêk tê ku dikarin bi makîneya Turing a diyarker di dema pirnomî de werin çareser kirin. Bi awayekî fermî, zimanek L aîdî P ye ger makîneya Turing a diyarker M û pirnomîlek p(n) hebe ku ji bo her xêza x, M biryarê dide ka x ji L-yê herî zêde di p(|x|) gavan de ye, li ku | x| dirêjahiya rêza x nîşan dide. Bi gotinên hêsan, pirsgirêkên di P-ê de dikarin bi bandor werin çareser kirin, digel ku wextê pêdivî ye ku herî zêde bi pirnomî bi mezinahiya têketinê re mezin dibe.
Ji hêla din ve, PSPACE (Cihê Polynomial) pirsgirêkên biryarê yên ku dikarin ji hêla makîneya Turing ve bi karanîna cîhek pirnomîal ve werin çareser kirin vedihewîne. Zimanek L di PSPACE de ye heke makîneya Turing M û pirnomîlek p(n) hebe ku ji bo her xêza x, M biryarê dide ka x ya L-yê herî zêde p(|x|) bi kar tîne. Nemaze, dema ku ji bo hesabkirinê hewce ye bi pirnomîlek ve nayê sînor kirin; tenê cîh e.
Ji bo têgihîştina têkiliya P û PSPACE, xalên jêrîn bifikirin:
1. Tevlîbûna P di PSPACE de: Her pirsgirêkek ku di dema pirnomî de were çareser kirin di cîhê pirnomî de jî dikare were çareser kirin. Ji ber ku makîneya Turing a diyarker a ku pirsgirêkek di dema pirnomî de çareser dike dê herî zêde cîhê pirnomîal bikar bîne, ji ber ku ew nikare ji hejmara gavên ku digire bêtir cîh bikar bîne. Ji ber vê yekê, P binkeyek PSPACE ye. Bi fermî, P ⊆ PSPACE.
2. Wekheviya Potansiyela P û PSPACE: Pirsa ku P bi PSPACE re wekhev e (P = PSPACE) yek ji pirsgirêkên vekirî yên sereke di teoriya tevliheviya hesabkirinê de ye. Ger P bi PSPACE re wekhev be, ev tê wê wateyê ku hemî pirsgirêkên ku bi cîhê pirnomîal re têne çareser kirin dikarin di dema pirnomî de jî werin çareser kirin. Lêbelê, niha tu delîl tune ku vê wekheviyê piştrast bike an red bike. Piraniya teorîsyenên tevliheviyê bawer dikin ku P bi hişkî di nav PSPACE (P ⊊ PSPACE) de heye, yanî di PSPACE de pirsgirêk hene ku di P de ne.
3. Nimûne û Encam: Pirsgirêka diyarkirina ka formula Boolean a bihejmarkirî (QBF) rast e an na. Ev pirsgirêk, ku wekî TQBF (Formula Boolean ya Rastîn a Quantified) tê zanîn, pirsgirêkek PSPACE-tevahî ya canonîkî ye. Pirsgirêkek PSPACE-temam e heke ew di PSPACE de be û her pirsgirêkek di PSPACE de dikare bi karanîna kêmkirina-dema polînomî jê were kêm kirin. Tê bawer kirin ku TQBF ne di P-yê de ye, ji ber ku ew hewce dike ku hemî peywirên rastîn ên gengaz ên guhêrbaran binirxîne, ku bi gelemperî di dema pirnomî de nayên kirin. Lêbelê, ew dikare bi karanîna cîhê polînomî ve bi nirxandina bineformulan vegerî çareser bibe.
4. Hiyerarşiya Dersên Tevliheviyê: Têkiliya di navbera P û PSPACE de bi nihêrandina çarçoveyek berfireh a dersên tevliheviyê çêtir dikare were fêm kirin. Çîna NP (Dema Polynomial Nedeterministic) ji pirsgirêkên biryarê yên ku çareseriyek di dema pirnomial de dikare were verast kirin pêk tê. Tê zanîn ku P ⊆ NP ⊆ PSPACE. Lêbelê, têkiliyên rastîn ên di navbera van çînan de (mînak, gelo P = NP an NP = PSPACE) neçar dimînin.
5. Teorema Savitch: Di teoriya tevliheviyê de encamek girîng Teorema Savitch e, ku dibêje her pirsgirêkek ku di cîhê pirnomîala nedetermînîstîk de (NPSPACE) de were çareser kirin, dikare di cîhê pirnomiyala diyarker de jî were çareser kirin. Bi fermî, NPSPACE = PSPACE. Ev teorem xurtbûna çîna PSPACE destnîşan dike û destnîşan dike ku nedetermînîzm di warê tevliheviya cîhê de hêza hesabker a zêde peyda nake.
6. Plmkanên Praktîkî: Têgihîştina têkiliya di navbera P û PSPACE de ji bo hesabkirina pratîkî bandorên girîng hene. Pirsgirêkên di P-ê de bi bandor têne çareser kirin têne hesibandin û ji bo serîlêdanên rast-ê-ê-ê-ê-ê-ê-ê-ê-ê ne. Berevajî vê, pirsgirêkên di PSPACE de, her çend bi cîhê pirnomîal re bêne çareser kirin, dibe ku hewceyê wextê berbiçav hebe, ku wan ji bo têketinên mezin nepraktîkî dike. Naskirina ka pirsgirêkek di P an PSPACE de heye di destnîşankirina fersendiya dîtina algorîtmayên bikêrhatî ji bo serîlêdanên cîhana rastîn de dibe alîkar.
7. Rêbernameyên Lêkolînê: Lêkolîna pirsa P û PSPACE wekî qada lêkolînê ya çalak berdewam dike. Pêşketinên di vî warî de dikarin di têgihîştina sînorên bingehîn ên hesabkirinê de bibin sedema destkeftiyan. Lekolînwan teknîkên cihêreng, wek tevliheviya çerxê, delîlên înteraktîf, û rêbazên cebrî vedikolin, da ku di têkiliyên di navbera çînên tevliheviyê de têgihiştinê bistînin.
Çîna tevlîheviyê P bi rastî jî binkeyek ji PSPACE ye, ji ber ku her pirsgirêkek ku di dema pirnomî de were çareser kirin dikare di cîhê pirnomî de jî were çareser kirin. Lêbelê, gelo P bi PSPACE re wekhev e di teoriya tevliheviya hesabkirinê de pirsek vekirî dimîne. Baweriya serdest ev e ku P bi hişkî di nav PSPACE de cih digire, û destnîşan dike ku di PSPACE de pirsgirêk hene ku ne di P de ne. tevliheviya hesabkirinê.
Pirs û bersivên din ên vê dawiyê di derbarê Tevlîheviyê:
- Ma pola PSPACE ne bi pola EXPSPACE re wekhev e?
- 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 her çarçoveyek zimanek azad e di pola tevliheviya P de?
- 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