PCP theorem
કોમ્પ્યુટેશનલ કોમ્પ્લેક્સિટી થિયરીમાં, પી. સી. પી. થીયરમ (જેને પી. સી. પી. કેરેક્ટરાઇઝેશન થીયરમ તરીકે પણ ઓળખવામાં આવે છે) જણાવે છે કે એન. પી. કોમ્પ્લેક્સિટી ક્લાસમાં દરેક નિર્ણયની સમસ્યામાં સતત ક્વેરી કોમ્પ્લેક્સિટી અને લોગરિધમિક રેન્ડમનેસ કોમ્પ્લેક્સિટીના (રેન્ડમ બિટ્સના લોગરિધમિક નંબરનો ઉપયોગ કરે છે) સંભવિત રીતે ચકાસી શકાય તેવા પુરાવા (પુરાવા કે જે રેન્ડમાઇઝ્ડ અલ્ગોરિધમ દ્વારા ચકાસી શકાય છે) હોય છે. પી. સી. પી. થીયરમ કહે છે કે કેટલાક સાર્વત્રિક અચળાંક K માટે, દરેક n માટે, લંબાઈ n ના નિવેદન માટેના કોઈપણ ગાણિતિક સાબિતીને લંબાઈ બહુ (n) ના અલગ સાબિતી તરીકે ફરીથી લખી શકાય છે જે ઔપચારિક રીતે 99 ટકા ચોકસાઈ સાથે રેન્ડમાઇઝ્ડ અલ્ગોરિધમ દ્વારા ચકાસી શકાય છે જે તે સાબિતીના માત્ર K અક્ષરોની તપાસ કરે છે. પી. સી. પી. થીયરમ એ અંદાજની ગણતરીની કઠિનતાના સિદ્ધાંતનો પાયાનો છે, જે વિવિધ ઓપ્ટિમાઇઝેશન સમસ્યાઓ માટે કાર્યક્ષમ અંદાજ અલ્ગોરિધમ્સ ડિઝાઇન કરવામાં સહજ મુશ્કેલીની તપાસ કરે છે. તેને ઇંગો વેજનર દ્વારા "કૂકના પ્રમેય પછી જટિલતા સિદ્ધાંતમાં સૌથી મહત્વપૂર્ણ પરિણામ" તરીકે વર્ણવવામાં આવ્યું છે અને ઓડેડ ગોલ્ડરીચ દ્વારા "નવીન વિચારોમાં સમૃદ્ધ પ્રભાવશાળી કાર્યોના ક્રમની પરાકાષ્ઠા" તરીકે વર્ણવવામાં આવ્યું છે. ઔપચારિક નિવેદન પી. સી. પી. થીયરમ જણાવે છે કે એન. પી. = પી. સી. પી. [ઓ. (લોગ એન.), ઓ. (1)], જ્યાં પી. સી. પી. [આર. (એન.), ક્યૂ. (એન.)] એ સમસ્યાઓનો વર્ગ છે જેના માટે ઉકેલનો સંભવિત રીતે ચકાસી શકાય તેવો પુરાવો આપી શકાય છે, જેમ કે રેન્ડમના આર. (એન.) બિટ્સનો ઉપયોગ કરીને બહુપદી સમયમાં પુરાવો ચકાસી શકાય છે અને સાબિતીના ક્યૂ. (એન.) બિટ્સ વાંચીને, સાચા પુરાવો હંમેશા સ્વીકારવામાં આવે છે, અને ખોટા પુરાવોને ઓછામાં ઓછા 1/2 સંભાવના સાથે નકારી કાઢવામાં આવે છે. n એ સમસ્યાના ઉદાહરણના વર્ણનની લંબાઈ છે. વધુમાં નોંધ કરો કે ચકાસણી અલ્ગોરિધમ બિન-અનુકૂલનશીલ છેઃ તપાસ કરવા માટે સાબિતીના બિટ્સની પસંદગી માત્ર રેન્ડમ બિટ્સ અને સમસ્યાના ઉદાહરણના વર્ણન પર આધારિત છે, સાબિતીના વાસ્તવિક બિટ્સ પર નહીં. પી. સી. પી. અને અંદાજની કઠિનતા પી. સી. પી. પ્રમેયની વૈકલ્પિક રચના જણાવે છે કે અવરોધ સંતોષ સમસ્યાના સંતોષકારક અવરોધોનો મહત્તમ અપૂર્ણાંક કેટલાક સ્થિર પરિબળમાં એન. પી.-હાર્ડથી અંદાજિત છે. ઔપચારિક રીતે, કેટલાક અચળાંકો q અને α <1 માટે, નીચેની વચન સમસ્યા (લાયસ, Lno) એ NP-સખત નિર્ણય સમસ્યા છેઃ લાયસ = {φ: માં તમામ અવરોધો એક સાથે સંતોષકારક છે} Lno = {φ: દરેક સોંપણી φ ના અવરોધોના α અપૂર્ણાંક કરતાં ઓછી સંતોષ આપે છે}, જ્યાં φ એ બુલિયન મૂળાક્ષર પર મર્યાદા સંતોષ સમસ્યા (CSP) છે જેમાં મર્યાદા દીઠ મહત્તમ q ચલ હોય છે. ઉપર ઉલ્લેખિત વર્ગ પી. સી. પી. સાથે જોડાણ એ નોંધવાથી જોઈ શકાય છે કે સાબિતીમાં બિટ્સ q ની સતત સંખ્યાને તપાસવાથી સાબિતીના તે બિટ્સ પર q બુલિયન ચલમાં અવરોધનું મૂલ્યાંકન તરીકે જોઈ શકાય છે. ચકાસણી અલ્ગોરિધમ યાદૃચ્છિકતાના ઓ (લોગ એન) બિટ્સનો ઉપયોગ કરે છે, તેથી તેને ઉપર વર્ણવ્યા મુજબ પોલી (એન) અવરોધો સાથે સી. એસ. પી. તરીકે રજૂ કરી શકાય છે. પી. સી. પી. પ્રમેયની અન્ય લાક્ષણિકતા પછી વચનની શરતને α = 1/2 સાથે બાંયધરી આપે છેઃ જો એન. પી. સમસ્યાનો જવાબ હા હોય, તો દરેક અવરોધ (જે રેન્ડમ બિટ્સ માટે ચોક્કસ મૂલ્યને અનુરૂપ હોય છે) સંતોષકારક સોંપણી (સ્વીકાર્ય સાબિતી) ધરાવે છે; અન્યથા, કોઈપણ સાબિતીને ઓછામાં ઓછી 1/2 સંભાવના સાથે નકારી કાઢવી જોઈએ, જેનો અર્થ છે કે કોઈપણ સોંપણીએ અડધાથી ઓછી મર્યાદાઓને સંતોષવી જોઈએ (જેનો અર્થ છે કે તે 1/2 કરતા ઓછી સંભાવના સાથે સ્વીકારવામાં આવશે). તેથી, વચન સમસ્યા માટેનું એક અલ્ગોરિધમ અંતર્ગત એન. પી. સમસ્યાને હલ કરવામાં સક્ષમ હશે, અને તેથી વચન સમસ્યા એન. પી. સખત હોવી જોઈએ. આ પ્રમેયના પરિણામે, એવું દર્શાવી શકાય છે કે મહત્તમ બુલિયન સૂત્ર સંતોષકારક, આલેખમાં મહત્તમ સ્વતંત્ર સમૂહ અને જાળીઓ માટેની ટૂંકી વેક્ટર સમસ્યા સહિત ઘણી કુદરતી ઓપ્ટિમાઇઝેશન સમસ્યાઓના ઉકેલો જ્યાં સુધી P = NP ન હોય ત્યાં સુધી અસરકારક રીતે અંદાજિત કરી શકાતા નથી. આ ઉપરોક્ત સ્વરૂપની વચનની સમસ્યાના ઉકેલની અંદાજિત સમસ્યાને ઘટાડીને કરી શકાય છે. આ પરિણામોને કેટલીકવાર પી. સી. પી. પ્રમેયો પણ કહેવામાં આવે છે કારણ કે તેમને કેટલાક વધારાના માળખા સાથે એન. પી. માટે સંભવિત રીતે ચકાસી શકાય તેવા પુરાવા તરીકે જોઈ શકાય છે. સાબિતી નબળા પરિણામનો પુરાવો, એન. પી. પી. પી. [એન. 3,1] ડેક્સટર કોઝેનના એક વ્યાખ્યાનમાં આપવામાં આવ્યો છે. પી. સી. પી. થીયરમ એ ઇન્ટરેક્ટિવ સાબિતીઓ અને સંભવિત રીતે ચકાસી શકાય તેવા સાબિતીઓ પર કામ કરવાની લાંબી લાઇનની પરાકાષ્ઠા છે. પ્રમાણભૂત પુરાવાઓ અને સંભવિત રીતે ચકાસી શકાય તેવા પુરાવાઓને લગતા પ્રથમ પ્રમેય એ નિવેદન છે કે NEXP [પોલી (એન), પોલી (એન)] દ્વારા સાબિત થયું છે. આદ્યાક્ષરોની ઉત્પત્તિ પી. સી. પી. સી. (એન), એસ (એન) [આર (એન), ક્યૂ (એન)] સંકેતો સંભવિત રીતે ચકાસી શકાય તેવા પુરાવા પર સમજાવવામાં આવ્યા છે. નોટેશન એ ફંક્શનનું છે જે ચોક્કસ જટિલતા વર્ગ આપે છે. ઉપર જણાવેલી સમજૂતી જુઓ. આ પ્રમેય ("પી. સી. પી. પ્રમેય") નું નામ કદાચ "પી. સી. પી". એટલે કે "સંભવિત રીતે ચકાસી શકાય તેવા પુરાવા" અથવા ઉપર ઉલ્લેખિત સંકેતો (અથવા બંને) માંથી આવે છે. પ્રથમ પ્રમેય [1990 માં] ત્યારબાદ, આ કાર્યમાં ઉપયોગમાં લેવાતી પદ્ધતિઓ 1991 માં બાબાઇ, લાન્સ ફોર્ટનો, લેવિન અને સેજેડી, ફીજ, ગોલ્ડવાસર, લંડ, સફરા અને સેજેડી (1991), અને અરોરા અને સફરા દ્વારા 1992 માં અરોરા, લંડ, મોટવાની, સુદાન અને સેજેડી દ્વારા 1998 માં પી. સી. પી. પ્રમેયનો પુરાવો આપવા માટે વિસ્તૃત કરવામાં આવી હતી. 2001નો ગોડેલ પુરસ્કાર સંજીવ અરોરા, ઉરીએલ ફીગે, શફી ગોલ્ડવાસર, કાર્સ્ટન લંડ, લેઝલો લોવેઝ, રાજીવ મોટવાની, શ્મુએલ સફરા, મધુ સુદાન અને મારિયો સેજેડીને પી. સી. પી. પ્રમેય પર કામ કરવા અને અંદાજની કઠિનતા સાથે તેના જોડાણ માટે એનાયત કરવામાં આવ્યો હતો. 2005માં ઇરિટ દીનુરએ વિસ્તરણ આલેખનો ઉપયોગ કરીને પી. સી. પી. પ્રમેયનો નોંધપાત્ર રીતે સરળ પુરાવો શોધ્યો હતો. તેણીને આ માટે 2019 ગોડેલ પુરસ્કાર મળ્યો હતો. 2012 માં, થોમસ વિડિક અને ત્સુયોશી ઇતોએ એક પરિણામ પ્રકાશિત કર્યું હતું જેણે "મલ્ટિપ્લેયર રમતમાં સંડોવણી કરવા માટે ગૂંચવાયેલા સમર્થકોની ક્ષમતા પર મજબૂત મર્યાદા" દર્શાવી હતી. આ પી. સી. પી. થીયરમના ક્વોન્ટમ એનાલોગને સાબિત કરવાની દિશામાં એક પગલું હોઈ શકે છે, કારણ કે જ્યારે પરિણામ મીડિયામાં નોંધવામાં આવ્યું હતું, ત્યારે પ્રોફેસર ડોરિટ અહરોનોવે તેને "મલ્ટિપ્રોવર ઇન્ટરેક્ટિવ પ્રૂફ પરના અગાઉના પેપરનું ક્વોન્ટમ એનાલોગ" ગણાવ્યું હતું જે "મૂળભૂત રીતે પી. સી. પી. થીયરમ તરફ દોરી ગયું હતું". 2018માં, થોમસ વિડિક અને આનંદ નટરાજને રેન્ડમાઇઝ્ડ રિડક્શન હેઠળ ક્વોન્ટમ પી. સી. પી. થીયરમનો ગેમ વેરિઅન્ટ સાબિત કર્યો હતો. તે જણાવે છે કે ક્યુએમએ એમઆઇપી * [લોગ (એન), 1,1/2], જ્યાં એમઆઇપી * [એફ (એન), સી, એસ] એ એફ (એન)-બીટ શાસ્ત્રીય સંદેશાવ્યવહાર સાથેની મલ્ટી-પ્રોવર ક્વોન્ટમ ઇન્ટરેક્ટિવ પ્રૂફ સિસ્ટમ્સનો જટિલતા વર્ગ છે, અને પૂર્ણતા સી છે અને ધ્વનિ એસ છે. તેઓએ એ પણ દર્શાવ્યું કે ક્વોન્ટમ પીસીપી અનુમાનનું હેમિલ્ટોનિયન સંસ્કરણ, એટલે કે સતત વચન અંતર સી-એસ સાથે સ્થાનિક હેમિલ્ટોનિયન સમસ્યા ક્યુએમએ-હાર્ડ છે, જે રમતના ક્વોન્ટમ પીસીપી પ્રમેયને સૂચવે છે. એન. એલ. ટી. એસ. અનુમાન એ મૂળભૂત વણઉકેલાયેલી અવરોધ અને પી. સી. પી. ના ક્વોન્ટમ એનાલોગનો પુરોગામી છે. નોંધો સંદર્ભો. . . . . . કોમ્પ્યુટેશનલ કોમ્પ્લેક્સિટી થિયરીમાં રેન્ડમાઇઝ્ડ એલ્ગોરિધમ્સ પ્રમેયો