Generalized geography
कम्प्यूटेशनल जटिलता सिद्धांत में, सामान्यीकृत भूगोल एक प्रसिद्ध पी. एस. पी. ए. सी. ई.-पूर्ण समस्या है। भूगोल एक बच्चों का खेल है, जहाँ खिलाड़ी बारी-बारी से दुनिया में कहीं से भी शहरों के नाम लेते हैं। चुने गए प्रत्येक शहर को उसी अक्षर से शुरू होना चाहिए जो पिछले शहर के नाम को समाप्त करता है। पुनरावृत्ति की अनुमति नहीं है। खेल एक मनमाने ढंग से शुरू होने वाले शहर से शुरू होता है और तब समाप्त होता है जब कोई खिलाड़ी हार जाता है क्योंकि वह जारी रखने में असमर्थ होता है। ग्राफ मॉडल खेल की कल्पना करने के लिए, एक निर्देशित ग्राफ का निर्माण किया जा सकता है जिसके नोड्स दुनिया के प्रत्येक शहर हैं। नोड एन1 से नोड एन2 में एक तीर जोड़ा जाता है यदि और केवल तभी जब शहर की लेबलिंग एन2 उस अक्षर से शुरू होती है जो शहर की लेबलिंग नोड एन1 के नाम को समाप्त करता है। दूसरे शब्दों में, हम एक शहर से दूसरे शहर में एक तीर खींचते हैं यदि पहला खेल के नियमों के अनुसार दूसरे की ओर ले जा सकता है। निर्देशित ग्राफ में प्रत्येक वैकल्पिक किनारा प्रत्येक खिलाड़ी (दो खिलाड़ियों के खेल के लिए) से मेल खाता है। पहला खिलाड़ी जो रास्ता बढ़ाने में असमर्थ होता है वह हार जाता है। खेल का एक चित्रण (जिसमें मिशिगन के कुछ शहर शामिल हैं) नीचे दिए गए चित्र में दिखाया गया है। एक सामान्यीकृत भूगोल (जी. जी.) खेल में, हम शहर के नामों के ग्राफ को एक मनमाने ढंग से निर्देशित ग्राफ से बदल देते हैं। निम्नलिखित ग्राफ एक सामान्यीकृत भूगोल खेल का एक उदाहरण है। खेल खेलना हम पी1 को पहले आगे बढ़ने वाले खिलाड़ी के रूप में और पी2 को दूसरे स्थान पर जाने वाले खिलाड़ी के रूप में परिभाषित करते हैं और नोड्स को एन1 से एनएन नाम देते हैं। उपरोक्त चित्र में, पी1 की जीत की रणनीति इस प्रकार हैः एन1 केवल नोड्स एन2 और एन3 को अंक देता है। इस प्रकार पी1 की पहली चाल इन दो विकल्पों में से एक होनी चाहिए। पी1 एन2 चुनता है (यदि पी1 एन3 चुनता है, तो पी2 एन9 चुनेगा क्योंकि यही एकमात्र विकल्प है और पी1 हार जाएगा)। अगला पी2 एन4 चुनता है क्योंकि यह एकमात्र शेष विकल्प है। पी1 अब एन5 चुनता है और पी2 बाद में एन3 या एन7 चुनता है। पी2 की पसंद के बावजूद, पी1 एन9 चुनता है और पी2 के पास कोई शेष विकल्प नहीं है और खेल हार जाता है। कम्प्यूटेशनल जटिलता एक सामान्यीकृत भूगोल खेल में किस खिलाड़ी की जीतने की रणनीति है, यह निर्धारित करने की समस्या पी. एस. पी. ए. सी. ई.-पूर्ण है। सामान्यीकृत भूगोल पी. एस. पी. ए. सी. ई. में है मान लीजिए कि जी. जी. = {75जी, बी. पी. ओ.। पी. 1 के पास जी. ग्राफ पर खेले जाने वाले सामान्यीकृत भूगोल खेल के लिए एक जीत की रणनीति है जो नोड बी. से शुरू होती है; यह दिखाने के लिए कि जी. जी. पी. एस. पी. ए. सी. ई., हम एक बहुपद-स्थान पुनरावर्ती एल्गोरिथ्म प्रस्तुत करते हैं जो यह निर्धारित करता है कि किस खिलाड़ी की जीत की रणनीति है। जी. जी. के एक उदाहरण को देखते हुए, जहां जी. एक निर्देशित ग्राफ है और एनस्टार्ट नामित प्रारंभ नोड है, एल्गोरिथ्म एम निम्नानुसार आगे बढ़ता हैः एम. (एन. जी. ओ. जी., एन. एस. टी. ओ. जी. ओ.): एन. एस. टी. ओ. के बाहरी स्तर को मापें। यदि यह डिग्री 0 है, तो लौटें, क्योंकि खिलाड़ी एक के लिए कोई चाल उपलब्ध नहीं है। nstart से एक किनारे तक पहुँचने योग्य सभी नोड्स की एक सूची बनाएँः n1, n2,., ni। जी1 बनाने के लिए जी से एनस्टार्ट और उससे जुड़े सभी किनारों को हटा दें। सूची n1,., ni में प्रत्येक नोड nj के लिए, M ( ꯫ यदि ये सभी कॉल वापस स्वीकार कर लेते हैं, तो कोई फर्क नहीं पड़ता कि पी1 क्या निर्णय लेता है, पी2 के पास जीतने की रणनीति है, इसलिए वापस अस्वीकार कर दें। अन्यथा (यदि एक कॉल वापस आती है तो अस्वीकार कर दें) पी1 के पास एक विकल्प है जो पी2 के लिए किसी भी सफल रणनीति को अस्वीकार कर देगा, इसलिए वापस स्वीकार करें। एल्गोरिथ्म एम स्पष्ट रूप से जीजी तय करता है। यह पी. एस. पी. ए. सी. ई. में है क्योंकि केवल गैर-स्पष्ट बहुपद कार्यस्थल की खपत पुनरावृत्ति ढेर में होती है। रिकर्शन स्टैक द्वारा खपत किया गया स्थान बहुपद है क्योंकि रिकर्शन का प्रत्येक स्तर स्टैक में एक एकल नोड जोड़ता है, और अधिकतम एन स्तरों पर होते हैं, जहां एन जी में नोड्स की संख्या है। यह अनिवार्य रूप से एक गहराई-पहली खोज के बराबर है। निम्नलिखित प्रमाण डेविड लिक्टेंस्टीन और माइकल सिप्सर के कारण है। जी. जी. की पी. एस. पी. ए. सी. ई.-कठोरता स्थापित करने के लिए, हम बहुपद समय (पी) में फॉर्मूला-गेम समस्या (जिसे पी. एस. पी. ए. सी. ई.-हार्ड के रूप में जाना जाता है) को जी. जी. तक कम कर सकते हैं। संक्षेप में, फॉर्मूला-गेम समस्या के एक उदाहरण में एक मात्रात्मक बूलियन सूत्र φ = HE x1 β x2 HE x3. Qxk (si) होता है जहां Q या तो HE या β है। यह खेल दो खिलाड़ियों, पा और पे द्वारा खेला जाता है, जो क्रमिक xi के लिए वैकल्पिक मूल्य चुनते हैं। पी खेल जीतता है यदि सूत्र ± सही हो जाता है, और पी जीतता है यदि ± गलत हो जाता है। सूत्र को संयुग्म सामान्य रूप में माना जाता है। इस प्रमाण में, हम मानते हैं कि परिमापक सूची सरलता के लिए अस्तित्वगत योग्यता, एच. ई. के साथ शुरू होती है और समाप्त होती है। ध्यान दें कि किसी भी अभिव्यक्ति को डमी चर जोड़कर इस रूप में परिवर्तित किया जा सकता है जो si में दिखाई नहीं देते हैं। ऊपर दिखाए गए ग्राफ की तरह एक ग्राफ जी का निर्माण करके, हम दिखाएंगे कि फॉर्मूला-गेम के किसी भी उदाहरण को सामान्यीकृत भूगोल के एक उदाहरण तक कम किया जा सकता है, जहां पी1 के लिए इष्टतम रणनीति पी के बराबर है, और पी2 के लिए इष्टतम रणनीति पी के बराबर है। नोड्स की बाईं ऊर्ध्वाधर श्रृंखला को फॉर्मुला-गेम में चर के लिए मूल्यों को चुनने की प्रक्रिया की नकल करने के लिए डिज़ाइन किया गया है। हीरे की प्रत्येक संरचना एक मात्रात्मक चर से मेल खाती है। खिलाड़ी बारी-बारी से प्रत्येक शाखा नोड पर रास्ता तय करते हैं। क्योंकि हमने माना था कि पहला परिमापक अस्तित्वगत होगा, पी1 पहले जाता है, बाएं नोड का चयन करते हुए यदि x1 सही है और दाएं नोड का चयन करते हुए यदि x1 गलत है। प्रत्येक खिलाड़ी को तब जबरन मोड़ लेना चाहिए, और फिर पी2 x2 के लिए एक मान चुनता है। ये वैकल्पिक कार्य बाईं ओर नीचे जारी रहते हैं। दोनों खिलाड़ियों के सभी हीरे पार करने के बाद, यह फिर से पी1 की बारी है, क्योंकि हमने माना कि अंतिम परिमापक अस्तित्वगत है। पी1 के पास ग्राफ के दाहिने तरफ के रास्ते का पालन करने के अलावा कोई विकल्प नहीं है। फिर कदम उठाने की पी2 की बारी है। जब खेल ग्राफ के दाईं ओर पहुँचता है, तो यह फॉर्मूला गेम में खेल के अंत के समान होता है। याद रखें कि फॉर्मूला गेम में, पे जीतता है यदि ± सही है, जबकि पा जीतता है यदि ± गलत है। ग्राफ का दाहिना पक्ष इस बात की गारंटी देता है कि पी1 तभी जीतता है जब पी जीतता है, और पी2 तभी जीतता है जब पी जीतता है। पहले हम दिखाते हैं कि पी2 हमेशा जीतता है जब पी जीतता है। यदि पा जीतता है, तो si गलत है। यदि si गलत है, तो एक असंतोषजनक खंड मौजूद है। पी2 जीतने के लिए एक असंतोषजनक खंड का चयन करेगा। फिर जब पी1 की बारी आती है तो उसे पी2 द्वारा चुने गए उस खंड में एक शाब्दिक का चयन करना चाहिए। चूँकि खंड में सभी अक्षर गलत हैं, वे बाईं ऊर्ध्वाधर श्रृंखला में पहले देखे गए नोड्स से नहीं जुड़ते हैं। यह पी2 को बाईं श्रृंखला के हीरे में संबंधित नोड के कनेक्शन का पालन करने और इसे चुनने की अनुमति देता है। हालाँकि, पी1 अब किसी भी आसन्न नोड्स और लॉस का चयन करने में असमर्थ है। अब हम दिखाते हैं कि पी1 हमेशा जीतता है जब पी जीतता है। यदि पे जीतता है, तो si सही है। यदि si सही है, तो ग्राफ के दाहिने तरफ के प्रत्येक खंड में एक सही शाब्दिक है। पी2 किसी भी खंड को चुन सकता है। फिर पी1 उस शाब्दिक को चुनता है जो सच है। और क्योंकि यह सच है, बाएं ऊर्ध्वाधर नोड में इसके आसन्न नोड को पहले ही चुना जा चुका है, इसलिए पी2 के पास बनाने और खोने के लिए कोई चाल नहीं है। समतल सामान्यीकृत भूगोल पी. एस. पी. ए. सी. ई.-पूर्ण सामान्यीकृत भूगोल पी. एस. पी. ए. सी. ई.-पूर्ण है, तब भी जब समतल ग्राफ पर खेला जाता है। निम्नलिखित प्रमाण के प्रमेय 3 से है। चूँकि समतलीय जी. जी. जी. जी. जी. का एक विशेष मामला है, और जी. जी. पी. एस. पी. ए. सी. ई. में है, इसलिए समतलीय जी. जी. पी. एस. पी. ए. सी. ई. में है। यह दिखाना बाकी है कि प्लेनर जीजी स्पेस-हार्ड है। इसे यह दिखाकर साबित किया जा सकता है कि एक मनमाने ग्राफ को एक समतलीय ग्राफ में कैसे परिवर्तित किया जाए, जैसे कि इस ग्राफ पर खेले गए जीजी के खेल का परिणाम मूल ग्राफ के समान ही होगा। ऐसा करने के लिए, केवल मूल ग्राफ के सभी किनारे क्रॉसिंग को समाप्त करना आवश्यक है। हम ग्राफ को इस तरह से बनाते हैं कि कोई भी तीन किनारे एक बिंदु पर एक दूसरे को नहीं काटते हैं, और एक ही खेल में पार करने वाले किनारों की किसी भी जोड़ी का उपयोग नहीं किया जा सकता है। यह सामान्य रूप से संभव नहीं है, लेकिन एक फॉर्मूला-गेम उदाहरण से निर्मित ग्राफ के लिए हमेशा संभव है; उदाहरण के लिए हमारे पास क्रॉसिंग में शामिल खंड शीर्षों के केवल किनारे हो सकते हैं। अब हम प्रत्येक क्रॉसिंग को इस संरचना के साथ प्रतिस्थापित करते हैंः परिणाम एक समतल ग्राफ है, और वही खिलाड़ी मूल ग्राफ की तरह जीत के लिए मजबूर कर सकता हैः यदि कोई खिलाड़ी परिवर्तित खेल में वी से "ऊपर" जाने का विकल्प चुनता है, तो दोनों खिलाड़ियों को डब्ल्यू की ओर "ऊपर" जाना जारी रखना चाहिए या तुरंत हारना चाहिए। इसलिए परिवर्तित खेल में V से "ऊपर" जाना मूल खेल में V → W चाल का अनुकरण करता है। यदि V → W एक विजयी चाल है, तो परिवर्तित खेल में V से "ऊपर" जाना भी एक विजयी चाल है, और इसके विपरीत। इस प्रकार, परिवर्तित ग्राफ पर खेले जाने वाले जी. जी. के खेल का परिणाम मूल ग्राफ के समान ही होगा। इस परिवर्तन में समय लगता है जो मूल ग्राफ में किनारे के चौराहों की संख्या का एक स्थिर गुणक है, इस प्रकार इसमें बहुपद समय लगता है। इस प्रकार समतल जी. जी. पी. एस. पी. ए. सी. ई.-पूर्ण है। अधिकतम डिग्री 3 के साथ समतल द्विदलीय ग्राफ पर खेले जाने वाले अधिकतम डिग्री 3 जी. जी. के साथ समतल द्विदलीय ग्राफ अभी भी पी. एस. पी. ए. सी. ई.-पूर्ण है, 3 से अधिक डिग्री के शीर्षों को अधिकतम डिग्री 3 के साथ शीर्षों की श्रृंखला के साथ प्रतिस्थापित करके। सबूत अंदर है। और निम्नलिखित संरचना का उपयोग करता हैः यदि एक खिलाड़ी इस निर्माण के किसी भी प्रवेश द्वार का उपयोग करता है, तो दूसरा खिलाड़ी चुनता है कि किस निकास का उपयोग किया जाएगा। इसके अलावा निर्माण को केवल एक बार पार किया जा सकता है, क्योंकि केंद्रीय शीर्ष पर हमेशा दौरा किया जाता है। इसलिए यह संरचना मूल शीर्ष के बराबर है। किनारे का भूगोल जी. जी. के एक प्रकार को किनारे का भूगोल कहा जाता है, जहाँ प्रत्येक चाल के बाद, खिलाड़ी जिस किनारे से गुजरा, उसे मिटा दिया जाता है। यह मूल जी. जी. के विपरीत है, जहां प्रत्येक चाल के बाद, खिलाड़ी जिस शीर्ष पर होता था, उसे मिटा दिया जाता है। इस दृष्टिकोण से मूल जी. जी. को वर्टेक्स भूगोल कहा जा सकता है। किनारे का भूगोल पी. एस. पी. ए. सी. ई.-पूर्ण है। यह उसी निर्माण का उपयोग करके साबित किया जा सकता है जिसका उपयोग शीर्ष भूगोल के लिए किया गया था। दिशाहीन भूगोल एक दिशाहीन ग्राफ पर भूगोल खेल खेलने पर भी विचार किया जा सकता है (यानी, किनारों को दोनों दिशाओं में पार किया जा सकता है)। फ्रेंकेल, शाइनरमैन और उलमैन बताते हैं कि दिशाहीन शीर्ष भूगोल को बहुपद समय में हल किया जा सकता है, जबकि दिशाहीन किनारे का भूगोल पी. एस. पी. ए. सी. ई.-पूर्ण है, यहां तक कि अधिकतम डिग्री 3 वाले समतल ग्राफ के लिए भी। यदि ग्राफ द्विदलीय है, तो दिशाहीन किनारा भूगोल बहुपद समय में हल करने योग्य है। परिणाम यह देखते हुए कि जी. जी. पी. एस. पी. ए. सी. ई.-पूर्ण है, जी. जी. में इष्टतम खेल के लिए कोई बहुपद समय एल्गोरिथ्म मौजूद नहीं है जब तक कि पी = पी. एस. पी. ए. सी. ई. न हो। हालाँकि, अन्य खेलों की जटिलता को साबित करना उतना आसान नहीं हो सकता है क्योंकि कुछ खेलों (जैसे शतरंज) में खेल की स्थिति की एक सीमित संख्या होती है-जिससे पी. एस. पी. ए. सी. ई.-पूर्ण समस्या के लिए मानचित्रण तैयार करना कठिन (या असंभव) हो जाता है। इसके बावजूद, कुछ खेलों की जटिलता का अभी भी सामान्यीकरण द्वारा विश्लेषण किया जा सकता है (उदाहरण के लिए, एक एन × एन बोर्ड)। जी. जी. की पूर्णता के प्रमाण के परिणाम के रूप में सामान्यीकृत गो के प्रमाण के लिए संदर्भ देखें। संदर्भ माइकल सिप्सर, इंट्रोडक्शन टू द थ्योरी ऑफ कम्प्यूटेशन, पीडब्ल्यूएस, 1997। PSPACE-पूर्ण समस्याएं