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

पोलीनोमिकल्स टाइम हायरार्की का सचित्र प्रतिनिधित्व। एरो समावेशन को दर्शाते हैं।

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

इतिहास

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

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

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

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

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

स्पेस हायरार्की थ्योरम

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

टाइम हायरार्की थ्योरम

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

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

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

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

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

सैविच का थ्योरम

सैविच का थ्योरम, 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)

होता है।

टोडा का थ्योरम

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

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

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

रिसर्च विषय

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

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

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

संदर्भ

↑ ^1.0 ^1.1 ^1.2 Juris Hartmanis, "New Developments in Structural Complexity Theory" (invited lecture), Proc. 15th International Colloquium on Automata, Languages and Programming, 1988 (ICALP 88), Lecture Notes in Computer Science, vol. 317 (1988), pp. 271-286.
↑ Valiant, L.; Vazirani, V. (1986). "एनपी अनूठे समाधानों का पता लगाने जितना आसान है" (PDF). Theoretical Computer Science. 47: 85–93. doi:10.1016/0304-3975(86)90135-0.

[jha-1] 1.0 ^1.1 ^1.2 Juris Hartmanis, "New Developments in Structural Complexity Theory" (invited lecture), Proc. 15th International Colloquium on Automata, Languages and Programming, 1988 (ICALP 88), Lecture Notes in Computer Science, vol. 317 (1988), pp. 271-286.

[2] Valiant, L.; Vazirani, V. (1986). "एनपी अनूठे समाधानों का पता लगाने जितना आसान है" (PDF). Theoretical Computer Science. 47: 85–93. doi:10.1016/0304-3975(86)90135-0.

[1]

[2]