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.
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?
Pirsa ka çînên P û NP wekhev in yek ji wan pirsgirêkên vekirî yên herî girîng û dirêj-mayînde ye di warê teoriya tevliheviya hesabkirinê de. Ji bo çareserkirina vê pirsê, pêdivî ye ku meriv pênasîn û taybetmendiyên van çînan, û hem jî encamên dîtina çareseriyek bikêr-polnomial-demê fam bike.
Ma pola NP dikare bi çîna EXPTIME re wekhev be?
Pirsa ka gelo çîna NP dikare bi pola EXPTIME re wekhev be, di aliyên bingehîn ên teoriya tevliheviya hesabkerî de vedigere. Ji bo çareserkirina vê pirsê bi berfirehî, pêdivî ye ku meriv pênasîn û taybetmendiyên van çînên tevliheviyê, têkiliyên di navbera wan de û encamên wekheviyek wusa fam bike. Pênase û Taybetmendî
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.
Ma pirsgirêkek SAT dikare bibe pirsgirêkek tevahî NP?
Pirsa ka gelo pirsgirêkek SAT (têrbûna Boolean) dikare bibe pirsgirêkek NP-temam, di teoriya tevliheviya hesabkirinê de pirsek bingehîn e. Ji bo çareserkirina vê yekê, pêdivî ye ku meriv pênasîn û taybetmendiyên NP-temambûnê bihesibîne û çarçoweya dîrokî û teorîkî ya ku dabeşkirina SAT-ê wekî pirsgirêkek NP-tevahî vedihewîne lêkolîn bike. Pênase û
- Weşandin Pîroz, EITC/IS/CCTF Bingehên Teoriya Tevliheviya Hesabkirinê, Tevlîheviyê, Ofspatkirina ku SAT NP temam e
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
Pirsa "Gelo pirsgirêkek di pola tevliheviya NP de hebe heke makîneyek Turing a ne diyarker hebe ku dê di dema pirnomî de wê çareser bike?" di teoriya tevliheviya hesabî de têgehên bingehîn disekine. Ji bo ku em vê pirsê bi berfirehî çareser bikin, divê em pênasîn û taybetmendiyên çîna tevliheviya NP û rola Turingê ne-determînîst bihesibînin.
NP çîna zimanên ku xwedan verastkerên dema pirnomî ne
Çîna NP, ku tê wateya "dema pirnomî ya nedetermînîst", têgehek bingehîn e di teoriya tevliheviya hesabkerî de, bineqadek zanistiya komputerê ya teorîkî. Ji bo fêmkirina NP, divê meriv pêşî têgîna pirsgirêkên biryarê, ku pirsên bi bersivek erê-an-na ne, fêm bike. Zimanek di vê çarçoveyê de li ser hinekan rêzek têlan vedibêje
- Weşandin Pîroz, EITC/IS/CCTF Bingehên Teoriya Tevliheviya Hesabkirinê, Tevlîheviyê, Danasîna pejirandina NP û pirjimar
Ma P û NP bi rastî heman çîna tevliheviyê ne?
Pirsa ku P bi NP re ye yek ji pirsgirêkên herî kûr û neçareserkirî ye di zanistiya kompîturê û matematîkê de. Ev pirsgirêk di dilê teoriya tevliheviya hesabkirinê de ye, qadek ku dijwariya xwerû ya pirsgirêkên hesabkeriyê lêkolîn dike û wan li gorî çavkaniyên ku ji bo çareserkirina wan hewce ne dabeş dike. Ji bo fêmkirina
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, cureyek fermî ye