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

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

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

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

इतिहास

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

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

संपीड़न प्रमेय

Main article: संपीड़न प्रमेय

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

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

अंतरिक्ष पदानुक्रम प्रमेय

Main article: अंतरिक्ष पदानुक्रम प्रमेय

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

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

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

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

बहादुर-वज़ीरानी प्रमेय

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

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

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

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

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

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

Main article: Savitch's theorem

सैविच का प्रमेय, 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)) = सह-NSPACE(s(n)) है। परिणाम को समान रूप से NL = co-NL (जटिलता) के रूप में बताया गया है; चूंकि यह विशेष विषय है, जब s(n) = log n, यह मानक पैडिंग तर्क द्वारा सामान्य प्रमेय का तात्पर्य करता है। परिणाम से दूसरी LBA समस्या हल हो गई।

शोध विषय

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

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