Di PSPACE de pirsgirêk hene ku ji bo wan algorîtmaya NP-ya naskirî tune?
Di warê teoriya tevliheviya hesabkerî de, nemaze dema ku dersên tevliheviya cîhê lêkolîn dikin, têkiliya di navbera PSPACE û NP de balkêş e. Ji bo ku rasterast pirsê çareser bikin: erê, di PSPACE de pirsgirêk hene ku ji bo wan algorîtmaya NP-ya naskirî tune. Ev îddîa di pênasîn û têkiliyên di navbera van çînên tevliheviyê de ye.
PSPACE çîna pirsgirêkên biryarê ye ku ji hêla makîneya Turing ve bi karanîna cîhê pirnomîal ve têne çareser kirin. Bi gotinek din, heke algorîtmayek hebe ku bikaribe wê bi karanîna mîqdarek bîranînê ya ku di mezinahiya têketinê de pirnomî ye çareser bike, pirsgirêk di PSPACE de ye. Ev çîn cûrbecûr pirsgirêkan vedihewîne, ku hin ji wan pir tevlihev in û pêvajoyên hesabker ên tevlihev vedigirin.
NP, ji hêla din ve, çîna pirsgirêkên biryarê ye ku ji bo çareseriya pêşniyarkirî dikare di dema polînomî de ji hêla makîneya Turing a diyarker ve were verast kirin. Ev tê vê wateyê ku heke kesek ji we re çareseriyek berendamek ji pirsgirêkek di NP-ê de peyda bike, hûn dikarin rastbûna wê çareseriyê zû kontrol bikin, nemaze di dema polînomî de li gorî mezinahiya têketinê.
Têkiliya di navbera van her du çînan de wusa ye ku NP binkeyek PSPACE ye. Ji ber ku her pirsgirêkek ku di dema pirnomî de were verast kirin dikare di cîhê pirnomî de jî were çareser kirin. Ji bo ku fêm bikin ka çima, bihesibînin ku verastkerek-dem-dema pirnomî dikare tenê hejmarek pirnomî ya bit-ên têketinê û çareseriya pêşniyarkirî bixwîne. Ji ber vê yekê, ew dikare ji hêla makîneyek cîhê-polnomîal ve were simul kirin ku cîhên ku xwendiye û karên ku kiriye dişopîne.
Lêbelê, danûstandin ne rast e; ango nayê zanîn ka PSPACE ji NP-ê ye. Bi rastî, bi gelemperî tê bawer kirin ku PSPACE pirsgirêkên ku di NP de ne hene, her çend ev bi fermî nehatiye îsbat kirin. Ev bawerî li ser hebûna pirsgirêkên di PSPACE de ye ku xuya dike ku ji bo çareserkirina wan ji dema pirnomî zêdetir hewce dike, her çend ew dikarin bi cîhê pirnomîal werin çareser kirin.
Yek ji mînakên kanonîkî yên pirsgirêkek di PSPACE de ku nayê zanîn di NP de ye, pirsgirêka Formula Boolean a Quantified (QBF) ye. QBF gelemperîkirina pirsgirêka têrbûna Boolean (SAT) e, ku NP-temam e. Dema ku SAT dipirse gelo veqetandinek nirxên rastiyê ji guhêrbaran re heye ku formula Boolean a diyarkirî rast dike, QBF li ser guhêrbaran pîvanên hêlkirî vedihewîne, wekî "ji bo hemî x, aytek wusa heye ku formula rast be." Hebûna van jimarvanan QBF bi girîngî tevlihevtir dike. QBF PSPACE-temam e, tê vê wateyê ku ew bi qasî her pirsgirêkek di PSPACE de dijwar e. Ger ji bo QBF algorîtmayek NP-ê hebûya, ew ê tê vê wateyê ku NP bi PSPACE re ye, encamek ku dê serpêhatî be û bi gelemperî ne gengaz tê hesibandin.
Nimûneyek din a diyarker pirsgirêka diyarkirina serketî ye di lîstikên gelemperî de, wek guhertoyên giştîkirî yên satrancê an Go, ku li ser tabloyek N x N têne lîstin. Van pirsgirêkan hejmareke potansiyel a tevger û vesazkirinê vedihewîne, lê ew dikarin bi karanîna cîhê polînomîal bi vekolîna hemî dewletên lîstikê yên gengaz bi rêkûpêk biryar bidin. Van pirsgirêkan di heman demê de PSPACE-temam in, ku bêtir hebûna pirsgirêkên li PSPACE yên ku di NP de ne destnîşan dikin.
Ji bo ku hûn kûrtir bigerin ka çima hin pirsgirêkên di PSPACE de têne bawer kirin ku li derveyî NP-ê ne, cewhera hesabên cîhê-sînorkirî li hember dem-sînordar bifikirin. Cihê pirnomî destûrê dide jimareyek potansiyel a berbiçav a gavên hesabkirinê, heya ku cîhê ku tê bikar anîn bi pirnomî ve girêdayî bimîne. Ev berevajî NP-ê ye, ku dem bi pirnomî ve girêdayî ye. Demjimêra berbiçav a ku ji hêla cîhê polînomî ve hatî destûr kirin dikare were bikar anîn da ku pirsgirêkên ku lêgerînên bêkêmasî li ser cîhên berbiçav ên mezin vedihewîne, mîna yên ku di QBF û lîstikên gelemperî de têne dîtin, were bikar anîn.
Wekî din, avahiyên teorîkî yên tevlihev hene ku cûdahiya di navbera PSPACE û NP de bêtir piştgirî dikin. Mînakî, têgeha alternatîf, ku ji hêla Chandra, Kozen, û Stockmeyer ve hatî destnîşan kirin, nedetermînîzmê gelemperî dike û berbi çîna AP (dema pirnomîal a alternatîf) vedike. Hat destnîşan kirin ku AP bi PSPACE re wekhev e, bi vî rengî perspektîfek cihêreng li ser hêza hesabên cîhê pirnomî peyda dike. Alternasyon rêzek pîvanên hebûnî û gerdûnî vedihewîne, ku strukturên QBF neynikê dike, û tevliheviya ku di pirsgirêkên PSPACE de ne diyar dike.
Di heman demê de hêjayî gotinê ye ku veqetandina dersên tevliheviyê di zanistiya kompîturê ya teorîkî de pirsek vekirî ya bingehîn e. Pirsgirêka navdar P vs NP dozek taybetî ya vê lêpirsîna berfireh e. Bi heman rengî, pirsa gelo NP wekhevî PSPACE ye, bêçareser dimîne. Lêbelê, lihevhatina li qadê, li ser bingeha lêkolînek berfireh û cewherê pirsgirêkên naskirî, ev e ku PSPACE îhtîmal e ku pirsgirêkên ku di NP de ne hene.
Hebûna pirsgirêkên li PSPACE yên ku algorîtmaya NP-ya naskirî ji bo wan tune ye, ji hêla pênase û têkiliyên di navbera van çînên tevliheviyê de, û her weha ji hêla mînakên berbiçav ên mîna QBF û pirsgirêkên lîstika gelemperî ve têne piştgirî kirin. Van mînakan pêvajoyên hesabkerî yên tevlihev û potansiyel ên ku di hundurê cîhê polînomî de têne rêvebirin ronî dikin, lê ne gengaz e ku di dema pirnomî de bêne sînordar kirin, bi vî rengî wan li derveyî qada NP-ê bi cih dike.
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?
- 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