डीएए - अंतरिक्ष जटिलताएं
इस अध्याय में, हम एक एल्गोरिथ्म की आवश्यकता वाले स्थान की मात्रा के संबंध में कम्प्यूटेशनल समस्याओं की जटिलता पर चर्चा करेंगे।
अंतरिक्ष जटिलता समय जटिलता की कई विशेषताओं को साझा करती है और उनकी कम्प्यूटेशनल कठिनाइयों के अनुसार समस्याओं को वर्गीकृत करने का एक और तरीका है।
अंतरिक्ष जटिलता क्या है?
अंतरिक्ष की जटिलता स्मृति (स्पेस) की मात्रा का वर्णन करने वाला एक फ़ंक्शन है जो एल्गोरिथ्म में इनपुट की मात्रा के संदर्भ में एक एल्गोरिथ्म लेता है।
हम अक्सर बोलते हैं extra memoryजरूरत है, इनपुट को स्टोर करने के लिए जरूरी मेमोरी को गिनना नहीं। फिर, हम इसे मापने के लिए प्राकृतिक (लेकिन निश्चित-लंबाई) इकाइयों का उपयोग करते हैं।
हम बाइट्स का उपयोग कर सकते हैं, लेकिन इसका उपयोग करना आसान है, कहते हैं, उपयोग किए गए पूर्णांकों की संख्या, निश्चित-आकार की संरचनाओं की संख्या, आदि।
अंत में, हम जिस फ़ंक्शन के साथ आते हैं वह यूनिट का प्रतिनिधित्व करने के लिए आवश्यक बाइट्स की वास्तविक संख्या से स्वतंत्र होगा।
अंतरिक्ष जटिलता को कभी-कभी अनदेखा कर दिया जाता है क्योंकि उपयोग की जाने वाली जगह न्यूनतम और / या स्पष्ट होती है, हालांकि कभी-कभी यह समय की जटिलता के रूप में महत्वपूर्ण मुद्दा बन जाता है
परिभाषा
चलो M एक निर्धारक हो Turing machine (TM)कि सभी आदानों पर टिका है। की अंतरिक्ष जटिलताM समारोह $ f \ colon एन \ n बैरो एन $ है, जहां f(n) टेप की कोशिकाओं की अधिकतम संख्या है और M लंबाई के किसी भी इनपुट को स्कैन करता है M। यदि अंतरिक्ष की जटिलताM है f(n), हम कह सकते हैं कि M अंतरिक्ष में चलता है f(n)।
हम स्पर्शोन्मुख संकेतन का उपयोग करके ट्यूरिंग मशीन की अंतरिक्ष जटिलता का अनुमान लगाते हैं।
$ F \ colon N \ rightarrow R ^ + $ को एक फंक्शन होने दें। अंतरिक्ष जटिलता वर्गों को निम्नानुसार परिभाषित किया जा सकता है -
SPACE = {L | L is a language decided by an O(f(n)) space deterministic TM}
SPACE = {L | L is a language decided by an O(f(n)) space non-deterministic TM}
PSPACE एक नियतात्मक ट्यूरिंग मशीन पर बहुपद स्थान में निर्णायक भाषाओं का वर्ग है।
दूसरे शब्दों में, PSPACE = Uk SPACE (nk)
सैविच की प्रमेय
अंतरिक्ष जटिलता से संबंधित सबसे शुरुआती प्रमेय में सेविच की प्रमेय है। इस प्रमेय के अनुसार, एक निर्धारक मशीन अंतरिक्ष की एक छोटी मात्रा का उपयोग करके गैर-नियतात्मक मशीनों का अनुकरण कर सकती है।
समय की जटिलता के लिए, इस तरह के अनुकरण के लिए समय में एक घातीय वृद्धि की आवश्यकता होती है। अंतरिक्ष जटिलता के लिए, यह प्रमेय दिखाता है कि कोई भी गैर-नियतात्मक ट्यूरिंग मशीन जो उपयोग करती हैf(n) अंतरिक्ष को नियतात्मक TM में परिवर्तित किया जा सकता है जो उपयोग करता है f2(n) अंतरिक्ष।
इसलिए, सैविच की प्रमेय में कहा गया है कि, किसी भी फ़ंक्शन के लिए $ f \ colon N \ rightarrow R ^ + $, जहां $ f (n) \ geqslant n $
NSPACE(f(n)) ⊆ SPACE(f(n))
जटिलता वर्गों के बीच संबंध
निम्नलिखित चित्र विभिन्न जटिलता वर्गों के बीच संबंधों को दर्शाते हैं।
अब तक, हमने इस ट्यूटोरियल में पी और एनपी कक्षाओं की चर्चा नहीं की है। इन पर बाद में चर्चा की जाएगी।