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

This article is about the area in computer science. For the area in applied mathematics, see Structural complexity (applied mathematics).

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

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

इतिहास

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

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

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

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, यह एक मानक पैडिंग तर्क द्वारा सामान्य प्रमेय का तात्पर्य करता है. परिणाम ने रैखिक परिबद्ध ऑटोमेटन#एलबीए समस्याओं को हल कर दिया।

शोध विषय

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

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