संरचनात्मक सम्मिश्र सिद्धांत

This article is about कंप्यूटर विज्ञान का क्षेत्र. For अनुप्रयुक्त गणित का क्षेत्र, see स्ट्रक्चरल कॉम्प्लेक्सिटी (अनुप्रयुक्त गणित).

बहुपद समय पदानुक्रम का सचित्र प्रतिनिधित्व। एरो समावेशन को दर्शाते हैं।

कंप्यूटर विज्ञान के स्ट्रक्चरल कॉम्प्लेक्सिटी थ्योरी में, संरचनात्मक कॉम्प्लेक्सिटी सिद्धांत या बस संरचनात्मक कॉम्प्लेक्सिटी व्यक्तिगत समस्याओं एवं एल्गोरिदम की संरचनात्मक कॉम्प्लेक्सिटी के अतिरिक्त कॉम्प्लेक्सिटी वर्गों का अध्ययन है। इसमें विभिन्न कॉम्प्लेक्सिटी वर्गों की आंतरिक संरचनाओं एवं विभिन्न कॉम्प्लेक्सिटी वर्गों के मध्य संबंधों का अनुसंधान सम्मिलित है।

इतिहास

यह सिद्धांत इस प्रकार के पूर्व एवं अभी भी सबसे महत्वपूर्ण प्रश्न, P = NP समस्या को हल करने के प्रयासों (अभी भी विफल) के परिणामस्वरूप उभरा है। अधिकांश शोध P की धारणा के आधार पर किया जाता है, जो NP के समान नहीं है, एवं अधिक दूरगामी अनुमान पर आधारित है कि कॉम्प्लेक्सिटी वर्गों का बहुपद समय पदानुक्रम अनंत है।

महत्वपूर्ण परिणाम

कम्प्रेशन प्रमेय

Main article: कम्प्रेशन प्रमेय

कम्प्रेशन प्रमेय गणना योग्य कार्यों की कॉम्प्लेक्सिटी के विषय में महत्वपूर्ण प्रमेय है।

प्रमेय बताता है, कि गणना योग्य सीमा के साथ कोई सबसे बड़ा कॉम्प्लेक्सिटी वर्ग उपस्थित नहीं है, जिसमें सभी गणना योग्य कार्य सम्मिलित हैं।

स्पेस पदानुक्रम प्रमेय

Main article: स्पेस पदानुक्रम प्रमेय

स्पेस पदानुक्रम प्रमेय पृथक्करण परिणाम हैं, जो दिखाते हैं कि नियतात्मक एवं गैर-नियतात्मक दोनों मशीनें कुछ नियमो के अधीन, अधिक स्थान में (असममित रूप से) अधिक समस्याओं को हल कर सकती हैं। उदाहरण के लिए, नियतात्मक ट्यूरिंग मशीन स्पेस n की अपेक्षा में स्पेस n log n में अधिक निर्णय समस्याओं को हल कर सकती है। समय के लिए कुछ सीमा तक शक्तिहीन अनुरूप प्रमेय समय पदानुक्रम प्रमेय हैं।

समय पदानुक्रम प्रमेय

Main article: समय पदानुक्रम प्रमेय

समय पदानुक्रम प्रमेय ट्यूरिंग मशीनों पर समयबद्ध गणना के विषय में महत्वपूर्ण कथन हैं। अनौपचारिक रूप से, ये प्रमेय कहते हैं, कि अधिक समय दिए जाने पर, ट्यूरिंग मशीन अधिक समस्याओं का समाधान कर सकती है। उदाहरण के लिए, ऐसी समस्याएं हैं जिन्हें n² समय के साथ हल किया जा सकता है, किन्तु n के साथ नहीं किया जा सकता है।

वैलेंट-वज़ीरानी प्रमेय

Main article: वैलेंट-वज़ीरानी प्रमेय

वैलेंट-वज़ीरानी प्रमेय संरचनात्मक कॉम्प्लेक्सिटी सिद्धांत में प्रमेय है। लेस्ली वैलेंट एवं विजय वज़ीरानी ने 1986 में प्रकाशित NP शीर्षक वाले अपने पेपर में यह सिद्ध किया था, कि अद्वितीय समाधानों की जानकारी ज्ञात करना सरल है। प्रमेय बताता है कि स्पष्ट-सैट बहुपद समय एल्गोरिथ्म है, तो NP=RP होता है। प्रमाण मुलमुले-वज़ीरानी आइसोलेशन लेम्मा पर आधारित है, जिसे पश्चात में सैद्धांतिक कंप्यूटर विज्ञान में कई महत्वपूर्ण अनुप्रयोगों के लिए उपयोग किया गया था।

सिप्सर-लौटेमैन प्रमेय

Main article: सिप्सर-लौटेमैन प्रमेय

सिप्सर-लौटेमैन प्रमेय या सिप्सर-गैक्स-लौटेमैन प्रमेय में कहा गया है कि बाउंडेड-एरर प्रोबेबिलिस्टिक पॉलिनोमियल (बीपीपी) समय, बहुपद पदानुक्रम में निहित है, एवं अधिक विशेष रूप से Σ₂ ∩ Π₂ है।

सैविच का प्रमेय

Main article: सैविच का प्रमेय

सैविच का प्रमेय, 1970 में वाल्टर सैविच द्वारा सिद्ध किया गया, निश्चयात्मक एवं गैर-नियतात्मक स्पेस कॉम्प्लेक्सिटी के मध्य संबंध प्रदान करता है। इसमें कहा गया है कि किसी भी फंक्शन के लिए $f\in \Omega (\log(n))$

${\mathsf {NSPACE}}\left(f\left(n\right)\right)\subseteq {\mathsf {DSPACE}}\left(\left(f\left(n\right)\right)^{2}\right)$ होता है।

टोडा का प्रमेय

Main article: टोडा का प्रमेय

टोडा का प्रमेय परिणाम है जिसे होशिनोसुके टोडा ने अपने पेपर पीपी इज एज़ हार्ड एज़ द पोलिनोमियल-टाइम हायरार्की (1991) में सिद्ध किया था एवं उन्हें 1998 का ​​गोडेल पुरस्कार दिया गया था। प्रमेय बताता है, कि संपूर्ण PH (कॉम्प्लेक्सिटी) P^PP में समाहित है; इसका तात्पर्य संबंधित कथन से है, कि PH, P^#P में निहित है।

इम्मरमैन-स्ज़ेलेपेसेनी प्रमेय

Main article: इमरमैन-स्ज़ेलेपेसेनी प्रमेय

इमरमैन-स्ज़ेलेपसेनी प्रमेय को 1987 में नील इमरमैन एवं रॉबर्ट सज़ेलेपसेनी द्वारा स्वतंत्र रूप से सिद्ध किया गया था, जिसके लिए उन्होंने 1995 का गोडेल पुरस्कार प्रदान किया गया था। अपने सामान्य रूप में प्रमेय बताता है कि किसी भी फंक्शन s(n) ≥ log n के लिए NSPACE(s(n)) = co-NSPACE(s(n)) है। परिणाम को समान रूप से NL = co-NL (कॉम्प्लेक्सिटी) के रूप में बताया गया है; चूंकि यह विशेष विषय है, जब s(n) = log n, यह मानक पैडिंग तर्क द्वारा सामान्य प्रमेय का तात्पर्य करता है। परिणाम से दूसरी एलबीए समस्या हल हो गई है।

शोध विषय

इस क्षेत्र में अनुसंधान की प्रमुख दिशाओं में सम्मिलित हैं: कॉम्प्लेक्सिटी वर्गों के विषय में विभिन्न अप्रचलित समस्याओं से उत्पन्न निहितार्थों का अध्ययन है।

• विभिन्न प्रकार की संसाधन-प्रतिबंधित कमी (कॉम्प्लेक्सिटी) एवं संबंधित पूर्ण लैंग्वेज का अध्ययन है।
• स्टोरेज एवं डेटा तक पहुंच के प्रणाली एवं विभिन्न प्रतिबंधों के परिणामों का अध्ययन है।