कम्प्युटेशनल जटिलता सिद्धान्तको दायरामा, विशेष गरी जब स्पेस जटिलता वर्गहरूको जाँच गर्दा, PSPACE र NP बीचको सम्बन्ध महत्त्वपूर्ण चासोको छ। प्रश्नलाई सीधा सम्बोधन गर्न: हो, त्यहाँ PSPACE मा समस्याहरू छन् जसको लागि त्यहाँ कुनै ज्ञात NP एल्गोरिथ्म छैन। यो दाबी यी जटिलता वर्गहरू बीचको परिभाषा र सम्बन्धहरूमा निहित छ।
PSPACE निर्णय समस्याहरूको वर्ग हो जसलाई ट्युरिङ मेसिनले स्पेसको बहुपद मात्रा प्रयोग गरेर समाधान गर्न सकिन्छ। अर्को शब्दमा, PSPACE मा समस्या छ यदि त्यहाँ एउटा एल्गोरिदम छ जसले यसलाई इनपुटको आकारमा बहुपदीय मेमोरीको मात्रा प्रयोग गरेर समाधान गर्न सक्छ। यस वर्गले विभिन्न प्रकारका समस्याहरू समावेश गर्दछ, जसमध्ये केही धेरै जटिल छन् र जटिल कम्प्यूटेशनल प्रक्रियाहरू समावेश छन्।
NP, अर्कोतर्फ, निर्णय समस्याहरूको वर्ग हो जसको लागि प्रस्तावित समाधान बहुपदीय समयमा एक निर्धारित ट्युरिङ मेसिनद्वारा प्रमाणित गर्न सकिन्छ। यसको मतलब यो हो कि यदि कसैले NP मा समस्याको लागि उम्मेदवार समाधान प्रदान गर्दछ भने, तपाइँ त्यस समाधानको शुद्धता छिट्टै जाँच गर्न सक्नुहुन्छ, विशेष गरी इनपुट साइजको सापेक्ष बहुपद समयमा।
यी दुई वर्गहरू बीचको सम्बन्ध यस्तो छ कि NP PSPACE को एक उपसेट हो। यो किनभने कुनै पनि समस्या जुन बहुपद समयमा प्रमाणित गर्न सकिन्छ बहुपद स्थानमा पनि समाधान गर्न सकिन्छ। किन बुझ्नको लागि, विचार गर्नुहोस् कि बहुपद-समय प्रमाणिकरणकर्ताले इनपुटको बिट्स र प्रस्तावित समाधानको बहुपद संख्या मात्र पढ्न सक्छ। तसर्थ, यसलाई बहुपदीय-स्पेस मेसिनद्वारा सिमुलेट गर्न सकिन्छ जसले यसले पढेको स्थिति र यसले गरेको कार्यहरू ट्र्याक राख्छ।
यद्यपि, कुराकानी सत्य हो भनेर थाहा छैन; अर्थात्, यो थाहा छैन कि PSPACE NP को उपसमूह हो कि होइन। वास्तवमा, यो व्यापक रूपमा विश्वास गरिन्छ कि PSPACE मा समस्याहरू छन् जुन NP मा छैनन्, यद्यपि यो औपचारिक रूपमा प्रमाणित भएको छैन। यो विश्वास PSPACE मा समस्याहरूको अस्तित्वमा आधारित छ जसलाई समाधान गर्न बहुपद समय भन्दा बढी आवश्यक देखिन्छ, यद्यपि तिनीहरू बहुपदीय स्थानबाट समाधान गर्न सकिन्छ।
NP मा नभएको PSPACE मा भएको समस्याको प्रमाणिक उदाहरणहरू मध्ये एक क्वान्टिफाइड बुलियन सूत्र (QBF) समस्या हो। QBF बुलियन सन्तुष्टि समस्या (SAT) को सामान्यीकरण हो, जुन NP-पूर्ण छ। जबकि SAT ले सोध्छ कि त्यहाँ चरहरूमा सत्य मानहरूको असाइनमेन्ट छ कि दिईएको बुलियन सूत्रलाई सत्य बनाउँछ, QBF ले चरहरूमा नेस्टेड क्वान्टीफायरहरू समावेश गर्दछ, जस्तै "सबै xका लागि, सूत्र सत्य हो।" यी क्वान्टीफायरहरूको उपस्थितिले QBF लाई धेरै जटिल बनाउँछ। QBF PSPACE-पूर्ण छ, यसको मतलब यो PSPACE मा कुनै पनि समस्या जत्तिकै कठिन छ। यदि QBF को लागी एक NP एल्गोरिथ्म थियो भने, यसले NP बराबर PSPACE को अर्थ दिन्छ, एक परिणाम जुन ग्राउन्डब्रेकिंग हुनेछ र व्यापक रूपमा असम्भव मानिन्छ।
अर्को उदाहरणीय उदाहरण सामान्यीकृत खेलहरूमा विजेता निर्धारण गर्ने समस्या हो, जस्तै चेस वा गो को सामान्यीकृत संस्करणहरू, N x N बोर्डमा खेलिएको। यी समस्याहरूले चाल र कन्फिगरेसनहरूको सम्भावित घातांक संख्या समावेश गर्दछ, तर तिनीहरू सबै सम्भावित खेल अवस्थाहरू व्यवस्थित रूपमा अन्वेषण गरेर बहुपदीय ठाउँ प्रयोग गरेर निर्णय गर्न सकिन्छ। यी समस्याहरू पनि PSPACE-पूर्ण छन्, थप PSPACE मा समस्याहरूको अस्तित्व सुझाव दिन्छ जुन NP मा छैन।
PSPACE मा किन निश्चित समस्याहरू NP बाहिर छन् भनी विश्वास गरिन्छ भन्ने बारे गहिरो अध्ययन गर्न, अन्तरिक्ष-बाउन्ड बनाम समय-सीमाबद्ध गणनाहरूको प्रकृतिलाई विचार गर्नुहोस्। बहुपदीय स्पेसले कम्प्युटेसनल चरणहरूको सम्भावित घातांक संख्याको लागि अनुमति दिन्छ, जबसम्म प्रयोग गरिएको ठाउँ बहुपद रूपमा सीमित रहन्छ। यो NP को एकदमै विपरित हो, जहाँ समय बहुपदीय रूपमा सीमित छ। बहुपदीय स्थानद्वारा अनुमति दिइएको घातीय समय समस्याहरू समाधान गर्न प्रयोग गर्न सकिन्छ जसमा QBF र सामान्यीकृत खेलहरूमा सामना गरिएका घातीय रूपमा ठूला ठाउँहरूमा विस्तृत खोजहरू समावेश हुन्छन्।
यसबाहेक, त्यहाँ जटिल सैद्धान्तिक निर्माणहरू छन् जसले थप PSPACE र NP बीचको भिन्नतालाई समर्थन गर्दछ। उदाहरणका लागि, चन्द्र, कोजेन र स्टकमेयरद्वारा प्रस्तुत गरिएको वैकल्पिक अवधारणाले ननडेटरमिनिज्मलाई सामान्य बनाउँछ र एपी (अल्टरनेटिंग बहुपदीय समय) वर्गमा लैजान्छ। यो देखाइएको छ कि AP PSPACE बराबर छ, यसरी बहुपद अन्तरिक्ष गणना को शक्ति मा एक फरक परिप्रेक्ष्य प्रदान गर्दछ। वैकल्पिकतामा QBF को संरचना प्रतिबिम्बित गर्ने, अस्तित्व र विश्वव्यापी क्वान्टीफायरहरूको अनुक्रम समावेश छ, र PSPACE समस्याहरूमा निहित जटिलता प्रदर्शन गर्दछ।
यो पनि ध्यान दिन लायक छ कि जटिलता वर्ग को विभाजन सैद्धांतिक कम्प्युटर विज्ञान मा एक मौलिक खुला प्रश्न हो। प्रसिद्ध P बनाम NP समस्या यस व्यापक अनुसन्धानको एक विशेष मामला हो। त्यसैगरी, NP बराबर PSPACE हुन्छ कि भन्ने प्रश्न अनसुलझे छ। यद्यपि, विस्तृत अध्ययन र ज्ञात समस्याहरूको प्रकृतिको आधारमा क्षेत्रको सहमति यो हो कि PSPACE ले NP मा नभएका समस्याहरू समावेश गर्दछ।
PSPACE मा समस्याहरूको अस्तित्व जसको लागि कुनै ज्ञात NP एल्गोरिदम छैन यी जटिलता वर्गहरू बीचको परिभाषा र सम्बन्धहरू, साथै QBF र सामान्यीकृत खेल समस्याहरू जस्ता ठोस उदाहरणहरूद्वारा समर्थित छ। यी उदाहरणहरूले जटिल र सम्भावित घातीय कम्प्युटेसनल प्रक्रियाहरूलाई हाइलाइट गर्दछ जुन बहुपद स्थान भित्र व्यवस्थापन गर्न सकिन्छ तर बहुपद समयमा सीमित हुन सम्भव छैन, यसैले तिनीहरूलाई NP को दायरा बाहिर राख्छ।
अन्य भर्खरका प्रश्न र उत्तरहरू सम्बन्धमा जटिलता:
- के PSPACE वर्ग EXPSPACE वर्गको बराबर छैन?
- के P जटिलता वर्ग PSPACE वर्गको उपसमूह हो?
- के हामी एक निश्चित TM मा कुनै पनि NP पूर्ण समस्याको लागि एक कुशल बहुपद समाधान खोजेर Np र P वर्ग समान छन् भनेर प्रमाणित गर्न सक्छौं?
- के NP वर्ग EXPTIME कक्षा बराबर हुन सक्छ?
- के एक SAT समस्या NP पूर्ण समस्या हुन सक्छ?
- के NP जटिलता वर्गमा समस्या हुन सक्छ यदि त्यहाँ एक गैर-निर्धारित ट्युरिङ मेसिन छ जसले यसलाई बहुपद समयमा समाधान गर्नेछ।
- NP बहुपदीय समय प्रमाणिकरण भएका भाषाहरूको वर्ग हो
- के P र NP वास्तवमा एउटै जटिलता वर्ग हो?
- के प्रत्येक सन्दर्भ मुक्त भाषा P जटिलता वर्गमा छ?
- के त्यहाँ बहुपद-समय प्रमाणिकरणहरूको साथ निर्णय समस्याहरूको वर्गको रूपमा NP को परिभाषा र वर्ग P मा पनि बहुपद-समय प्रमाणिकरणहरू छन् भन्ने तथ्य बीचको विरोधाभास छ?
जटिलतामा थप प्रश्न र उत्तरहरू हेर्नुहोस्