Ma zimanên hesas ên kontekstê ji hêla Makîneya Turing ve têne nas kirin?
Zimanên hesas-contekst (CSL) çînek zimanên fermî ne ku ji hêla rêzimanên hesas-contekst ve têne diyar kirin. Van rêzimanan giştîkirina rêzimanên bê kontekst in, rê dide qaîdeyên hilberînê ku dikarin rêzek bi rêzek din biguhezînin, bi şertê ku veguheztin di çarçoveyek taybetî de pêk were. Ev çîna zimanan di teoriya hesabkirinê de ji ber ku pir girîng e
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 û Bingehîn
- Weşandin Pîroz, EITC/IS/CCTF Bingehên Teoriya Tevliheviya Hesabkirinê, Tevlîheviyê, Dersên tevliheviya fezayê
Ma pola tevliheviya P binkomek pola PSPACE ye?
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 derheqê ka pola tevliheviya P-ya binekomek pola PSPACE ye an her du çîn yek in, pêdivî ye ku meriv pênas û taybetmendiyan binirxîne.
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.