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

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, यह मानक पैडिंग तर्क द्वारा सामान्य थ्योरम का तात्पर्य करता है। परिणाम से दूसरी एलबीए समस्या हल हो गई है।

रिसर्च विषय

इस क्षेत्र में रिसर्च की प्रमुख दिशाओं में सम्मिलित हैं:

कॉम्प्लेक्सिटी क्लासेज के विषय में विभिन्न अनसॉल्वड प्रॉब्लम्स से उत्पन्न इम्प्लीकेशन का अध्ययन है।

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