MAX-3SAT
MAX-3SAT એ કોમ્પ્યુટર વિજ્ઞાનના કોમ્પ્યુટેશનલ જટિલતા પેટાક્ષેત્રમાં એક સમસ્યા છે. તે બુલિયન સંતોષકારક સમસ્યા (SAT) ને સામાન્ય બનાવે છે, જે જટિલતા સિદ્ધાંતમાં માનવામાં આવતી નિર્ણયની સમસ્યા છે. તેને આ રીતે વ્યાખ્યાયિત કરવામાં આવે છેઃ 3-સી. એન. એફ. સૂત્ર આપવામાં આવ્યું છે (એટલે કે. કલમ દીઠ વધુમાં વધુ 3 ચલ સાથે), એવી સોંપણી શોધો જે સૌથી વધુ કલમોને સંતોષે. MAX-3SAT એ જટિલતા વર્ગ MAXSNP માટે કેનોનિકલ સંપૂર્ણ સમસ્યા છે (પાપાડિમિટ્રિયો pg માં સંપૂર્ણ બતાવેલ છે. 314). અંદાજીતતા MAX-3SAT નું નિર્ણય સંસ્કરણ NP-પૂર્ણ છે. તેથી, બહુપદી-સમય ઉકેલ માત્ર ત્યારે જ પ્રાપ્ત કરી શકાય છે જો P = NP હોય. 2 ના પરિબળમાં અંદાજ આ સરળ અલ્ગોરિધમ સાથે પ્રાપ્ત કરી શકાય છે, જો કેઃ જ્યારે બધા ચલ = TRUE અથવા બધા ચલ = FALSE હોય ત્યારે મોટાભાગની કલમો સંતુષ્ટ હોય તેવા ઉકેલને આઉટપુટ કરો. દરેક કલમ બે ઉકેલોમાંથી એક દ્વારા સંતુષ્ટ થાય છે, તેથી એક ઉકેલ ઓછામાં ઓછી અડધી કલમોને સંતુષ્ટ કરે છે. કાર્લોફ-ઝ્વિક અલ્ગોરિધમ બહુપદી-સમયમાં ચાલે છે અને કલમ 7/8 ને સંતોષે છે. જ્યારે આ અલ્ગોરિધમ રેન્ડમાઇઝ્ડ હોય છે, ત્યારે તેનો ઉપયોગ કરીને તેને અલગ કરી શકાય છે, દા. ત., સમાન અંદાજ બાંયધરીઓ સાથે નિર્ધારક (બહુપદી-સમય) અલ્ગોરિધમ મેળવવાની તકનીકો. પ્રમેય 1 (અસંગતતા) પી. સી. પી. પ્રમેય સૂચવે છે કે ત્યાં એક ε> 0 અસ્તિત્વમાં છે કે જે MAX-3SAT નું (1-ε)-સમર્થન એન. પી.-હાર્ડ છે. પુરાવોઃ પી. સી. પી. પ્રમેય દ્વારા કોઈપણ એન. પી.-પૂર્ણ સમસ્યા. x ω L માટે, 3-CNF સૂત્ર મ્બાક્ષ બનાવવામાં આવે છે જેથી x ω L ωx સંતોષકારક હોય x ω L ωx ની (1-ε) m કલમો સંતોષકારક ન હોય. વેરિફાયર V બધા જરૂરી બિટ્સને એક જ સમયે વાંચે છે. બિન-અનુકૂલનશીલ પ્રશ્નો કરે છે. આ માન્ય છે કારણ કે પ્રશ્નોની સંખ્યા સ્થિર રહે છે. ધારો કે q એ પ્રશ્નોની સંખ્યા છે. તમામ રેન્ડમ સ્ટ્રિંગ્સની ગણતરી કરીને, આપણે દરેક સ્ટ્રિંગની લંબાઈથી પોલી (x) સ્ટ્રિંગ્સ મેળવીએ છીએ. દરેક Ri V માટે q સ્થાનો i1,., iq અને બુલિયન વિધેય fR: {0,1} q-> {0,1} પસંદ કરે છે અને જો અને માત્ર fR (π (i1,., iq)) હોય તો જ સ્વીકારે છે. અહીં π એ ઓરેકલમાંથી મેળવેલા સાબિતીનો સંદર્ભ આપે છે. આગળ આપણે આનું અનુકરણ કરવા માટે બુલિયન સૂત્ર શોધવાનો પ્રયાસ કરીએ છીએ. આપણે બુલિયન ચલ x1,., xl રજૂ કરીએ છીએ, જ્યાં l એ સાબિતીની લંબાઈ છે. ચકાસણીકર્તા સંભવિત બહુપદી-સમયમાં ચાલે છે તે દર્શાવવા માટે, આપણે સંતોષકારક કલમોની સંખ્યા અને ચકાસણીકર્તા સ્વીકારે છે તે સંભાવના વચ્ચે પત્રવ્યવહારની જરૂર છે. દરેક R માટે, 2q SAT કલમોનો ઉપયોગ કરીને fR (xi1,., xiq) નું પ્રતિનિધિત્વ કરતી કલમો ઉમેરો. લંબાઈ q ની કલમોને નવા (સહાયક) ચલ ઉમેરીને લંબાઈ 3 માં રૂપાંતરિત કરવામાં આવે છે. x2 * x10 * x11 * x12 = (x2 * x10 * yR) (R * x11 * x12). આ માટે મહત્તમ q2q 3-SAT કલમોની જરૂર છે. જો z ω L હોય તો ત્યાં એક એવો પુરાવો π છે કે જે દરેક Ri માટે Vπ (z) સ્વીકારે છે. જો xi = π (i) અને સહાયક ચલ યોગ્ય રીતે ઉમેરવામાં આવે તો તમામ કલમો સંતુષ્ટ થાય છે. જો ઇનપુટ z′L હોય તો x1,., xl અને yR ની દરેક સોંપણી માટે, અનુરૂપ સાબિતી π (i) = xi એ તમામ R ω {0,1} r (|z |) ના અડધા માટે ચકાસણીકર્તાને નકારવાનું કારણ બને છે. દરેક આર માટે, એફઆરનું પ્રતિનિધિત્વ કરતી એક કલમ નિષ્ફળ જાય છે. તેથી, કલમોનો અપૂર્ણાંક નિષ્ફળ જાય છે. એવું તારણ કાઢી શકાય છે કે જો આ દરેક એન. પી.-પૂર્ણ સમસ્યા માટે લાગુ પડે તો પી. સી. પી. થીયરમ સાચું હોવું જોઈએ. પ્રમેય 2 હેસ્ટાડ પ્રમેય 1 એટલે કે વધુ સખત પરિણામ દર્શાવે છે. ε માટે સૌથી જાણીતું મૂલ્ય. તે 3-SAT માટે પી. સી. પી. વેરિફાયર બનાવે છે જે પ્રૂફમાંથી માત્ર 3 બિટ્સ વાંચે છે. દરેક ε> 0 માટે, 3-SAT માટે એક PCP-ચકાસણીકર્તા M હોય છે જે લંબાઈની રેન્ડમ સ્ટ્રિંગ r વાંચે છે અને પ્રૂફ π અને બીટ br માં ક્વેરી પોઝિશન ir, jr, kr ની ગણતરી કરે છે. તે સ્વીકારે છે જો અને માત્ર ત્યારે જ જો 'π (ir) ωπ (jr) ωπ (kr) = br. ચકાસણી કરનારમાં પૂર્ણતા (1 − ε) અને મજબૂતી (પી. સી. પી. (જટિલતા) નો સંદર્ભ લો) હોય. જો આ બે સમીકરણોમાંથી પ્રથમ સમીકરણોને હંમેશની જેમ "= 1" સાથે સરખાવવામાં આવે, તો P = NP સૂચવતા રેખીય સમીકરણોની પ્રણાલીને હલ કરીને (MAX-3LIN-EQN જુઓ) π નો પુરાવો મળી શકે છે. જો ઝેડ. એલ. હોય, તો કલમોનો અપૂર્ણાંક (1 − ε) સંતોષાય છે. જો z′L હોય, તો R ના (1/2−ε) અપૂર્ણાંક માટે, 1/4 કલમો વિરોધાભાસી છે. આ અંદાજ ગુણોત્તરની કઠિનતાને સાબિત કરવા માટે પૂરતું છે સંબંધિત સમસ્યાઓ MAX-3SAT (B) એ MAX-3SAT નો પ્રતિબંધિત વિશેષ કેસ છે જ્યાં દરેક ચલ મહત્તમ B કલમોમાં જોવા મળે છે. પી. સી. પી. થીયરમ સાબિત થાય તે પહેલાં, પાપાડિમિટ્રિયુ અને યન્નાકાકિસે દર્શાવ્યું હતું કે અમુક નિશ્ચિત અચળાંક બી માટે, આ સમસ્યા મેક્સ એસ. એન. પી.-હાર્ડ છે. પરિણામે, પી. સી. પી. થીયરમ સાથે, તે એ. પી. એક્સ.-હાર્ડ પણ છે. આ ઉપયોગી છે કારણ કે MAX-3SAT (B) નો ઉપયોગ ઘણીવાર PTAS-જાળવણી ઘટાડો મેળવવા માટે કરી શકાય છે જે રીતે MAX-3SAT કરી શકતું નથી. બી ના સ્પષ્ટ મૂલ્યો માટેના પુરાવાઓમાં નીચેનાનો સમાવેશ થાય છેઃ તમામ બી ≤ 13, સંજીવ અરોરા, "પ્રોબેબિલિસ્ટિક ચેકિંગ ઓફ પ્રૂફ્સ એન્ડ હાર્ડનેસ ઓફ એપ્રોક્સીમેશન પ્રોબ્લેમ્સ", ઓગસ્ટ 1994માં સી. એસ. ડિવિઝન, યુ. સી. બર્કલે ખાતે રજૂ કરાયેલા શોધ નિબંધનું સુધારેલું સંસ્કરણ. CS-TR-476-94. વિભાગ 7.2. અને તમામ બી ≤3 (જે શ્રેષ્ઠ શક્ય છે). વધુમાં, 2SAT નિર્ણયની સમસ્યા બહુપદી સમયમાં ઉકેલી શકાય તેવી હોવા છતાં, MAX-2SAT (3) પણ APX-હાર્ડ છે. MAX-3SAT (B) માટે શ્રેષ્ઠ સંભવિત અંદાજ ગુણોત્તર, B ના કાર્ય તરીકે, ઓછામાં ઓછો અને વધુમાં વધુ હોય છે, સિવાય કે NP = RP. બી ના ચોક્કસ મૂલ્યો માટે અંદાજિત સ્થિરાંકો પરની કેટલીક સ્પષ્ટ સીમાઓ જાણીતી છે. બર્મન, કાર્પિન્સ્કી અને સ્કોટે સાબિત કર્યું કે MAX-3SAT ના "નિર્ણાયક" ઉદાહરણો માટે જેમાં દરેક શાબ્દિક બરાબર બે વાર આવે છે, અને દરેક કલમ બરાબર કદ 3 ની હોય છે, સમસ્યા એ છે કે કેટલાક સ્થિર પરિબળ માટે અંદાજ મુશ્કેલ છે. MAX-EkSAT એ MAX-3SAT નું પેરામીટરાઇઝ્ડ વર્ઝન છે જ્યાં દરેક કલમ બરાબર શાબ્દિક હોય છે, k "≤ 3 માટે. કોડિંગ થિયરીના વિચારોનો ઉપયોગ કરીને તેને અંદાજ ગુણોત્તર સાથે અસરકારક રીતે અંદાજિત કરી શકાય છે. તે સાબિત થયું છે કે MAX-3SAT ના અવ્યવસ્થિત ઉદાહરણોને પરિબળની અંદર અંદાજિત કરી શકાય છે. યુનિવર્સિટી ઓફ કેલિફોર્નિયા, બર્કલેના સંદર્ભ વ્યાખ્યાન નોંધો યુનિવર્સિટી એટ બફેલો ખાતે કોડિંગ થિયરી નોંધે છે સંતોષકારક સમસ્યાઓ એન. પી.-હાર્ડ સમસ્યાઓ