Tevliheviya demê ya modelên hesabkirinê yên diyarker ji modelên ne-determînîst çawa cûda dibe?
Modelên diyarker û ne-determînîst ên hesabkirinê du nêzîkatiyên cihêreng in ku ji bo analîzkirina tevliheviya demê ya pirsgirêkên hesabkirinê têne bikar anîn. Di warê teoriya tevliheviya hesabkirinê de, têgihîştina cûdahiyên di navbera van modelan de ji bo nirxandina karîgerî û pêkaniya çareserkirina pirsgirêkên cûda yên hesabkirinê girîng e. Armanca vê bersivê ew e ku di warê tevliheviya demê de ravekirinek berfireh a cûdahiyên di navbera modelên diyarker û nedetermînîst de peyda bike.
Modelên diyarker ên hesabkirinê li ser bingeha vê ramanê ne ku hesabek bi rengek baş diyarkirî û pêşbînîkirî pêşve diçe. Di van modelan de, pêkanîna bernameyekê ji bo têketinek diyar rêyek yekane dişopîne, bêyî ku nezelaliyek an nezelaliyê ye. Modelên diyarker bi gelemperî di ziman û algorîtmayên bernamesaziyê yên kevneşopî de têne bikar anîn, ku tevgera bernameyê bi tevahî ji hêla têketin û rêza rêwerzan ve tê destnîşankirin. Tevliheviya demê ya modelên diyarker bi gelemperî bi jimartina hejmara operasyonên bingehîn, wek operasyonên jimareyî û berhevdan, ku di dema hesabkirinê de têne darve kirin, tê pîvandin.
Ji hêla din ve, modelên ne-determînîst ên hesabkirinê di dema pêkanîna bernameyekê de rê dide gelek rê an vebijarkan. Ev tê vê wateyê ku, bername dikare bi hevdemî îmkanên cihêreng keşif bike, têketinek were dayîn. Modelên ne-determînîst bi gelemperî di zanistiya kompîturê ya teorîkî de têne bikar anîn da ku dijwariya navxweyî ya pirsgirêkên hesabkirinê analîz bikin. Di van modelan de, tevliheviya demê bi hejmara herî zêde ya gavên ku ji bo gihîştina çareseriyekê hewce ne, tête pîvandin, hemî bijarteyên mimkun ên ku ji hêla bernameyê ve hatine çêkirin têne hesibandin.
Cûdahiya sereke di navbera modelên diyarker û ne-determînîst de di xwezaya analîza tevliheviya dema wan de ye. Modelên diyarker balê dikişînin ser senaryoya herî xirab, li ser dema ku hewce dike ji bo çareserkirina pirsgirêkek ji bo her mezinahiya têketinê sînorek jorîn peyda dike. Ev rê dide nirxandinek pratîktir a karbidestiya algorîtmayan, ji ber ku ew garantî dike ku algorîtma dê ji senaryoya herî xirab bêtir dem negire. Mînakî, heke algorîtmayek xwedan tevliheviya demê ya O(n^2) be, ev tê vê wateyê ku dema darvekirinê bi mezinahiya têketinê re çargoşe mezin dibe, û piştrast dike ku algorîtm dê ji pirjimarek domdar a n^2 gavan zêdetir negire.
Ji hêla din ve, modelên ne-determînîst, senaryoya çêtirîn-doza dihesibînin, ku bername di her gavê de bijartinên çêtirîn çêdike. Analîzkirina tevliheviya demê ya di modelên ne-determînîst de li ser dema ku ji bo çareserkirina pirsgirêkek hewce ye sînorek jêrîn peyda dike, ji ber ku ew hejmara hindiktirîn gavên ku ji bo gihîştina çareseriyê hewce dike temsîl dike. Lêbelê, modelên ne-determînîst di cewherê xwe de bêtir teorîkî ne, ji ber ku ew rasterast bi pêkanînên pratîkî re têkildar nabin. Tevliheviya dema ne-determînîst a pirsgirêkê bi gelemperî bi çîna NP (Dema Polynomî ya Ne-determînîst) tê destnîşan kirin, ku komek pirsgirêkên biryarê yên ku ji hêla makîneya Turing a ne-determînîst ve di dema pirnomî de têne çareser kirin temsîl dike.
Ji bo ronîkirina cûdahiya di navbera tevliheviya dema diyarker û ne-determînîst de, werin em pirsgirêka dîtina hêmanek taybetî di navnîşek nerêkûpêk de binirxînin. Di modelek diyarker de, tevliheviya dema herî xirab a vê pirsgirêkê O(n) ye, ku n mezinahiya navnîşê temsîl dike. Ev tê vê wateyê ku, di senaryoya herî xirab de, dibe ku algorîtm hewce bike ku hemî n hêmanên navnîşê lêkolîn bike berî ku hêmana xwestinê bibîne. Di modelek ne-determînîst de, tevliheviya dema herî baş a vê pirsgirêkê O(1) ye, ji ber ku bername dikare bijartina çêtirîn bike û tavilê hêmana xwestî bibîne. Lêbelê, girîng e ku were zanîn ku ev tevliheviya dema ne-determînîst nayê wê wateyê ku pirsgirêk di demek domdar de di wateya pratîkî de were çareser kirin.
Tevliheviya demê ya modelên diyarker ên hesabkirinê li ser bingeha senaryoya herî xirab e, li ser wextê ku ji bo çareserkirina pirsgirêkek hewce ye sînorek jorîn peyda dike. Ji hêla din ve, modelên ne-determînîst, senaryoya çêtirîn-dozê dihesibînin û li ser tevliheviya demê sînorek jêrîn peyda dikin. Dema ku modelên diyarker pratîktir in û rasterast ji algorîtmayên cîhana rastîn re têne sepandin, modelên ne-determînîst di serî de ji bo analîza teorîkî û dersên tevliheviyê têne bikar anîn. Fêmkirina cûdahiyên di navbera van modelan de ji bo analîzkirin û sêwirana çareseriyên hesabker ên bikêr girîng e.
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?
- 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?
Pir pirs û bersivan di Complexity de bibînin