NP çîna zimanên ku xwedan verastkerên dema pirnomî ne
Çîna NP, ku tê wateya "dema pirnomî ya ne-determînîst", têgehek bingehîn e di teoriya tevliheviya hesabkerî de, bineqadek zanistiya computerê 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 komek rêzikên li ser hin alfabeyê vedibêje, ku her rêzek mînakek pirsgirêkek biryarê kod dike.
Zimanek (L) di NP-yê de tê gotin ku heke ji bo (L) verastker-dema pirnomî hebe. Verastker algorîtmayek diyarker e (V) ku du têketinan digire: mînakek (x) û sertîfîkayek (y). Belgeya (y) wekî "şahid" an "delîl" jî tê zanîn. Verastker (V) kontrol dike ka sertîfîkaya (y) piştrast dike ku (x) aîdî zimanê (L) ye. Bi awayekî fermî, zimanek (L) di NP de ye heke algorîtmayek-dema pirnomî (V) û pirnomîlek (p(n)) hebe ku ji bo her rêzek (x di L) de, rêzek (y) bi (y) hebe. |y|. leq p(|x|)) û (V(x, y) = 1). Berevajî vê, ji bo her rêzek (x notin L), rêzek (y) tune ku (V(x, y) = 1).
Ji bo ronîkirina vê têgehê, pirsgirêka naskirî ya "têrbûna Boolean" (SAT) binirxînin. Pirsgirêka SAT dipirse gelo di formula Boolean a diyarkirî de veqetandinek nirxên rastiyê ji guherbaran re heye, wusa ku formula rast binirxîne. Pirsgirêka SAT di NP-ê de ye ji ber ku, ji ber ku formula Boolean (phi) û veqetandinek (alpha) ya nirxên rastiyê ji guhêrbarên wê re tê dayîn, meriv dikare di dema polînomî de verast bike ka (alpha) (phi) têr dike. Li vir, mînaka (x) formula Boolean (phi) ye, û sertîfîka (y) peywirdar e (alpha). Verastker (V) kontrol dike ka (alpha) (phi) rast dike, ku dikare di dema pirnomî de li gorî mezinahiya (phi) were kirin.
Nimûneyek din a berbiçav pirsgirêka "Rêya Hamiltonî" ye. Ev pirsgirêk dipirse gelo di grafiyek diyarkirî de rêyek heye ku tam carekê serdana her verteksê dike. Pirsgirêka Rêya Hamiltonî jî di NP-ê de ye ji ber ku, grafîkek (G) û rêzek xalîkan (P) tê dayîn, mirov dikare di dema pirnomî de verast bike ka (P) di (G) de rêyek Hamiltonî ye yan na. Di vê rewşê de, mînaka (x) grafîk (G) ye, û sertîfîka (y) rêza xalan e (P). Verastker (V) kontrol dike ka (P) rêyek Hamiltonî çêdike, ku dikare di dema pirnomî de li gorî mezinahiya (G) were kirin.
Têgîna verastkirina polînomî-demê girîng e ji ber ku ew rêyek ji bo karakterîzekirina pirsgirêkên ku bi bandor têne kontrol kirin peyda dike, tewra ku dîtina çareseriyê ji hêla hesabkirinê ve ne pêkan be jî. Ev dibe sedema pirsa navdar a gelo (P = NP), ku dipirse gelo her pirsgirêkek ku çareseriya wê di dema pirnomî de were verast kirin dikare di dema pirnomî de jî were çareser kirin. Çîna (P) ji pirsgirêkên biryarê pêk tê ku dikarin di dema pirnomî de bi makîneya Turing a diyarker ve werin çareser kirin. Ger (P = NP), ev tê wê wateyê ku her pirsgirêkek bi verastkerek-dema pirnomî re jî çareserkerek dema pirnomî heye. Ev pirs di zanistiya komputerê de yek ji pirsgirêkên vekirî yên herî girîng dimîne.
Yek ji taybetmendiyên sereke yên NP-ê ev e ku ew di bin kêmkirina dema polînomî de girtî ye. Kêmkirina pirnomî-demê ji zimanekî (L_1) bo zimanekî (L_2) fonksiyonek dema pirnomî ya hejmarbar e (f) wisa ye ku (x di L_1 de) ger û tenê heke (f(x) di L_2 de). Ger kêmkirina dema pirnomî ji (L_1) heya (L_2) hebe û (L_2) di NP de be, wê demê (L_1) jî di NP de ye. Ev taybetmendî di lêkolîna NP-temambûnê de, ku pirsgirêkên "herî dijwar" di NP-ê de destnîşan dike, amûrek e. Pirsgirêkek NP-temam e heke ew di NP-ê de be û her pirsgirêk di NP-ê de dikare di dema pirnomî de jê were kêm kirin. Pirsgirêka SAT pirsgirêka yekem bû ku hate îsbat kirin ku NP-temam e, û ew wekî bingehek ji bo îsbatkirina NP-temamiya pirsgirêkên din re xizmet dike.
Ji bo bêtir ronîkirina têgeha verastkirina dema-polnomial-ê, pirsgirêka "Subset Sum" bifikirin. Ev pirsgirêk dipirse gelo binekomek ji komek jimareyên bêkêmasî yên ku digihîje nirxek armancek diyarkirî heye yan na. Pirsgirêka Binkoma Berhevokê di NP de ye ji ber ku, ji ber ku komek ji hejmarên bêkêmasî (S), nirxek armanc (t) û jêrkomek (S') ya (S) were dayîn, mirov dikare di dema pirnomî de verast bike ka berhevoka hêmanên di (S') wekhev (t) ye. Li vir nimûneya (x) cotê ((S, t)) ye, û sertîfîka (y) binekom e (S'). Verastker (V) kontrol dike ka kombûna hêmanên di (S') de (t) ye yan na, ku dikare di dema pirnomî de li gorî mezinahiya (S) were kirin.
Girîngiya verastkirina polînomî-demê ji ramanên teorîkî derbas dibe. Di warê pratîkî de, ev tê vê wateyê ku ji bo pirsgirêkên di NP-ê de, heke çareseriyek (sertîfîka) pêşniyar were peyda kirin, ew dikare bi bandor were kontrol kirin. Ev ji bo protokolên krîptografî, pirsgirêkên xweşbîniyê, û qadên cihêreng ên ku verastkirina rastdariya çareseriyek girîng e, bandorên girîng hene.
Bi kurtasî, çîna NP pirsgirêkên biryarê yên ku çareseriyek pêşniyarkirî dikare di dema pirnomî de ji hêla algorîtmayek diyarker ve were verast kirin vedihewîne. Ev têgeh di teoriya tevliheviya hesabkerî de bingehîn e û hem ji bo aliyên teorîkî hem jî pratîkî yên zanistiya komputerê xwedî bandorek kûr e. Lêkolîna NP, verastkirina-dema polînomî, û têgehên têkildar ên wekî NP-temamî berdewam dike ku qada lêkolînê ya zindî û krîtîk be.
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
- Ma P û NP bi rastî heman çîna tevliheviyê ne?
- Ma her çarçoveyek zimanek azad e di pola tevliheviya P de?
- 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?
Pir pirs û bersivan di Complexity de bibînin