Ma pola PSPACE ne bi pola EXPSPACE re wekhev e?
Pirsa ku çîna PSPACE bi çîna EXPSPACE re ne wekhev e, di teoriya tevliheviya hesabkirinê de pirsgirêkek bingehîn û çaresernekirî ye. Ji bo ku têgihiştinek berfireh peyda bike, pêdivî ye ku meriv pênasîn, taybetmendî û encamên van çînên tevliheviyê, û her weha çarçoveyek berfireh a tevliheviya cîhê bihesibîne.
Pênase û Taybetmendiyên Bingehîn
PSPACE: Çîna PSPACE ji hemû pirsgirêkên biryarê yên ku ji hêla makîneya Turing ve bi karanîna mîqdarek pirnomî ya cîhê ve têne çareser kirin pêk tê. Bi awayekî fermî, zimanek L di PSPACE de ye heke makîneya Turing M û fonksiyonek pirnomîal p(n) hebe ku ji bo her têketina x, makîneya M biryarê dide ka x di L de herî zêde cîhê p(|x|) bikar tîne an na. PSPACE gelek pirsgirêkan dihewîne, di nav wan de yên ku di dema pirnomîal de (P) de têne çareser kirin û yên ku ji bo PSPACE temam in, wek pirsgirêka Formula Boolean a Quantified (QBF).
EXPSPACE: Çîna EXPSPACE hemî pirsgirêkên biryarê yên ku ji hêla makîneya Turing ve bi karanîna mîqdarek berbiçav a cîhê ve têne çareser kirin vedihewîne. Bi taybetî, zimanek L di EXPSPACE de ye heke makîneya Turing M û fonksiyonek nîşankirî f(n) hebe ku ji bo her têketina x, makîneya M biryarê dide ka x di L de herî zêde 2^f(|x|) bikar tîne an na. dem. EXPSPACE ji PSPACE çînek mezintir e, ji ber ku ew rê dide ku cîhê bi qawet zêdetir were peyda kirin, ku çareseriya pirfirehtir pirsgirêkan pêk tîne.
Têkiliya Di navbera PSPACE û EXPSPACE de
Ji bo têgihîştina têkiliya di navbera PSPACE û EXPSPACE de, girîng e ku meriv hiyerarşiya çînên tevliheviya cîhê nas bike. Ji hêla pênasê ve, PSPACE di nav EXPSPACE de ye ji ber ku her pirsgirêkek ku bi karanîna cîhê pirnomîal were çareser kirin dikare bi karanîna cîhê berbiçav jî were çareser kirin. Bi fermî, PSPACE ⊆ EXPSPACE. Lêbelê, danûstandin ne hewce ne rast e; Bi gelemperî tê bawer kirin ku EXPSPACE pirsgirêkên ku bi karanîna cîhê pirnomîal nayên çareser kirin dihewîne, tê vê wateyê ku PSPACE ≠ EXPSPACE.
Nimûne û Encam
Pirsgirêka QBF, ku PSPACE-temam e, bifikirin. Ev pirsgirêk bi destnîşankirina rastiya formulek Boolean a hejmarkirî ve girêdayî ye, û ew dikare bi karanîna cîhê pirnomîal were çareser kirin. Ji ber ku QBF PSPACE-temam e, her pirsgirêkek di PSPACE de dikare di dema polînomî de bibe QBF. Ji hêla din ve, mînakek pirsgirêkek di EXPSPACE de lê ne pêdivî ye ku di PSPACE de pirsgirêka gihîştinê ye ji bo makîneyên Turing ên alternatîf ên bi sînorên cîhê berbiçav. Vê pirsgirêkê hewce dike ku bi rengek berbiçav gelek veavakirinan bişopînin, ku bi cîhê pirnomîal re ne pêkan e.
Teorema Hiyerarşiya Fezayê
Teorema Hiyerarşiya Fezayê ji bo vê baweriyê bingehek fermî peyda dike ku PSPACE bi hişkî di nav EXPSPACE de ye. Ev teorem diyar dike ku ji bo her fonksiyonek cihê-çêker f(n), zimanek heye ku di cîha f(n) de dikare were biryardan lê ne di cîhê o(f(n) de). Bi sepandina vê teoremê bi f(n) = 2^n, em werdigirin ku di cîhê rêjeyê de pirsgirêkên ku dikarin bên çareser kirin hene ku di ti cîhek binîqatan de nayên çareser kirin, di nav de cîhê pirnomî jî. Ji ber vê yekê, Teorema Hiyerarşiya Fezayê tê vê wateyê ku PSPACE bi hişkî di nav EXPSPACE de ye, ango PSPACE ⊂ EXPSPACE.
Xwezaya Neçareserkirî ya PSPACE ≠ EXPSPACE
Tevî delîlên bihêz ên ku ji hêla Teorema Hiyerarşiya Fezayê ve têne peyda kirin, pirsa gelo PSPACE ne bi EXPSPACE re wekhev e, neçar dimîne. Ev ji ber ku îsbatkirina newekheviya hişk PSPACE ≠ EXPSPACE hewce dike ku hebûna pirsgirêkek taybetî di EXPSPACE de were destnîşan kirin ku di PSPACE de nayê çareser kirin, ya ku heya îro nehatiye bicîh kirin. Zehmetî di kêşeyên xwerû yên îsbatkirina veqetandina di navbera çînên tevliheviyê de, mijarek hevpar di teoriya tevliheviya hesabker de ye.
Dersên Berfirehtir û Tevliheviya Têkildar
Têkiliya di navbera PSPACE û EXPSPACE de dikare di hundurê perestgeha berfireh a çînên tevliheviyê de were girêdan. Mînakî, çîna P (pirsgirêkên ku di dema pirnomîal de têne çareser kirin) binkeyek PSPACE ye, û bi gelemperî tê bawer kirin ku P ≠ PSPACE. Bi heman rengî, çîna NP (dema pirnomî ya ne-determinîstîk) jî di nav PSPACE de heye, û pirsgirêka navdar P û NP di qadê de pirsek vekirî ya navendî ye. Têkiliyên ragirtinê yên di nav van çînan de wiha têne kurt kirin:
– P ⊆ NP ⊆ PSPACE ⊆ EXPSPACE
Ji bilî van çînan, çînên din ên tevliheviya fezayê yên girîng hene, wek L (qada logarîtmîkî) û NL (qada logarîtmîkî ya nedeterminîstîk), ku binkeyên PSPACE ne. Têkiliyên di navbera van çînan de bêtir hîyerarşiya tevliheviya hesabkirinê ya li ser bingeha hewcedariyên cîhê diyar dike.
Pirsa ku PSPACE bi EXPSPACE re ne wekhev e di teoriya tevliheviya hesabkirinê de pirsgirêkek bingehîn û çaresernekirî ye. Digel ku Teorema Hiyerarşiya Fezayê delîlên xurt peyda dike ku PSPACE bi hişkî di hundurê EXPSPACE de ye, delîlek fermî ya newekheviya hişk PSPACE ≠ EXPSPACE neçar dimîne. Lêgerîna vê pirsê ronahiyê dide ser perestgeha berfireh a çînên tevliheviyê û kêşeyên xwerû yên îsbatkirina veqetiyan di navbera wan de.
Pirs û bersivên din ên vê dawiyê di derbarê Tevlîheviyê:
- 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 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