Generalized geography
કોમ્પ્યુટેશનલ કોમ્પ્લેક્સિટી થિયરીમાં, સામાન્યીકૃત ભૂગોળ એ એક જાણીતી PSPACE-પૂર્ણ સમસ્યા છે. ભૂગોળ એ બાળકોની રમત છે, જ્યાં ખેલાડીઓ વારાફરતી વિશ્વમાં ગમે ત્યાંથી શહેરોનું નામકરણ કરે છે. પસંદ કરેલ દરેક શહેર એ જ અક્ષરથી શરૂ થવું જોઈએ જે અગાઉના શહેરનું નામ સમાપ્ત કરે છે. પુનરાવર્તનની મંજૂરી નથી. રમત મનસ્વી શરૂઆતના શહેરથી શરૂ થાય છે અને જ્યારે કોઈ ખેલાડી હારી જાય છે ત્યારે સમાપ્ત થાય છે કારણ કે તે ચાલુ રાખવામાં અસમર્થ હોય છે. ગ્રાફ મોડેલ રમતની કલ્પના કરવા માટે, એક નિર્દેશિત ગ્રાફ બનાવી શકાય છે, જેના નોડ્સ વિશ્વના દરેક શહેરો છે. નોડ N1 થી નોડ N2 માં તીર ઉમેરવામાં આવે છે જો અને માત્ર ત્યારે જ જ્યારે શહેરનું લેબલિંગ N2 એ અક્ષરથી શરૂ થાય છે જે શહેરનું લેબલિંગ નોડ N1 નું નામ સમાપ્ત કરે છે. બીજા શબ્દોમાં કહીએ તો, જો રમતના નિયમો અનુસાર પ્રથમ તીર બીજા તરફ દોરી શકે તો આપણે એક શહેરમાંથી બીજા શહેરમાં તીર દોરીએ છીએ. નિર્દેશિત આલેખમાં દરેક વૈકલ્પિક ધાર દરેક ખેલાડી (બે ખેલાડીઓની રમત માટે) ને અનુરૂપ હોય છે. જે પ્રથમ ખેલાડી રસ્તો લંબાવવામાં અસમર્થ હોય તે હારી જાય છે. રમતનું ચિત્ર (મિશિગનના કેટલાક શહેરો ધરાવતું) નીચેની આકૃતિમાં દર્શાવવામાં આવ્યું છે. સામાન્યીકૃત ભૂગોળ (જી. જી.) રમતમાં, આપણે શહેરના નામોના આલેખને મનસ્વી નિર્દેશિત આલેખ સાથે બદલીએ છીએ. નીચેનો આલેખ સામાન્ય ભૂગોળ રમતનું ઉદાહરણ છે. રમત રમવી આપણે પી 1 ને પહેલા આગળ વધતા ખેલાડી તરીકે અને પી 2 ને બીજા તરફ આગળ વધતા ખેલાડી તરીકે વ્યાખ્યાયિત કરીએ છીએ અને નોડ્સને એન 1 થી એન એન નામ આપીએ છીએ. ઉપરોક્ત આંકડામાં, પી1ની જીતવાની વ્યૂહરચના નીચે મુજબ છેઃ એન1 માત્ર નોડ્સ એન2 અને એન3ને જ નિર્દેશ કરે છે. આમ P1 ની પ્રથમ ચાલ આ બે પસંદગીઓમાંથી એક હોવી જોઈએ. P1 N2 પસંદ કરે છે (જો P1 N3 પસંદ કરે છે, તો P2 N9 પસંદ કરશે કારણ કે તે એકમાત્ર વિકલ્પ છે અને P1 ગુમાવશે). આગળ P2 N4 પસંદ કરે છે કારણ કે તે એકમાત્ર બાકીની પસંદગી છે. P1 હવે N5 પસંદ કરે છે અને P2 પછીથી N3 અથવા N7 પસંદ કરે છે. પી 2 ની પસંદગીને ધ્યાનમાં લીધા વિના, પી 1 એન 9 પસંદ કરે છે અને પી 2 પાસે કોઈ બાકી પસંદગીઓ નથી અને રમત ગુમાવે છે. કોમ્પ્યુટેશનલ જટિલતા સામાન્ય ભૂગોળ રમતમાં કયા ખેલાડીની જીતવાની વ્યૂહરચના છે તે નક્કી કરવાની સમસ્યા PSPACE-પૂર્ણ છે. સામાન્યીકૃત ભૂગોળ પી. એસ. પી. એ. સી. ઈ. માં છે ધારો કે જી. જી. = {75જી, બી. જી. એલ. એ. | પી. 1 પાસે ગ્રાફ જી પર રમાયેલી સામાન્યીકૃત ભૂગોળ રમત માટે જીતવાની વ્યૂહરચના છે જે નોડ બી} થી શરૂ થાય છે; તે બતાવવા માટે કે જી. જી. bul. પી. એસ. પી. એ. સી. ઈ., આપણે બહુપદી-જગ્યા પુનરાવર્તિત અલ્ગોરિધમ રજૂ કરીએ છીએ જે નક્કી કરે છે કે કયા ખેલાડીની જીતની વ્યૂહરચના છે. GG, 75G, nstartω નું ઉદાહરણ આપવામાં આવે છે જ્યાં G એ નિર્દેશિત આલેખ છે અને nstart એ નિયુક્ત પ્રારંભ નોડ છે, એલ્ગોરિધમ M નીચે પ્રમાણે આગળ વધે છેઃ M (75G, nstartω) પરઃ નોડ nstart ની આઉટ-ડિગ્રીને માપો. જો આ ડિગ્રી 0 હોય, તો પાછા ફરો, કારણ કે પ્રથમ ખેલાડી માટે કોઈ ચાલ ઉપલબ્ધ નથી. nstart થી એક ધાર દ્વારા પહોંચી શકાય તેવા તમામ ગાંઠોની સૂચિ બનાવોઃ n1, n2,., ni. જી1 બનાવવા માટે જીમાંથી એનસ્ટાર્ટ અને તેની સાથે જોડાયેલી તમામ ધારને દૂર કરો. સૂચિ n1,., ni માં દરેક નોડ nj માટે, M (75G1, nj આહાત) પર કૉલ કરો. જો આ બધા કૉલ્સ રીટર્ન સ્વીકારે છે, તો પછી P1 ગમે તે નિર્ણય લે, P2 પાસે જીતવાની વ્યૂહરચના છે, તેથી રીટર્ન નકારી કાઢે છે. નહિંતર (જો કોઈ એક કૉલ રીટર્ન નકારે તો) પી1 પાસે એક વિકલ્પ છે જે પી2 માટે કોઈપણ સફળ વ્યૂહરચનાને નકારી કાઢશે, તેથી રીટર્ન સ્વીકારે છે. અલ્ગોરિધમ M સ્પષ્ટપણે GG નક્કી કરે છે. તે પી. એસ. પી. એ. સી. ઈ. માં છે કારણ કે એકમાત્ર બિન-સ્પષ્ટ બહુપદી કાર્યસ્થાનનો વપરાશ રિકર્શન સ્ટેકમાં થાય છે. રિકર્શન સ્ટૅક દ્વારા વપરાતી જગ્યા બહુપદી છે કારણ કે રિકર્શનનું દરેક સ્તર સ્ટેકમાં એક જ નોડ ઉમેરે છે, અને ત્યાં મોટાભાગના n સ્તરો હોય છે, જ્યાં n એ G માં ગાંઠોની સંખ્યા છે. આ અનિવાર્યપણે ઊંડાઈ-પ્રથમ શોધની સમકક્ષ છે. સામાન્યીકૃત ભૂગોળ સ્પેસ-હાર્ડ છે નીચેનો પુરાવો ડેવિડ લિક્ટનસ્ટીન અને માઇકલ સિપ્સરને કારણે છે. GGની PSPACE-કઠોરતા સ્થાપિત કરવા માટે, આપણે બહુપદી સમય (P) માં FORMULA-GAME સમસ્યા (જે PSPACE-કઠોર તરીકે ઓળખાય છે) ને GGમાં ઘટાડી શકીએ છીએ. ટૂંકમાં કહીએ તો, ફોર્મ્યુલા-ગેમ સમસ્યાના ઉદાહરણમાં માત્રાત્મક બુલિયન સૂત્ર φ = HE x1  કાય x2 HE x3. Qxk (si) નો સમાવેશ થાય છે જ્યાં Q એ કાં તો HE અથવા  કાય છે. આ રમત બે ખેલાડીઓ, પા અને પે દ્વારા રમવામાં આવે છે, જેઓ ક્રમિક xi માટે વૈકલ્પિક પસંદગીના મૂલ્યો ધરાવે છે. જો સૂત્ર si સાચું પડે તો પે રમત જીતે છે, અને જો si ખોટું થાય તો પા જીતે છે. સૂત્ર si એ સંયોજી સામાન્ય સ્વરૂપમાં હોવાનું માનવામાં આવે છે. આ સાબિતીમાં, આપણે ધારીએ છીએ કે ક્વોન્ટિફાયર સૂચિ સરળતા માટે અસ્તિત્વની લાયકાત, HE સાથે શરૂ થાય છે અને સમાપ્ત થાય છે. નોંધ લો કે કોઈપણ અભિવ્યક્તિને ડમી ચલો ઉમેરીને આ સ્વરૂપમાં રૂપાંતરિત કરી શકાય છે જે si માં દેખાતા નથી. ઉપર બતાવ્યા પ્રમાણે ગ્રાફ Gનું નિર્માણ કરીને, આપણે બતાવીશું કે ફોર્મ્યુલા-ગેમનું કોઈપણ ઉદાહરણ સામાન્યીકૃત ભૂગોળના ઉદાહરણમાં ઘટાડી શકાય છે, જ્યાં P1 માટે શ્રેષ્ઠ વ્યૂહરચના એ પેની સમકક્ષ છે, અને P2 માટે શ્રેષ્ઠ વ્યૂહરચના એ પા ની સમકક્ષ છે. નોડ્સની ડાબી ઊભી સાંકળ ફોર્મુલા-ગેમમાં ચલ માટે મૂલ્યો પસંદ કરવાની પ્રક્રિયાની નકલ કરવા માટે રચાયેલ છે. હીરાનું દરેક માળખું માત્રાત્મક ચલને અનુરૂપ હોય છે. ખેલાડીઓ દરેક શાખા નોડ પર વારાફરતી પાથ નક્કી કરે છે. કારણ કે આપણે ધાર્યું હતું કે પ્રથમ પરિમાણ અસ્તિત્વમાં હશે, P1 પહેલા જાય છે, જો x1 સાચું હોય તો ડાબી નોડ પસંદ કરે છે અને જો x1 ખોટું હોય તો જમણી નોડ પસંદ કરે છે. દરેક ખેલાડીએ પછી બળજબરીથી વળાંક લેવો જોઈએ, અને પછી P2 એ x2 માટે મૂલ્ય પસંદ કરે છે. આ વૈકલ્પિક સોંપણીઓ ડાબી બાજુ નીચે ચાલુ રહે છે. બંને ખેલાડીઓ તમામ હીરામાંથી પસાર થયા પછી, તે ફરીથી પી 1 નો વારો છે, કારણ કે અમે ધાર્યું હતું કે છેલ્લું પરિમાણ અસ્તિત્વમાં છે. ગ્રાફની જમણી બાજુના માર્ગને અનુસરવા સિવાય P1 પાસે કોઈ વિકલ્પ નથી. પછી પી 2 નો ચાલવાનો વારો છે. જ્યારે રમત ગ્રાફની જમણી બાજુએ પહોંચે છે, ત્યારે તે ફોર્મ્યુલા ગેમમાં રમતના અંત જેવું જ હોય છે. યાદ કરો કે ફોર્મ્યુલાની રમતમાં, જો ± સાચું હોય તો પે જીતે છે, જ્યારે ± ખોટો હોય તો પા જીતે છે. ગ્રાફની જમણી બાજુ ખાતરી આપે છે કે જો પી જીતે તો જ પી 1 જીતે છે, અને જો પી જીતે તો જ પી 2 જીતે છે. પહેલા આપણે બતાવીએ છીએ કે જ્યારે પી જીતે છે ત્યારે પી2 હંમેશા જીતે છે. જો પા જીતે છે, તો si ખોટો છે. જો si ખોટો હોય, તો એક અસંતોષકારક કલમ અસ્તિત્વમાં છે. પી2 જીતવા માટે અસંતોષકારક કલમ પસંદ કરશે. પછી જ્યારે પી 1 નો વારો આવે ત્યારે તેણે પી 2 દ્વારા પસંદ કરેલા તે કલમમાં શાબ્દિક પસંદ કરવું આવશ્યક છે. કલમમાંના તમામ અક્ષરો ખોટા હોવાથી, તેઓ ડાબી ઊભી સાંકળમાં અગાઉ મુલાકાત લેવાયેલા નોડ્સ સાથે જોડાતા નથી. આ P2 ને ડાબી સાંકળના હીરામાં અનુરૂપ નોડ સાથેના જોડાણને અનુસરવા અને તેને પસંદ કરવાની મંજૂરી આપે છે. જો કે, P1 હવે કોઈપણ અડીને આવેલા નોડ્સ અને લોસને પસંદ કરવામાં અસમર્થ છે. હવે આપણે બતાવીએ છીએ કે જ્યારે પી જીતે છે ત્યારે પી1 હંમેશા જીતે છે. જો પે જીતે છે, તો si સાચું છે. જો si સાચું હોય, તો આલેખની જમણી બાજુના દરેક કલમમાં સાચું શાબ્દિક હોય છે. પી2 કોઈપણ કલમ પસંદ કરી શકે છે. પછી P1 સાચું હોય તે શાબ્દિક પસંદ કરે છે. અને કારણ કે તે સાચું છે, ડાબી ઊભી નોડમાં તેની અડીને આવેલ નોડ પહેલેથી જ પસંદ કરવામાં આવ્યો છે, તેથી P2 પાસે બનાવવા અને ગુમાવવા માટે કોઈ ચાલ નથી. સમતલીય સામાન્યીકૃત ભૂગોળ એ PSPACE-પૂર્ણ સામાન્યીકૃત ભૂગોળ છે, જ્યારે સમતલીય આલેખ પર રમાય છે ત્યારે પણ તે PSPACE-પૂર્ણ છે. નીચેનો પુરાવો 3 ના પ્રમેયમાંથી છે. પ્લાનર GG એ GG નો એક ખાસ કેસ છે, અને GG એ PSPACE માં છે, તેથી પ્લાનર GG એ PSPACE માં છે. તે બતાવવાનું બાકી છે કે પ્લાનર જી. જી. સ્પેસ-હાર્ડ છે. મનસ્વી આલેખને સમતલીય આલેખમાં કેવી રીતે રૂપાંતરિત કરવો તે દર્શાવીને આ સાબિત કરી શકાય છે, જેમ કે આ આલેખ પર રમાયેલી જી. જી. ની રમતનું મૂળ આલેખ જેવું જ પરિણામ હશે. તે કરવા માટે, માત્ર મૂળ ગ્રાફના તમામ ધાર ક્રોસિંગને દૂર કરવું જરૂરી છે. અમે આલેખ એવી રીતે દોરીએ છીએ કે કોઈ પણ ત્રણ ધાર એક બિંદુ પર એકબીજાને છેદતી નથી, અને એક જ રમતમાં બંનેને પાર કરવાની કોઈ જોડીનો ઉપયોગ કરી શકાતો નથી. આ સામાન્ય રીતે શક્ય નથી, પરંતુ ફોર્મ્યુલા-ગેમના ઉદાહરણથી બનેલા આલેખ માટે હંમેશા શક્ય છે; ઉદાહરણ તરીકે આપણી પાસે ક્રોસિંગમાં સામેલ કલમ શિરોબિંદુઓની માત્ર ધાર હોઈ શકે છે. હવે આપણે દરેક ક્રોસિંગને આ રચના સાથે બદલીએ છીએઃ પરિણામ એક સમતલીય આલેખ છે, અને તે જ ખેલાડી મૂળ આલેખની જેમ જીત માટે દબાણ કરી શકે છેઃ જો કોઈ ખેલાડી રૂપાંતરિત રમતમાં V થી "ઉપર" જવાનું પસંદ કરે છે, તો પછી બંને ખેલાડીઓએ "ઉપર" થી W તરફ આગળ વધવાનું ચાલુ રાખવું જોઈએ અથવા તરત જ હારવું પડશે. તેથી રૂપાંતરિત રમતમાં V થી "ઉપર" ખસેડવું એ મૂળ રમતમાં ચાલ V → W નું અનુકરણ કરે છે. જો V → W એ જીતવાની ચાલ છે, તો પછી રૂપાંતરિત રમતમાં V થી "ઉપર" જવું પણ એક જીતવાની ચાલ છે, અને તેનાથી ઊલટું. આમ, રૂપાંતરિત આલેખ પર રમાયેલી જી. જી. ની રમતનું મૂળ આલેખ જેવું જ પરિણામ હશે. આ પરિવર્તનમાં સમય લાગે છે જે મૂળ આલેખમાં ધાર આંતરછેદોની સંખ્યાનો સતત ગુણાંક છે, આમ તે બહુપદી સમય લે છે. આમ સમતલીય GG એ PSPACE-પૂર્ણ છે. 3 કરતા વધુ ડિગ્રીના શિરોબિંદુઓને મહત્તમ 3 ડિગ્રી સાથે શિરોબિંદુઓની સાંકળ સાથે બદલીને, મહત્તમ ડિગ્રી 3 GG સાથેનો સમતલીય દ્વિપક્ષી આલેખ, મહત્તમ ડિગ્રી 3 સાથે સમતલીય દ્વિપક્ષી આલેખ પર રમવામાં આવે છે, તે હજુ પણ PSPACE-પૂર્ણ છે. પુરાવો અંદર છે. અને નીચેની રચનાનો ઉપયોગ કરે છેઃ જો એક ખેલાડી આ રચનાના કોઈપણ પ્રવેશદ્વારનો ઉપયોગ કરે છે, તો બીજો ખેલાડી પસંદ કરે છે કે કઈ બહાર નીકળવાનો ઉપયોગ કરવામાં આવશે. ઉપરાંત બાંધકામ માત્ર એક જ વાર પસાર કરી શકાય છે, કારણ કે કેન્દ્રિય શિરોબિંદુની હંમેશા મુલાકાત લેવામાં આવે છે. તેથી આ રચના મૂળ શિરોબિંદુની સમકક્ષ છે. ધાર ભૂગોળ જી. જી. ના એક પ્રકારને ધાર ભૂગોળ કહેવામાં આવે છે, જ્યાં દરેક ચાલ પછી, ખેલાડી જે ધારમાંથી પસાર થયો હતો તે ભૂંસી નાખવામાં આવે છે. આ મૂળ જી. જી. થી વિપરીત છે, જ્યાં દરેક ચાલ પછી, ખેલાડી જે શિરોબિંદુ પર રહેતો હતો તે ભૂંસી નાખવામાં આવે છે. આ દ્રષ્ટિકોણમાં, મૂળ જી. જી. ને વર્ટેક્સ ભૂગોળ કહી શકાય. ધારની ભૂગોળ અવકાશ-પૂર્ણ છે. આ એ જ રચનાનો ઉપયોગ કરીને સાબિત કરી શકાય છે જેનો ઉપયોગ શિરોબિંદુ ભૂગોળ માટે કરવામાં આવ્યો હતો. દિશાહીન ભૂગોળ કોઈ પણ વ્યક્તિ દિશાહીન આલેખ પર ભૂગોળની રમત રમવાનું પણ વિચારી શકે છે (એટલે કે, ધારને બંને દિશામાં પસાર કરી શકાય છે). ફ્રેન્કેલ, શાઈનરમેન અને ઉલમેન દર્શાવે છે કે દિશાહીન શિરોબિંદુ ભૂગોળ બહુપદી સમયમાં ઉકેલી શકાય છે, જ્યારે દિશાહીન ધાર ભૂગોળ PSPACE-પૂર્ણ છે, મહત્તમ ડિગ્રી 3 ધરાવતા સમતલીય આલેખ માટે પણ. જો આલેખ દ્વિપક્ષી હોય, તો દિશાહીન ધાર ભૂગોળ બહુપદી સમયમાં ઉકેલી શકાય તેવું છે. પરિણામો GG એ PSPACE-પૂર્ણ છે તે જોતાં, જ્યાં સુધી P = PSPACE ન હોય ત્યાં સુધી GG માં શ્રેષ્ઠ રમત માટે કોઈ બહુપદી સમય અલ્ગોરિધમ અસ્તિત્વમાં નથી. જો કે, અન્ય રમતોની જટિલતાને સાબિત કરવી એટલી સરળ ન પણ હોઈ શકે કારણ કે અમુક રમતો (જેમ કે ચેસ) માં મર્યાદિત સંખ્યામાં રમતની સ્થિતિ હોય છે-જે PSPACE-પૂર્ણ સમસ્યાનું મેપિંગ ઘડવાનું મુશ્કેલ (અથવા અશક્ય) બનાવે છે. આમ છતાં, અમુક રમતોની જટિલતાનું હજી પણ સામાન્યીકરણ દ્વારા વિશ્લેષણ કરી શકાય છે (દા. ત., એન × એન બોર્ડ). જી. જી. ની સંપૂર્ણતાના પુરાવા તરીકે, સામાન્યીકૃત ગો માટેના પુરાવા માટે સંદર્ભો જુઓ. સંદર્ભો માઈકલ સિપ્સર, કોમ્પ્યુટેશનના સિદ્ધાંતનો પરિચય, પીડબ્લ્યુએસ, 1997. PSPACE-પૂર્ણ સમસ્યાઓ