Random self-reducibility
રેન્ડમ સેલ્ફ-રિડ્યુસિબિલિટી (આરએસઆર) એ નિયમ છે કે સરેરાશ કેસ માટે સારો અલ્ગોરિધમ સૌથી ખરાબ કેસ માટે સારો અલ્ગોરિધમ સૂચવે છે. આરએસઆર એ ઉદાહરણોના મોટા ભાગને હલ કરીને સમસ્યાના તમામ ઉદાહરણોને હલ કરવાની ક્ષમતા છે. વ્યાખ્યા જો કોઈ પણ ઉદાહરણ x નું મૂલ્યાંકન કરતા વિધેય f માટે બહુપદી સમયમાં એક અથવા વધુ યાદૃચ્છિક ઉદાહરણો yi પર f ના મૂલ્યાંકનમાં ઘટાડો કરી શકાય, તો તે સ્વ-ઘટાડી શકાય તેવું છે (આને બિન-અનુકૂલનશીલ સમાન સ્વ-ઘટાડો તરીકે પણ ઓળખવામાં આવે છે). રેન્ડમ સેલ્ફ-રિડક્શનમાં, f ના ડોમેનમાં મનસ્વી સૌથી ખરાબ-કેસ ઇન્સ્ટન્સ x ને y1,., yk ઇન્સ્ટન્સના રેન્ડમ સેટમાં મેપ કરવામાં આવે છે. આ એટલા માટે કરવામાં આવે છે કે જેથી f (x) ની ગણતરી બહુપદી સમયમાં કરી શકાય, મેપિંગમાંથી સિક્કો-ટૉસ ક્રમ આપવામાં આવે, x, અને f (y1),., f (yk). તેથી, yi પર પ્રેરિત વિતરણના સંદર્ભમાં સરેરાશ લેતા, f ની સરેરાશ-કેસ જટિલતા એ f ની સૌથી ખરાબ-કેસ રેન્ડમાઇઝ્ડ જટિલતા જેટલી જ (બહુપદી પરિબળોની અંદર) છે. એક ખાસ નોંધ એ છે કે જ્યારે દરેક રેન્ડમ ઉદાહરણ yi એ f ના ડોમેનમાં તત્વોના સમગ્ર સમૂહ પર સમાન રીતે વહેંચવામાં આવે છે જેની લંબાઈ |x | હોય છે. આ કિસ્સામાં f સરેરાશ એટલું જ મુશ્કેલ છે જેટલું તે સૌથી ખરાબ કિસ્સામાં છે. આ અભિગમમાં બે મુખ્ય પ્રતિબંધો છે. પ્રથમ y1,., yk ની પેઢી બિન-અનુકૂલનશીલ રીતે કરવામાં આવે છે. આનો અર્થ એ છે કે f (y1) જાણીતા થાય તે પહેલાં y2 પસંદ કરવામાં આવે છે. બીજું, તે જરૂરી નથી કે y1,., yk બિંદુઓ સમાનરૂપે વહેંચવામાં આવે. ક્રિપ્ટોગ્રાફિક પ્રોટોકોલમાં એપ્લિકેશન એવી સમસ્યાઓ કે જેમાં ડેટામાં થોડી ગોપનીયતાની જરૂર હોય (સામાન્ય રીતે ક્રિપ્ટોગ્રાફિક સમસ્યાઓ) તે ગોપનીયતાની ખાતરી કરવા માટે રેન્ડમાઇઝેશનનો ઉપયોગ કરી શકે છે. હકીકતમાં, એકમાત્ર સાબિત રીતે સુરક્ષિત ક્રિપ્ટોગ્રાફિક સિસ્ટમ (વન-ટાઇમ પેડ) તેની સુરક્ષા ધરાવે છે જે સિસ્ટમને પૂરા પાડવામાં આવેલ મુખ્ય ડેટાની અવ્યવસ્થિતતા પર સંપૂર્ણપણે આધાર રાખે છે. ક્રિપ્ટોગ્રાફીનું ક્ષેત્ર એ હકીકતનો ઉપયોગ કરે છે કે અમુક સંખ્યા-સૈદ્ધાંતિક કાર્યો અવ્યવસ્થિત રીતે સ્વ-ઘટાડી શકાય તેવા હોય છે. આમાં સંભવિત એન્ક્રિપ્શન અને ક્રિપ્ટોગ્રાફિકલી મજબૂત સ્યુડોરાન્ડમ નંબર જનરેશનનો સમાવેશ થાય છે. ઉપરાંત, ઉદાહરણ-છુપાવવાની યોજનાઓ (જ્યાં નબળું ખાનગી ઉપકરણ તેની માહિતી જાહેર કર્યા વિના મજબૂત જાહેર ઉપકરણનો ઉપયોગ કરે છે) સરળતાથી રેન્ડમ સ્વ-ઘટાડા દ્વારા ઉદાહરણરૂપ છે. ઉદાહરણો સ્વતંત્ર લઘુગણક સમસ્યા, દ્વિઘાત અવશેષ સમસ્યા, આર. એસ. એ. વ્યુત્ક્રમ સમસ્યા અને મેટ્રિક્સની કાયમી ગણતરીની સમસ્યા એ દરેક અવ્યવસ્થિત સ્વ-ઘટાડી શકાય તેવી સમસ્યાઓ છે. અલગ લઘુગણક પ્રમેય-|G | કદના ચક્રીય જૂથ G આપવામાં આવે છે. જો નિર્ધારક બહુપદી સમય અલ્ગોરિધમ A તમામ ઇનપુટ્સના 1/પોલી (n) અપૂર્ણાંક માટે અલગ લઘુગણકની ગણતરી કરે છે (જ્યાં n = log |G | એ ઇનપુટ કદ છે), તો પછી તમામ ઇનપુટ્સ માટે અલગ લઘુગણક માટે એક રેન્ડમાઇઝ્ડ બહુપદી સમય અલ્ગોરિધમ છે. ચક્રીય જૂથ G = {gi | 0 ≤ i <|G |} નું જનરેટર g અને x bul G આપવામાં આવે તો, આધાર g પર x નો સ્વતંત્ર લોગ x = gk સાથે પૂર્ણાંક k (0 ≤ k <|G |) છે. B ને {0,., |G | −1} પર સમાનરૂપે વિતરિત કરવા માટે લો, પછી xgB = gk + B પણ G પર સમાનરૂપે વિતરિત થાય છે. તેથી xgB એ x થી સ્વતંત્ર છે, અને તેના લઘુગણકની ગણતરી બહુપદી સમયમાં સંભાવના 1/પોલી (n) સાથે કરી શકાય છે. પછી loggx ષ્ણ loggxgB-B (મૉડ |G |) અને સ્વતંત્ર લઘુગણક સ્વ-ઘટાડી શકાય તેવું છે. મેટ્રિક્સની કાયમી વ્યાખ્યા જોતાં, તે સ્પષ્ટ છે કે કોઈપણ n-by-n મેટ્રિક્સ M માટે PERM (M) એ M માં એન્ટ્રીઓ પર n ડિગ્રીની બહુપરીમાણીય બહુપદી છે. મેટ્રિક્સની કાયમી ગણતરી કરવી એ એક મુશ્કેલ ગણતરી કાર્ય છે-PERM એ #P-પૂર્ણ (સાબિતી) હોવાનું દર્શાવવામાં આવ્યું છે. વધુમાં, મોટાભાગના મેટ્રિસીસ માટે PERM (M) ની ગણતરી કરવાની ક્ષમતા એ રેન્ડમ પ્રોગ્રામનું અસ્તિત્વ સૂચવે છે જે તમામ મેટ્રિસીસ માટે PERM (M) ની ગણતરી કરે છે. આ દર્શાવે છે કે PERM અવ્યવસ્થિત રીતે સ્વ-ઘટાડી શકાય તેવું છે. નીચેની ચર્ચા એ કેસને ધ્યાનમાં લે છે કે જ્યાં અમુક મુખ્ય p માટે મર્યાદિત ક્ષેત્ર Fp માંથી મેટ્રિક્સ એન્ટ્રીઓ દોરવામાં આવે છે, અને જ્યાં તે ક્ષેત્રમાં તમામ અંકગણિત કરવામાં આવે છે. ધારો કે X એ Fp માંથી એન્ટ્રીઓ સાથે રેન્ડમ n-બાય-n મેટ્રિક્સ છે. કોઈપણ મેટ્રિક્સ M + kX ની તમામ એન્ટ્રીઓ k ના રેખીય વિધેયો હોવાથી, PERM (M) ની ગણતરી કરતી ડિગ્રી n મલ્ટિવેરિયેટ બહુપદી સાથે તે રેખીય વિધેયોની રચના કરીને આપણને k પર બીજી ડિગ્રી n બહુપદી મળે છે, જેને આપણે p (k) કહીશું. સ્પષ્ટપણે, p (0) એ M ના કાયમી બરાબર છે. ધારો કે આપણે એક એવો પ્રોગ્રામ જાણે છે જે મોટાભાગના n-by-n મેટ્રિસીસ માટે PERM (A) ના સાચા મૂલ્યની ગણતરી કરે છે, જેમાં Fp------------------------------------------------------------------------------------------------------------------------------------------------------ - પછી લગભગ બે તૃતીયાંશ સંભાવના સાથે, આપણે k = 1,2,., n + 1 માટે PERM (M + kX) ની ગણતરી કરી શકીએ છીએ. એકવાર આપણી પાસે તે n + 1 મૂલ્યો હોય, તો આપણે ઇન્ટરપોલેશનનો ઉપયોગ કરીને p (k) ના ગુણાંક માટે ઉકેલ લાવી શકીએ છીએ (યાદ રાખો કે p (k) ની ડિગ્રી n છે). એકવાર આપણે p (k) બરાબર જાણી લઈએ, પછી આપણે p (0) નું મૂલ્યાંકન કરીએ છીએ, જે PERM (M) ની બરાબર છે. જો આપણે આમ કરીએ, તો આપણે એક તૃતીયાંશ વખત ખોટા બનવાનું જોખમ ચલાવીએ છીએ, પરંતુ બહુવિધ રેન્ડમ એક્સ પસંદ કરીને અને ઉપરોક્ત પ્રક્રિયાને ઘણી વખત પુનરાવર્તન કરીને, અને માત્ર જવાબ તરીકે બહુમતી વિજેતા પ્રદાન કરીને, આપણે ભૂલ દરને ખૂબ ઓછો કરી શકીએ છીએ. પરિણામ જો એન. પી.-પૂર્ણ સમસ્યા બિન-અનુકૂલનશીલ રીતે સ્વયં-ઘટાડી શકાય તેવી હોય તો બહુપદી પદાનુક્રમ σ3 પર તૂટી જાય છે. જો કોએનપી-હાર્ડ સમસ્યા ઓ (લોગ એન/એન) માં રેન્ડમ સેલ્ફ-રિડ્યુસિબલ હોય તો σ2 = Π2. સંદર્ભો એમ. અબાદી, જે. ફીગેનબૌમ, અને જે. કિલિયન, ઓન હાઈડિંગ ઇન્ફર્મેશન ફ્રોમ એન ઓરેકલ, જે. કોમ્પુટ. સિસ્ટ. વિજ્ઞાન., 1989 એસ. અરોરા, પીસીપી પ્રમેયની આસપાસ, 1996 જે. ફીગેનબૌમ, એલ. ફોર્ટનો, સંપૂર્ણ સમૂહોની રેન્ડમ-સેલ્ફ-રિડ્યુસિબિલિટી પર, 1991 રેન્ડમાઇઝ્ડ અલ્ગોરિધમ્સ