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

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

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

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

इतिहास

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

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

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

Main article: Compression theorem

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

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

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

Main article: Space hierarchy theorem

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

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

Main article: Time hierarchy theorem

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

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

Main article: Valiant–Vazirani theorem

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

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

Main article: Sipser–Lautemann theorem

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

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

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: Toda's theorem

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

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

Main article: Immerman–Szelepcsényi theorem

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

शोध विषय

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

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