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ênasîn û Têkilî
Pirsgirêka SAT: Pirsgirêka SAT bi destnîşankirina ka gelo veqetandinek nirxên rastiyê ji guhêrbaran re heye ku formulek Boolean ya diyar rast dike. Formulek Boolean bi gelemperî di forma normal ya hevedudanî (CNF) de tête diyar kirin, ku formula lihevhatina bendan e, û her bend veqetandek ji peyvan e. Mînakî, formûlek dikare wiha xuya bike:
![\[ (x_1 \lor \neg x_2) \erd (\ neg x_1 \lor x_3) \erd (x_2 \lor \ neg x_3). \]](https://eitca.org/wp-content/ql-cache/quicklatex.com-8e405df3b02de2e85a91e7957c82bb5b_l3.png "Ji hêla QuickLaTeX.com ve hatî pêşkêş kirin")
NP (Dema Polynomiya Nedeterminîstîk): Pirsgirêka biryarê di NP de ye heke çareseriyek diyarkirî di dema pirnomial de ji hêla makîneya Turing a diyarker ve wekî rast an nerast were verast kirin. Di bingeh de, heke we çareseriyek berendamek heye, hûn dikarin pêbaweriya wê bi bandor kontrol bikin.
NP-Temam: Pirsgirêkek NP-temam e heke ew du şertan têr dike:
1. Di NP de ye.
2. Her pirsgirêkek di NP de dikare di dema pirnomî de jê were kêm kirin.
Têgeha NP-temambûnê ji hêla Stephen Cook ve di gotara xwe ya seretayî ya sala 1971-an de "Tevhevbûna Pêvajoyên Teorem-Îsbatkirinê" hate destnîşan kirin, ku wî destnîşan kir ku pirsgirêka SAT yekem pirsgirêka NP-temamî ya naskirî ye. Ev encam niha wekî Teorema Cook tê zanîn.
Teorema Cook û Encamên Wê
Ji bo ku fêm bikin ka çima SAT NP-temam e, divê em du xalên sereke saz bikin:
1. SAT di NP de ye.
2. Her pirsgirêk di NP de dikare di dema polînomî de bi SAT kêm bibe.
SAT di NP de ye
Ji bo verastkirina ku SAT di NP de ye, bihesibînin ku formula Boolean û pêşniyarek nirxên rastiyê ji guhêrbarên wê re tê dayîn, em dikarin kontrol bikin ka formula di dema pirnomî de rast dinirxîne. Ev tê de nirxandina her bendek di formulê de ye da ku hûn bibînin ka bi kêmanî yek biwêj di her bendê de rast e. Ji ber ku nirxandina formula Boolean pêvajoyek rasterast e ku hejmareke bêdawî ya operasyonên mantiqî pêk tîne, ew dikare bi bandor were kirin. Bi vî rengî, SAT di NP-ê de ye ji ber ku em dikarin çareseriyek di dema polînomî de verast bikin.
Kêmkirina Polynomial-Time
Beşa dijwartir a îsbatkirina ku SAT NP-temam e ev e ku nîşan dide ku her pirsgirêk di NP de dikare di dema polînomî de ji SAT were kêm kirin. Vê yekê destnîşan dike ku ji bo her pirsgirêkek di NP-ê de, fonksiyonek hesabker-dem-polnomî heye ku mînakên pirsgirêkê vediguhezîne mînakên SAT-ê wusa ku pirsgirêka orîjînal çareseriyek heye ger û tenê heke mînaka SAT-a veguherî têrker be.
Ji bo ronîkirina vê yekê, pirsgirêkek gelemperî bifikirin 
li NP. Ji hêla pênasê ve, makîneyek Turing-a-dema pirnomî ya nedetermînîst heye 
ku biryar dide . Makîne xwedan pêvajoyek verastkirinê ya polînomî ye ku dikare kontrol bike ka sertîfîkayek (çareserî) derbasdar e. Em dikarin operasyonê şîfre bikin li ser input 
wek formula Boolean wisa ku formula têrker e ger û tenê heke qebûl dike .
Encoding gavên jêrîn pêk tîne:
1. Veavakirina Encoding: Veavakirinên (dewlet, naverokên tape, û pozîsyonên serî) yên şîfre bikin wek guherbarên Boolean. Her veavakirin dikare bi rêzek bits ve were temsîl kirin.
2. Transition Encoding: Kodkirina fonksiyona derbasbûnê ya wekî komek astengên Boolean. Van astengan piştrast dikin ku veguheztinên derbasdar di navbera mîhengan de têne girtin.
3. Dewletên Destpêk û Qebûl: Veavakirina destpêkê (gava ku makîne dest pê dike) û veavakirina pejirandinê (gava ku makîne disekine û qebûl dike) wekî astengên Boolean şîfre bikin.
Bi avakirina formula Boolean ku tevgerê digire , em mînakek SAT-ê diafirînin ku têr be heke û tenê heke rêzek veguheztinên derbasdar hebe ku berbi rewşek pejirandinê ve diçe. Ev kêmkirin dikare di dema polînomî de li gorî mezinahiya têketinê were kirin .
Mînak: Kêmkirina ji 3-SAT bo SAT
Ji bo ronîkirina têgeha kêmkirina polînomî-demê, rewşa taybetî ya kêmkirina 3-SAT-ê ji SAT-ê re binirxînin. Pirsgirêka 3-SAT rewşek taybetî ya SAT-ê ye ku her bend bi rastî sê tîpan heye. Ji bo kêmkirina 3-SAT bo SAT, em dikarin bi hêsanî bibînin ku her mînakek 3-SAT jixwe di forma ku ji hêla SAT-ê ve tê xwestin de ye (ango, formula CNF). Ji ber vê yekê, kêmkirin kêmasî ye û dikare di dema xêzikî de were kirin, ku kêmkirina-dema polînomî ye.
Encamên SAT ku NP-Temam e
Dabeşkirina SAT-ê wekî NP-temamî ji bo teoriya tevliheviya hesabkerî û çareserkirina pirsgirêka pratîkî bandorek kûr heye. Ji ber ku SAT NP-temam e, her pirsgirêkek di NP de dikare di mînakek SAT de were wergerandin. Ev gerdûnî tê vê wateyê ku SAT ji bo tevliheviya pirsgirêkên din wekî pîvanek xizmet dike. Ger em bikarin algorîtmayek-dema polynomial-ê bibînin ku SAT çareser bike, em dikarin hemî pirsgirêkên NP-ê di dema pirnomî de çareser bikin, tê wateya 
.
Berevajî vê, heke em îspat bikin ku ji bo SAT-ê algorîtmayek-dem-polnomial tune ye, ew ê tê vê wateyê ku 
. Tevî lêkolînên berfireh, pirsa ka gelo di zanistiya komputerê de yek ji pirsgirêkên vekirî yên herî girîng dimîne.
Serketên praktîkî
Di pratîkê de, çareserkerên SAT bi berfirehî di warên cihêreng de têne bikar anîn, di nav de verastkirina nermalavê, îstîxbarata sûnî, û krîptografî. Vebijêrkên SAT-ê yên nûjen algorîtmayên sofîstîke û heurîstîk bikar tînin da ku mînakên mezin û tevlihev bi karîgerî bi rê ve bibin, tevî tevhevbûna NP-ya teorîkî ya SAT. Van çareserkeran mimkun kir ku pirsgirêkên cîhana rastîn ên ku berê neçar bûn çareser bikin.
Xelasî
Pirsgirêka SAT bi rastî pirsgirêkek NP-temam e, wekî ku ji hêla Teorema Cook ve hatî damezrandin. Ev dabeşkirin li ser vê rastiyê ye ku SAT di NP de ye û her pirsgirêk di NP de dikare di dema polînomî de ji SAT were kêm kirin. Encamên ku SAT-a NP-tevahî ye, dûr e, hem bandorê li lêkolîna teorîkî û hem jî serîlêdanên pratîkî yên di zanistiya komputerê de dike.
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 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?
- 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