Finite promise games and greedy clique sequences
મર્યાદિત વચન રમતો એ 2009 માં અમેરિકન ગણિતશાસ્ત્રી હાર્વે ફ્રીડમેન દ્વારા વિકસાવવામાં આવેલી ગાણિતિક રમતોનો સંગ્રહ છે, જેનો ઉપયોગ ઝડપથી વિકસતા કાર્યોના કુટુંબને વિકસાવવા માટે થાય છે. લોભી જૂથ ક્રમ એ આલેખ સિદ્ધાંતની વિભાવના છે, જે 2010માં ફ્રીડમેન દ્વારા પણ વિકસાવવામાં આવી હતી, જેનો ઉપયોગ ઝડપથી વિકસતા કાર્યો વિકસાવવા માટે થાય છે, અને. ઝેડએફસી પ્લસના સિદ્ધાંતને રજૂ કરે છે, દરેક માટે, "એક મજબૂત-માહલો કાર્ડિનલ છે", અને ઝેડએફસી પ્લસના સિદ્ધાંતને રજૂ કરે છે "દરેક માટે, એક મજબૂત-માહલો કાર્ડિનલ છે". ઝેડએફસી પ્લસના સિદ્ધાંતને રજૂ કરે છે, દરેક માટે, "ત્યાં એક-સ્થિર રેમ્સે કાર્ડિનલ છે", અને ઝેડએફસી પ્લસના સિદ્ધાંતને રજૂ કરે છે "દરેક માટે, એક મજબૂત-સ્થિર રેમ્સે કાર્ડિનલ છે". ઝેડએફસી પ્લસના સિદ્ધાંતને રજૂ કરે છે, દરેક માટે, "એક-વિશાળ કાર્ડિનલ છે", અને ઝેડએફસી પ્લસના સિદ્ધાંતને રજૂ કરે છે "દરેક માટે, એક મજબૂત-વિશાળ કાર્ડિનલ છે". મર્યાદિત વચન રમતો દરેક રમત મર્યાદિત છે, લંબાઈમાં પૂર્વનિર્ધારિત છે, અને તેમાં બે ખેલાડીઓ (એલિસ અને બોબ) છે. દરેક વળાંક પર, એલિસ એક પૂર્ણાંક અથવા સંખ્યાબંધ પૂર્ણાંકો (એક પ્રસ્તાવ) પસંદ કરે છે અને બોબે તેની ભાવિ સંભવિત ચાલને મર્યાદિત કરતા બે પ્રકારના વચનોમાંથી એક વચન આપવું પડે છે. તમામ રમતોમાં, બોબ ત્યારે જ જીતે છે જ્યારે બોબ તેના તમામ વચનો પાળશે. મર્યાદિત પીસવાઇઝ રેખીય નકલ/ઇન્વર્ટ રમતો અહીં, પૂર્ણાંકોનો સમૂહ છે, અને બિન-નકારાત્મક પૂર્ણાંકોનો સમૂહ છે. અહીં, બધા અક્ષરો પૂર્ણાંકોનું પ્રતિનિધિત્વ કરે છે. આપણે કહીએ છીએ કે નકશો પીસવાઇઝ રેખીય છે જો તેને મર્યાદિત રીતે ઘણા ટુકડાઓ પર પૂર્ણાંક ગુણાંક સાથે વિવિધ એફાઇન કાર્યો દ્વારા વ્યાખ્યાયિત કરી શકાય, જ્યાં દરેક ભાગને પૂર્ણાંક ગુણાંક સાથે રેખીય અસમાનતાઓના મર્યાદિત સમૂહ દ્વારા વ્યાખ્યાયિત કરવામાં આવે છે. કેટલાક પીસવાઇઝ રેખીય નકશા માટે, નું-ઇન્વર્ઝન એવું છે. પછી આપણે બિન-શૂન્ય માટે રમતને વ્યાખ્યાયિત કરીએ છીએ. તેમાં રાઉન્ડ હોય છે, અને એલિસ અને બોબ વચ્ચે વારાફરતી હોય છે. રમતના દરેક તબક્કે, એલિસે રમવું જરૂરી છે, જેને તેણીની રજૂઆત કહેવામાં આવે છે, જે કાં તો સ્વરૂપનું છે અથવા, જ્યાં અને પૂર્ણાંકો છે જે અગાઉ બોબ દ્વારા રમવામાં આવતા હતા. પછી બોબને ક્યાં તોઃ સ્વીકારવું જરૂરી છે, આમ રમવું અને વચન આપવું કે બોબ દ્વારા ભજવવામાં આવેલા પૂર્ણાંકોમાં કોઈ-વ્યુત્ક્રમ નહીં હોય. આ વચન રમતમાં ભૂતકાળ, વર્તમાન અને ભવિષ્યની તમામ રમતો પર લાગુ પડે છે. નકારી કાઢો, આમ બોબ દ્વારા ક્યારેય ભજવવામાં ન આવે તેવું-ઇન્વર્ઝન અને આશાસ્પદ વગાડો. RCA0 માં, તે સાબિત કરી શકાય છે કે બોબ હંમેશા કોઈપણ રમત માટે જીતવાની વ્યૂહરચના ધરાવે છે. આ રમત એક સંશોધિત સંસ્કરણ છે જ્યાં બોબને એલિસની તમામ ફેક્ટોરિયલ ઓફર સ્વીકારવાની ફરજ પાડવામાં આવે છે. બોબ પાસે હંમેશાં પૂરતા પ્રમાણમાં મોટા માટે જીતવાની વ્યૂહરચના હોય છે, જો કે આ કોઈ પણ સુસંગત ભાગમાં સાબિત કરી શકાતું નથી, અને માત્ર. કાર્ય એ સૌથી નાનું છે કે બોબ આવા કોઈપણ માટે જીતી શકે છે અને તે તેના કરતા વધારે અથવા સમાન હોય છે અને નીચેના તમામ મૂલ્યો તેના કરતા ઓછા હોય છેઃ (નું ક્ષેત્ર) અસમાનતાના ગુણાંકના નિરપેક્ષ મૂલ્યોના ટુકડાઓની સંખ્યા મર્યાદિત બહુપદી નકલ/ઊંધી રમતોમાં સંલગ્ન કાર્યોના ગુણાંકના નિરપેક્ષ મૂલ્યોમાં. એક વિશેષ-વ્યુત્ક્રમ એટ ઇનમાં તે હોય છે. હવે આપણે બિન-શૂન્ય માટે રમતને વ્યાખ્યાયિત કરીએ છીએ, જ્યાં પૂર્ણાંક ગુણાંક સાથેની બહુપદીઓ છે. તેમાં એલિસ અને બોબના વારાફરતી નાટકોનો સમાવેશ થાય છે. રમતના દરેક તબક્કે, એલિસે સ્વરૂપમાં રમવું જરૂરી છે, અથવા, જ્યાં બોબ દ્વારા અગાઉ રમાયેલ પૂર્ણાંકોનું એક-ટુપલ છે. પછી બોબને ક્યાં તોઃ સ્વીકારવું જરૂરી છે, આમ રમવું અને વચન આપવું કે બોબ દ્વારા ભજવવામાં આવેલા પૂર્ણાંકોમાં કોઈ વિશેષ-અથવા-વ્યુત્ક્રમ નહીં હોય. આ વચન રમતમાં ભૂતકાળ, વર્તમાન અને ભવિષ્યની તમામ રમતો પર લાગુ પડે છે. નકારી કાઢો, જેથી બોબ દ્વારા ક્યારેય ભજવવામાં ન આવે તેવું વિશેષ-અથવા-રૂપાંતર અને આશાસ્પદ વગાડો. ચાલો પૂર્ણાંક ગુણાંક સાથેની બહુપદીઓ. RCA0 માં, તે સાબિત કરી શકાય છે કે બોબ હંમેશા કોઈપણ રમત માટે જીતવાની વ્યૂહરચના ધરાવે છે. જો પૂરતા પ્રમાણમાં મોટા હોય તો બોબ જીતે છે, જ્યાં બોબને એલિસ દ્વારા ઓફર કરાયેલા તમામ ડબલ ફેક્ટોરિયલ્સ સ્વીકારવાની ફરજ પડે છે. જો કે, ફરી એકવાર, આ માત્ર અને માત્રના કોઈપણ સુસંગત ભાગમાં સાબિત કરી શકાતું નથી. ફંક્શન એ સૌથી નાનું છે કે બોબ આવા કોઈપણ માટે જીતી શકે છે અને તે તેનાથી મોટા અથવા સમાન હોય છે અને નીચેના તમામ મૂલ્યો તેના કરતા ઓછા હોય છેઃ (બહુપદીઓનું ક્ષેત્ર છે) ગુણાંકની ડિગ્રી અને નિરપેક્ષ મૂલ્યો અને મર્યાદિત રેખીય નકલ/ઇન્વર્ટ રમતો. બિન-શૂન્ય પૂર્ણાંકો માટે અને, અમે રમતને વ્યાખ્યાયિત કરીએ છીએ જેમાં એલિસ અને બોબ વચ્ચે વૈકલ્પિક રાઉન્ડનો સમાવેશ થાય છે. રમતના દરેક તબક્કે, એલિસે ફોર્મનો પૂર્ણાંક રમવો જરૂરી છે અથવા, જ્યાં અગાઉ બોબ દ્વારા ભજવવામાં આવતા પૂર્ણાંકો છે. પછી બોબને ક્યાં તો સ્વીકારવું જરૂરી છેઃ સ્વીકારો, આમ રમવું અને વચન આપવું કે જેને આ રીતે લખી શકાતું નથી, જ્યાં કેટલાકની વધારાની સમકક્ષ હોય છે, અને વિવિધ સમયે બોબ દ્વારા ભજવવામાં આવતા પૂર્ણાંકો હોય છે. નકારી કાઢો, આમ રમવું, ક્યાં અને વધારાની રીતે કેટલાકની સમકક્ષ છે, અને વચન આપે છે જે બોબ દ્વારા ક્યારેય ભજવવામાં આવતું નથી. જવા દો. RCA0 માં, તે સાબિત કરી શકાય છે કે બોબ હંમેશા કોઈપણ રમત માટે જીતવાની વ્યૂહરચના ધરાવે છે. જવા દો. જો પૂરતું મોટું હોય, તો બોબ જીતે છે, જ્યાં બોબ એલિસ દ્વારા ઓફર કરાયેલા તમામ ફેક્ટોરિયલ્સ સ્વીકારે છે. જો કે, ફરી એકવાર, આ માત્ર અને માત્રના કોઈપણ સુસંગત ભાગમાં સાબિત કરી શકાતું નથી. કાર્ય એ સૌથી નાનું છે કે બોબ એવા કોઈપણ માટે જીતી શકે છે જે તેનાથી વધારે અથવા સમાન હોય, હકારાત્મક હોય અને નીચે આપેલા તમામ મૂલ્યો તેના કરતા ઓછા હોયઃ કાર્યોમાં દરેક વેક્ટરના ઘટકોની સંખ્યા ફ્રીડમેન દ્વારા બતાવ્યા પ્રમાણે, ત્રણ કાર્યો, અને અત્યંત ઝડપથી વિકસતા હોય છે, આખરે કોઈપણ કાર્ય પર પ્રભુત્વ ધરાવે છે જે કોઈપણ સુસંગત ભાગમાં પુનરાવર્તિત છે (આમાંથી એક ઝેડએફસી છે), પરંતુ તે ગણતરીપાત્ર અને સાબિત કુલ છે. લોભી જૂથ ક્રમ તર્કસંગત સંખ્યાઓના તમામ ટપલ્સના સમૂહને સૂચવે છે. આપણે અનુક્રમણિકાને ટપલ્સ (1 થી શરૂ કરીને) અને કોણ કૌંસમાં સૂચવવા માટે સબસ્ક્રિપ્ટનો ઉપયોગ કરીએ છીએ, જે ટપલ્સના સંયોજનને સૂચવે છે, દા. ત. . આપેલ છે, આપણે તેની ઉપરની પાળીને વ્યાખ્યાયિત કરીએ છીએ, જે તેના તમામ બિન-નકારાત્મક ઘટકોમાં 1 ઉમેરવાનું પરિણામ હોવાનું સૂચવવામાં આવે છે. આપેલ, આપણે તે અને કહીએ છીએ. જો અને માત્ર જો તેમની લંબાઈ સમાન હોય અને બધા માટે, આઇએફએફ હોય તો તેમને ઓર્ડર સમકક્ષ કહેવામાં આવે છે. સમૂહ એ તમામ ક્રમ સમકક્ષ અને, માટે ક્રમ અપરિવર્તનશીલ iff છે. ચાલો શિરોબિંદુઓ સાથેનો આલેખ બનીએ. ચાલો સમૂહને નીચે પ્રમાણે વ્યાખ્યાયિત કરીએઃ અંદરની દરેક ધાર માટે, તેમનું સંયોજન અંદર છે. પછી જો ક્રમ અપરિવર્તનશીલ હોય, તો આપણે કહીએ છીએ કે તે ક્રમ અપરિવર્તનશીલ છે. જ્યારે ક્રમ અપરિવર્તનશીલ હોય છે, ત્યારે તેની અનંત ધાર હોય છે. આપણને આપવામાં આવે છે, અને શિરોબિંદુઓ સાથે એક સરળ આલેખ (અથવા ઉપલા પાળીના લોભી ડાઉન ક્લીક સિક્વન્સના કિસ્સામાં ડિગ્રાફ) આપવામાં આવે છે. આપણે ક્રમને નોન એમ્પ્ટી ટુપલ તરીકે વ્યાખ્યાયિત કરીએ છીએ. આ ટુપલ નથી પણ ટુપલની ટુપલ છે. જ્યારે, એક ઉચ્ચ પાળી લોભી જૂથ ક્રમ કહેવાય છે જો તે નીચેની બાબતોને સંતોષેઃ તેમાં માત્ર શૂન્ય હોય છે. જો આપણે અનંત ક્રમને મંજૂરી આપીએ તો તે પૂર્ણાંક હોવો જોઈએ, અથવા હકારાત્મક પૂર્ણાંક હોવો જોઈએ. અને જવા દો. પછી, અને ની ધાર નથી. એક જૂથ છે, એટલે કે. તેમાં શિરોબિંદુઓની દરેક જોડી ધાર તરીકે હોય છે. જ્યારે, લોભી જૂથ ક્રમમાં ઉપલા પાળી તરીકે કહેવામાં આવે છે જો તે નીચેની બાબતોને સંતોષે છેઃ તેમાં માત્ર શૂન્ય હોય છે. જો આપણે અનંત ક્રમને મંજૂરી આપીએ તો તે પૂર્ણાંક હોવો જોઈએ, અથવા હકારાત્મક પૂર્ણાંક હોવો જોઈએ. અને જવા દો. પછી, અથવા અને એક ધાર નથી; અને. એક ડાઉન ક્લીક છે, એટલે કે. બધા માટે અને, એક ધાર છે. જ્યારે, લોભી જૂથ ક્રમમાં એક આત્યંતિક ઉપલા પાળી તરીકે કહેવામાં આવે છે જો તે નીચેની બાબતોને સંતોષે છેઃ તેમાં માત્ર શૂન્ય હોય છે. જો આપણે અનંત ક્રમને મંજૂરી આપીએ તો તે પૂર્ણાંક હોવો જોઈએ, અથવા હકારાત્મક પૂર્ણાંક હોવો જોઈએ. અને જવા દો. પછી, અથવા અને એક ધાર નથી; અને. જો એમ હોય તો. જો એમ હોય તો. જો અને, તો પછી એક ડાઉન ક્લીક છે ધ થ્રેડ ઓફ એક અનુગામી છે જે પ્રેરક રીતે વ્યાખ્યાયિત થયેલ છેઃ એક થ્રેડ આપવામાં આવે તો, આપણે કહીએ છીએ કે તે ઓપન છે જો. આનો ઉપયોગ કરીને હાર્વે ફ્રીડમેને ત્રણ ખૂબ જ શક્તિશાળી કાર્યોને વ્યાખ્યાયિત કર્યાઃ શું તે સૌથી નાનું છે કે દરેક સરળ, ક્રમમાં અપરિવર્તનશીલ આલેખમાં ખુલ્લી દોરી સાથે મહત્તમ લંબાઈમાં ઉપલા પાળીનો લોભી જૂથ ક્રમ હોય છે. તે સૌથી નાનું છે કે દરેક ક્રમના અપરિવર્તનશીલ ડિગ્રાફમાં ખુલ્લી દોરી સાથે મહત્તમ લંબાઈમાં લોભી નીચે જૂથ ક્રમ હોય છે. તે સૌથી નાનું છે કે દરેક ક્રમના અપરિવર્તનશીલ ડિગ્રાફમાં ખુલ્લા થ્રેડ સાથે મહત્તમ લંબાઈમાં અત્યંત ઉપલા પાળીનો લોભી નીચેનો ક્લીક ક્રમ હોય છે. અને આખરે સાબિત રીતે પુનરાવર્તિત તમામ કાર્યો પર પ્રભુત્વ ધરાવે છે, પરંતુ પોતે સાબિત રીતે પુનરાવર્તિત છે. આખરે સાબિત રીતે પુનરાવર્તિત તમામ કાર્યો પર પ્રભુત્વ ધરાવે છે, પરંતુ પોતે જ સાબિત રીતે કુલ છે. સંદર્ભો ગાણિતિક રમતો ગાણિતિક ખ્યાલો