Pêvajoya avakirina verastkerek dema pirnomî ya ji makîneya Turing a ne-determînîst a dema pirnomîal vebêjin.
Verastkerek dema pirnomî dikare ji makîneya Turing a ne-determînîst a dema pirnomîal (NTM) bi şopandina pêvajoyek sîstematîk were çêkirin. Ji bo têgihiştina vê pêvajoyê, pêdivî ye ku meriv têgihîştinek zelal a têgehên teoriya tevliheviyê, nemaze çînên P û NP, û têgîna verastkirina polînomî hebe.
Di teoriya tevliheviya hesabkerî de, P behsa çîna pirsgirêkên biryarê dike ku bi makîneya Turing a diyarker di dema pirnomîal de têne çareser kirin. Ji hêla din ve, NP behsa çîna pirsgirêkên biryarê dike ku çareseriyek ji hêla makîneya Turing a diyarker ve di dema pirnomî de dikare were verast kirin. Cûdahiya sereke di navbera van her du çînan de ev e ku P pirsgirêkên ku bi bandor têne çareser kirin, dema ku NP pirsgirêkên ku bi bandor têne verast kirin temsîl dike.
Verastkera dema pirnomîal makîneyek Turing a diyarker e ku dikare rastbûna çareseriya pirsgirêkek NP di dema pirnomî de verast bike. Pêvajoya avakirina verastkerek wusa ji NTM-ya demek pirnomî gavên jêrîn pêk tîne:
1. Ji ber pirsgirêkek NP, em bibêjin pirsgirêka X, em hebûna demek pirnomial NTM M ferz dikin ku dikare X-yê çareser bike.
2. Em ji bo pirsgirêka X verastkerek demê ya pirnomîal V ava dikin bi simulkirina tevgera NTM M. Verastker V du têketinan digire: çareseriya pirsgirêka X û sertîfîka. Sertîfîka delîlek e ku çareserî rast e.
3. Verastker V pêşî kontrol dike ka sertîfîka xwedan formatek derbasdar e. Ev gav dikare di dema polînomî de were kirin ji ber ku verastker strukturên bendewar ên sertîfîkayê dizane.
4. Dûv re, verastker V tevgera NTM M li ser çareserî û sertîfîkaya hatî dayîn simule dike. Ew hemî şaxên mimkun ên hesabkirina M-yê dimeşîne, kontrol dike ka çi şax têketinê qebûl dike. Ev simulasyon dikare di dema pirnomî de were kirin ji ber ku NTM M di dema pirnomî de dixebite.
5. Ger verastker V bi kêmanî şaxek pejirandinê ya hesabkirinê bibîne, ew têketinê qebûl dike. Ev tê wê wateyê ku çareserî ji bo pirsgirêka X rast tê piştrast kirin. Wekî din, heke yek ji şaxan qebûl neke, verastker têketinê red dike.
Fikra bingehîn a li pişt avakirina verastkerek dema pirnomîal ev e ku NTM M dikare di dema polînomî de sertîfîkaya rast texmîn bike. Bi simulkirina tevgera M û kontrolkirina hemî şaxên gengaz, verastker V dikare rastdariya çareseriyê bi bandor verast bike.
Werin em mînakek ji bo ronîkirina vê pêvajoyê. Pirsgirêka diyarkirina ka grafiyek diyarkirî xwedan çerxa Hamiltonî ye, ku pirsgirêkek NP-temam e, binihêrin. Em hebûna demek pirnomîal NTM M texmîn dikin ku dikare vê pirsgirêkê çareser bike.
Ji bo ku ji bo vê pirsgirêkê verastkerek dema pirnomîal V ava bikin, em tevgera M-ya li ser graf û sertîfîkaya hatî destnîşan kirin simule dikin. Verastker kontrol dike ka sertîfîka çerxeke Hamiltonî ya derbasdar temsîl dike bi verastkirina ku ew tam carekê serdana her verteksê dike û çerxekê çêdike.
Bi simulkirina hemî şaxên mimkun ên hesabkirina M-yê, verastker dikare bi bandor diyar bike ka grafika hatî dayîn xwedan çerxa Hamiltonî ye. Ger bi kêmanî yek şaxek M têketinê qebûl bike, verastker têketinê wekî çerxa Hamiltonî ya derbasdar qebûl dike. Wekî din, ew têketinê red dike.
Çêkirina verastkerek dema pirnomî ya ji demek pirnomîkal NTM bi simulkirina tevgera NTM û kontrolkirina hemî şaxên mimkun ên hesabkirinê vedihewîne. Ev pêvajo rê dide verastkirina bikêrhatî ya çareseriyên pirsgirêkên NP. Bi avakirina verastkerên weha, em dikarin pirsgirêkan li gorî verastkirina wan di dema pirnomial de dabeş bikin.
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