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?
Çîna NP, ku ji bo dema Polynomiya Ne-determînîst radiweste, ji bo teoriya tevliheviya hesabkerî navendî ye û pirsgirêkên biryarê yên ku xwedan verastkerên dema pirnomî ne vedihewîne. Pirsgirêkek biryarê ew e ku bersivek erê-an-na hewce dike, û verastker di vê çarçoveyê de algorîtmayek e ku rastdariya çareseriyek diyarkirî kontrol dike.
Girîng e ku meriv di navbera çareserkirina pirsgirêkek (hesibandin) û verastkirina çareseriyê (verastkirin) de cûda bike. Di NP de, balê dikişîne ser ka gelo verastkerek-dema polînomî heye ku dikare rastbûna çareseriyek piştrast bike.
Çîna P, dema Polynomial temsîl dike, pirsgirêkên biryarê yên ku ji hêla makîneya Turing a diyarker ve di dema pirnomî de têne çareser kirin vedihewîne. Ji ber vê yekê, ji bo her pirsgirêkek di P-ê de, ne tenê algorîtmayek-dem-polînomî heye ku çareseriyek bibîne, lê di heman demê de algorîtmayek-dem-polînomî jî heye ku çareseriyê verast bike.
Nakokî xuya dike di çavdêriya ku her pirsgirêkek di P-yê de, bi xwezayî xwedan algorîtmayek çareserkirinê ya pirnomîal-demê ye, di heman demê de xwedan verastkerek dema pirnomî ye. Lêbelê, ev ne dijberî pênase NP ye. Taybetmendiya diyarker a NP hebûna verastkerek-dema polînomî ye, bêyî ku ew çiqas dirêj dibe ku çareseriyê bibîne. Ev tê vê wateyê ku hemî pirsgirêkên di P-ê de jî di NP de ne, ji ber ku çareseriyên wan dikarin di dema polînomî de werin verast kirin.
Mînakî, pirsgirêka ceribandina jimareya yekem bifikire. Ev pirsgirêk dikare bi du awayan were çarçove kirin: çêkirina jimareyên yekem û verastkirina ka hejmareke diyarkirî ya yekem e. Sieve of Eratosthenes algorîtmayek e ji bo hilberîna hemî jimareyên yekem heya sînorek diyarkirî û bi karîgerî vê yekê dike, lê tevliheviya wê ya dema wê ne pirnomî ye di wateya hişk de ku di teoriya tevliheviya hesabkirinê de tê bikar anîn; ew bi gelemperî wekî O(n log n) tê binavkirin, ku ji rêzê çêtir e lê li gorî pênaseya P-yê ne bi hişkî pirnomî ye. Ji hêla din ve, pirsgirêka verastkirina ka hejmareke diyar yekem e (ceribandina jimareya pêşîn) e. karekî cuda. Algorîtmayên bikêrhatî yên wekî ceribandina seretayî ya AKS destûrê dide verastkirina seretayî di dema polînomî de. Ji ber vê yekê, pirsgirêka ceribandina jimareya bingehîn, di çarçoweya verastkirinê de, dikeve pola P, û hem jî NP, ji ber ku çareseriyek (gelo hejmarek yekem e) dikare di dema pirnomî de were verast kirin. Ev nîşan dide ku dema ku hilberîna jimareya yekem û ceribandina jimareya yekem bi hev ve girêdayî ne, ew di warê tevliheviya hesabkirinê de ramanên cihêreng vedigirin.
Di encamê de, pênasekirina NP wekî xwedan verastkerên pirnomî-demê bi xwezaya P re li hev dike. Cûdahî ne di qonaxa verastkirinê de lê di pêvajoya peydakirina çareyan de ye: Pirsgirêkên P di dema pirnomî de çareser û verastbar in, dema ku pirsgirêkên NP têne çareser kirin. di dema pirnomî de têne verast kirin, lê her gav nayê zanîn ka ew dikarin di dema pirnomî de werin çareser kirin.
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