Unique games conjecture
કોમ્પ્યુટેશનલ કોમ્પ્લેક્સિટી થિયરીમાં, અનન્ય રમત અનુમાન (જેને ઘણીવાર યુ. જી. સી. તરીકે ઓળખવામાં આવે છે) એ સુભાષ ખોટ દ્વારા 2002માં કરવામાં આવેલ અનુમાન છે. આ અનુમાન એવું માને છે કે વિશિષ્ટ રમત તરીકે ઓળખાતી ચોક્કસ પ્રકારની રમતનું અંદાજિત મૂલ્ય નક્કી કરવાની સમસ્યામાં એન. પી.-હાર્ડ કોમ્પ્યુટેશનલ જટિલતા છે. અંદાજની કઠિનતાના સિદ્ધાંતમાં તેનો વ્યાપક ઉપયોગ થાય છે. જો અનન્ય રમત અનુમાન સાચું હોય અને P ષ્ણુત NP હોય, તો ઘણી મહત્વપૂર્ણ સમસ્યાઓ માટે બહુપદી સમયમાં ચોક્કસ ઉકેલ મેળવવો માત્ર અશક્ય જ નથી (જેમ કે P વિરુદ્ધ NP સમસ્યા દ્વારા પ્રતિપાદિત), પરંતુ સારી બહુપદી-સમય અંદાજ મેળવવો પણ અશક્ય છે. આવી અસંગતતા જે સમસ્યાઓ માટે પરિણમે છે તેમાં અવરોધ સંતોષની સમસ્યાઓનો સમાવેશ થાય છે, જે વિવિધ શાખાઓમાં ઊભી થાય છે. આ અનુમાન અસામાન્ય છે કારણ કે તે સાચું છે કે નહીં તે અંગે શૈક્ષણિક જગત લગભગ સમાનરૂપે વિભાજિત લાગે છે. રચનાઓ અનન્ય રમતના અનુમાનને ઘણી સમાન રીતે કહી શકાય. અનન્ય લેબલ આવરણ અનન્ય રમતના અનુમાનની નીચેની રચનાનો ઉપયોગ ઘણીવાર અંદાજની કઠિનતામાં થાય છે. આ અનુમાન અનન્ય અવરોધો સાથે લેબલ કવર તરીકે ઓળખાતી નીચેની વચન સમસ્યાની એન. પી.-કઠોરતાને રજૂ કરે છે. દરેક ધાર માટે, બે શિરોબિંદુઓ પરના રંગો અમુક ચોક્કસ ક્રમબદ્ધ જોડીઓ સુધી મર્યાદિત છે. અનન્ય અવરોધોનો અર્થ એ છે કે દરેક ધાર માટે કોઈ પણ ક્રમાંકિત જોડી સમાન નોડ માટે સમાન રંગ ધરાવતી નથી. આનો અર્થ એ છે કે કદ k ના મૂળાક્ષર પર અનન્ય મર્યાદાઓ સાથે લેબલ કવરનું ઉદાહરણ πe: [k] → [k] ક્રમચયોના સંગ્રહ સાથે નિર્દેશિત આલેખ તરીકે રજૂ કરી શકાય છે, જે આલેખની દરેક ધાર e માટે એક છે. લેબલ કવર ઉદાહરણની સોંપણી G ના દરેક શિરોબિંદુને સમૂહ [k] = {1,2,. k} માં મૂલ્ય આપે છે, જેને ઘણીવાર "રંગો" કહેવામાં આવે છે. આવા ઉદાહરણો એ અર્થમાં મજબૂત રીતે મર્યાદિત હોય છે કે શિરોબિંદુ રંગ તેના પડોશીઓના રંગોને અનન્ય રીતે વ્યાખ્યાયિત કરે છે, અને તેથી તેના સંપૂર્ણ જોડાયેલા ઘટક માટે. આમ, જો ઇનપુટ ઉદાહરણ માન્ય સોંપણી સ્વીકારે છે, તો આવી સોંપણી એક જ નોડના તમામ રંગો પર પુનરાવર્તન કરીને અસરકારક રીતે શોધી શકાય છે. ખાસ કરીને, આપેલ ઉદાહરણ સંતોષકારક સોંપણી સ્વીકારે છે કે નહીં તે નક્કી કરવાની સમસ્યા બહુપદી સમયમાં ઉકેલી શકાય છે. અનન્ય લેબલ કવર ઉદાહરણનું મૂલ્ય એ અવરોધોનો અપૂર્ણાંક છે જે કોઈપણ સોંપણી દ્વારા સંતુષ્ટ કરી શકાય છે. સંતોષકારક ઉદાહરણો માટે, આ મૂલ્ય 1 છે અને તેને શોધવું સરળ છે. બીજી બાજુ, લગભગ પણ અસંતોષકારક રમતનું મૂલ્ય નક્કી કરવું ખૂબ જ મુશ્કેલ લાગે છે. અનન્ય રમત અનુમાન આ મુશ્કેલીને ઔપચારિક બનાવે છે. વધુ ઔપચારિક રીતે, અનન્ય અવરોધો સાથેની (સી, એસ)-ગેપ લેબલ-કવર સમસ્યા એ નીચેની વચન સમસ્યા છે (લાયસ, લોનો): લાયસ = {જીઃ કેટલીક સોંપણી ઓછામાં ઓછી જીમાં અવરોધોની સી-અપૂર્ણાંકને સંતોષે છે} લનો = {જીઃ દરેક સોંપણી જીમાં અવરોધોની મહત્તમ એસ-અપૂર્ણાંકને સંતોષે છે જ્યાં જી એ અનન્ય અવરોધો સાથે લેબલ કવર સમસ્યાનું ઉદાહરણ છે. અનન્ય રમત અનુમાન જણાવે છે કે ε, δ> 0 અચળાંકોની દરેક પૂરતી નાની જોડી માટે, એક અચળાંક k અસ્તિત્વમાં છે જેમ કે (1 − δ, ε)-ગેપ લેબલ-કવર સમસ્યા કદ k ના મૂળાક્ષર પર અનન્ય અવરોધો સાથે NP-હાર્ડ છે. આલેખને બદલે, લેબલ આવરણ સમસ્યાને રેખીય સમીકરણોની દ્રષ્ટિએ ઘડી શકાય છે. ઉદાહરણ તરીકે, ધારો કે આપણી પાસે પૂર્ણાંકો મોડ્યુલો 7 પર રેખીય સમીકરણોની પ્રણાલી છેઃ આ અનન્ય અવરોધો સાથે લેબલ કવર સમસ્યાનું એક ઉદાહરણ છે. ઉદાહરણ તરીકે, પ્રથમ સમીકરણ ક્રમચય (1,2) ને અનુરૂપ છે જ્યાં (1,2) (x1) = 2x2 મોડ્યુલો 7 છે. બે-પુરાવો પ્રૂફ સિસ્ટમ્સ એક અનન્ય રમત એ બે-પુરાવો વન-રાઉન્ડ (2P1R) રમતનો એક વિશેષ કેસ છે. બે-પુરાવોવાળી એક રાઉન્ડની રમતમાં બે ખેલાડીઓ (પુરાવો તરીકે પણ ઓળખાય છે) અને એક રેફરી હોય છે. રેફરી દરેક ખેલાડીને જાણીતા સંભાવના વિતરણમાંથી એક પ્રશ્ન મોકલે છે, અને દરેક ખેલાડીએ જવાબ મોકલવો પડે છે. જવાબો નિશ્ચિત કદના સમૂહમાંથી આવે છે. રમતને એક વિધેય દ્વારા નિર્દિષ્ટ કરવામાં આવે છે જે ખેલાડીઓને મોકલવામાં આવેલા પ્રશ્નો અને તેમના દ્વારા આપવામાં આવેલા જવાબો પર આધારિત હોય છે. ખેલાડીઓ અગાઉથી વ્યૂહરચના નક્કી કરી શકે છે, જો કે તેઓ રમત દરમિયાન એકબીજા સાથે વાતચીત કરી શકતા નથી. જો ભવિષ્યવાણી તેમના પ્રશ્નો અને તેમના જવાબોથી સંતુષ્ટ હોય તો ખેલાડીઓ જીતે છે. બે-પુરાવોવાળી એક-રાઉન્ડની રમતને એક અનન્ય રમત કહેવામાં આવે છે જો પ્રથમ ખેલાડી દ્વારા દરેક પ્રશ્ન અને દરેક જવાબ માટે, બીજા ખેલાડી દ્વારા બરાબર એક જવાબ હોય જે ખેલાડીઓ માટે જીતમાં પરિણમે છે, અને ઊલટું. રમતનું મૂલ્ય એ તમામ વ્યૂહરચનાઓ પર ખેલાડીઓ માટે જીતવાની મહત્તમ સંભાવના છે. અનન્ય રમત અનુમાન જણાવે છે કે ε, δ> 0 સ્થિરાંકોની દરેક પૂરતી નાની જોડી માટે, એક સ્થિરાંક k અસ્તિત્વમાં છે જેમ કે નીચેની વચન સમસ્યા (લાયસ, Lno) NP-સખત છેઃ લાયસ = {G: G નું મૂલ્ય ઓછામાં ઓછું 1 − δ} Lno = {G: G નું મૂલ્ય વધુમાં વધુ ε} છે જ્યાં G એક અનન્ય રમત છે જેના જવાબો કદ k ના સમૂહમાંથી આવે છે. વૈકલ્પિક રીતે, અનન્ય રમત અનુમાન NP માં સમસ્યાઓ માટે ચોક્કસ પ્રકારના સંભવિત રીતે ચકાસી શકાય તેવા પુરાવાના અસ્તિત્વને રજૂ કરે છે. એક અનોખી રમતને ક્વેરી જટિલતા 2 સાથે એક ખાસ પ્રકારના બિન-અનુકૂલનશીલ સંભવિત રીતે ચકાસી શકાય તેવા પુરાવા તરીકે જોઈ શકાય છે, જ્યાં ચકાસણીકર્તાના સંભવિત પ્રશ્નોની દરેક જોડી અને પ્રથમ ક્વેરીના દરેક સંભવિત જવાબ માટે, બીજી ક્વેરીનો બરાબર એક સંભવિત જવાબ હોય છે જે ચકાસણીકર્તાને સ્વીકારે છે, અને તેનાથી ઊલટું. અનન્ય રમત અનુમાન જણાવે છે કે સ્થિરાંકોની દરેક પૂરતી નાની જોડી માટે એક સ્થિરાંક હોય છે કે એન. પી. માં દરેક સમસ્યા સંપૂર્ણતા, મજબૂતી અને અવ્યવસ્થિત જટિલતા સાથે કદના મૂળાક્ષર પર સંભવિત રીતે ચકાસી શકાય તેવો પુરાવો ધરાવે છે જે એક અનન્ય રમત છે. સુસંગતતા અંદાજની કઠિનતાના સિદ્ધાંતમાં ચોક્કસ પ્રશ્નો પર પ્રગતિ કરવા માટે સુભાષ ખોટ દ્વારા 2002 માં અનન્ય રમત અનુમાન રજૂ કરવામાં આવ્યું હતું. અનન્ય રમતના અનુમાનનું સત્ય ઘણા જાણીતા અંદાજિત અલ્ગોરિધમ્સની શ્રેષ્ઠતા સૂચવે છે (એમ ધારી રહ્યા છીએ કે પી ≤ એન. પી.). ઉદાહરણ તરીકે, ગ્રાફમાં મહત્તમ કાપનો અંદાજ કાઢવા માટે ગોમેન્સ અને વિલિયમસનના અલ્ગોરિધમ દ્વારા પ્રાપ્ત અંદાજ ગુણોત્તર અનન્ય રમત અનુમાન અને પી ષ્ણ એન. પી. ધારીને કોઈપણ એડિટિવ અચળાંકની અંદર શ્રેષ્ઠ છે. અનન્ય રમત અનુમાન સૂચવે છે તે પરિણામોની સૂચિ નજીકના કોષ્ટકમાં નબળી ધારણા P ષ્ણ NP માટે અનુરૂપ શ્રેષ્ઠ પરિણામો સાથે દર્શાવવામાં આવી છે. એક અચળાંક અથવા તેનો અર્થ એ છે કે પરિણામ દરેક અચળાંક (સમસ્યાના કદના સંદર્ભમાં) માટે અનુક્રમે તેના કરતા વધારે અથવા ઓછું હોય છે. ચર્ચા અને વિકલ્પો હાલમાં, અનન્ય રમતના અનુમાનના સત્યને લઈને કોઈ સર્વસંમતિ નથી. અનુમાનના કેટલાક મજબૂત સ્વરૂપોને નકારી કાઢવામાં આવ્યા છે. અનુમાનનું એક અલગ સ્વરૂપ એવું માને છે કે જ્યારે અનન્ય રમતનું મૂલ્ય ઓછામાં ઓછું તે કેસથી અલગ હોય છે જ્યારે મૂલ્ય સૌથી વધુ હોય ત્યારે બહુપદી-સમયના અલ્ગોરિધમ્સ (પરંતુ કદાચ એન. પી.-હાર્ડ નહીં) માટે અશક્ય છે. અનુમાનનું આ સ્વરૂપ હજુ પણ અંદાજની કઠિનતામાં કાર્યક્રમો માટે ઉપયોગી થશે. જ્યાં સુધી P = NP ન હોય ત્યાં સુધી અનુમાનના ઉપરોક્ત ફોર્મ્યુલેશનમાં અચળાંક જરૂરી છે. જો વિશિષ્ટતાની જરૂરિયાતને દૂર કરવામાં આવે તો અનુરૂપ નિવેદન સમાંતર પુનરાવર્તન પ્રમેય દ્વારા સાચું હોવાનું જાણીતું છે, મારેક કાર્પિન્સ્કી અને વોરેન શુડીએ પણ અનન્ય રમત સમસ્યાના ગાઢ ઉદાહરણો માટે રેખીય સમય અંદાજ યોજનાઓ બનાવી છે. 2008 માં, પ્રસાદ રાઘવેન્દ્રએ બતાવ્યું છે કે જો અનન્ય રમત અનુમાન સાચું છે, તો પછી દરેક અવરોધ સંતોષ સમસ્યા માટે શ્રેષ્ઠ અંદાજ ગુણોત્તર ચોક્કસ સરળ અર્ધ-મર્યાદિત પ્રોગ્રામિંગ ઉદાહરણ દ્વારા આપવામાં આવે છે, જે ખાસ કરીને બહુપદીમાં છે. 2010માં, પ્રસાદ રાઘવેન્દ્ર અને ડેવિડ સ્ટીયુરરે ગેપ-સ્મોલ-સેટ વિસ્તરણ સમસ્યાને વ્યાખ્યાયિત કરી હતી અને અનુમાન લગાવ્યું હતું કે તે એન. પી.-હાર્ડ છે. આ અનુમાન અનન્ય રમત અનુમાન સૂચવે છે. તેનો ઉપયોગ સંપૂર્ણ દ્વિપક્ષી પેટા આલેખ શોધવા માટે અંદાજિત પરિણામોની મજબૂત કઠિનતા સાબિત કરવા માટે પણ કરવામાં આવે છે. 2010 માં, સંજીવ અરોરા, બોઆઝ બરાક અને ડેવિડ સ્ટીયુરરે અનન્ય રમત સમસ્યા માટે સબએક્સપોનેન્શિયલ ટાઇમ એપ્રોક્સીમેશન અલ્ગોરિધમ શોધી કાઢ્યું હતું. 2012 માં, એવું દર્શાવવામાં આવ્યું હતું કે ઓછામાં ઓછા મૂલ્ય સાથેના ઉદાહરણોથી મોટાભાગના મૂલ્ય સાથેના ઉદાહરણોને અલગ પાડવું એ એન. પી.-હાર્ડ છે. 2018 માં, કાગળોની શ્રેણી પછી, અનુમાનનું નબળું સંસ્કરણ, જેને 2-2 રમતો અનુમાન કહેવામાં આવે છે, તે સાબિત થયું હતું. ચોક્કસ અર્થમાં, આ મૂળ અનુમાનનો "અડધો ભાગ" સાબિત કરે છે. આ અનન્ય લેબલ કવર માટે સૌથી વધુ જાણીતું અંતર પણ સુધારે છેઃ ઓછામાં ઓછા મૂલ્ય ધરાવતા ઉદાહરણોથી મહત્તમ મૂલ્ય ધરાવતા ઉદાહરણોને અલગ પાડવાનું એન. પી.-મુશ્કેલ છે. નોંધો સંદર્ભો. 2002 કોમ્પ્યુટિંગ એપ્રોક્સિમેશન એલ્ગોરિધમ્સ કોમ્પ્યુટેશનલ કોમ્પ્લેક્સિટી થિયરી કોમ્પ્યુટેશનલ હાર્ડનેસ ધારણાઓ કોમ્પ્યુટર વિજ્ઞાનમાં વણઉકેલાયેલી સમસ્યાઓ અનુમાન