संरचनात्मक सम्मिश्र सिद्धांत: Difference between revisions
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
{{about|कंप्यूटर विज्ञान का क्षेत्र|अनुप्रयुक्त गणित का क्षेत्र|संरचनात्मक | {{about|कंप्यूटर विज्ञान का क्षेत्र|अनुप्रयुक्त गणित का क्षेत्र|संरचनात्मक समष्टिता (अनुप्रयुक्त गणित)}} | ||
[[Image:Polynomial time hierarchy.svg|250px|thumb|right|बहुपद समय पदानुक्रम का सचित्र प्रतिनिधित्व। तीर समावेशन को दर्शाते हैं।]][[कंप्यूटर विज्ञान]] के [[कम्प्यूटेशनल जटिलता सिद्धांत|'''संरचनात्मक | [[Image:Polynomial time hierarchy.svg|250px|thumb|right|बहुपद समय पदानुक्रम का सचित्र प्रतिनिधित्व। तीर समावेशन को दर्शाते हैं।]][[कंप्यूटर विज्ञान]] के [[कम्प्यूटेशनल जटिलता सिद्धांत|'''संरचनात्मक समष्टिता सिद्धांत''']] में, संरचनात्मक समष्टिता सिद्धांत या बस संरचनात्मक समष्टिता व्यक्तिगत समस्याओं एवं एल्गोरिदम की संरचनात्मक समष्टिता के अतिरिक्त [[जटिलता वर्ग|समष्टिता वर्गों]] का अध्ययन है। इसमें विभिन्न समष्टिता वर्गों की आंतरिक संरचनाओं एवं विभिन्न समष्टिता वर्गों के मध्य संबंधों का अनुसंधान सम्मिलित है।<ref name=jha>[[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.</ref> | ||
== इतिहास == | == इतिहास == | ||
यह सिद्धांत इस प्रकार के पूर्व एवं अभी भी सबसे महत्वपूर्ण प्रश्न, P = NP समस्या को हल करने के प्रयासों (अभी भी विफल) के परिणामस्वरूप उभरा है। अधिकांश शोध P की धारणा के आधार पर किया जाता है, जो NP के समान नहीं है, एवं अधिक दूरगामी अनुमान पर आधारित है कि | यह सिद्धांत इस प्रकार के पूर्व एवं अभी भी सबसे महत्वपूर्ण प्रश्न, P = NP समस्या को हल करने के प्रयासों (अभी भी विफल) के परिणामस्वरूप उभरा है। अधिकांश शोध P की धारणा के आधार पर किया जाता है, जो NP के समान नहीं है, एवं अधिक दूरगामी अनुमान पर आधारित है कि समष्टिता वर्गों का [[बहुपद समय पदानुक्रम]] अनंत है।<ref name=jha/> | ||
== महत्वपूर्ण परिणाम == | == महत्वपूर्ण परिणाम == | ||
| Line 9: | Line 9: | ||
===संपीड़न प्रमेय=== | ===संपीड़न प्रमेय=== | ||
{{main|संपीड़न प्रमेय}} | {{main|संपीड़न प्रमेय}} | ||
[[संपीड़न प्रमेय]] [[गणना योग्य कार्य|गणना योग्य कार्यों]] की | [[संपीड़न प्रमेय]] [[गणना योग्य कार्य|गणना योग्य कार्यों]] की समष्टिता के विषय में महत्वपूर्ण प्रमेय है। | ||
प्रमेय बताता है, कि गणना योग्य सीमा के साथ कोई सबसे बड़ा | प्रमेय बताता है, कि गणना योग्य सीमा के साथ कोई सबसे बड़ा समष्टिता वर्ग उपस्थित नहीं है, जिसमें सभी गणना योग्य कार्य सम्मिलित हैं। | ||
===अंतरिक्ष पदानुक्रम प्रमेय=== | ===अंतरिक्ष पदानुक्रम प्रमेय=== | ||
| Line 24: | Line 24: | ||
{{main|वैलेंट-वज़ीरानी प्रमेय}} | {{main|वैलेंट-वज़ीरानी प्रमेय}} | ||
वैलेंट-वज़ीरानी प्रमेय संरचनात्मक | वैलेंट-वज़ीरानी प्रमेय संरचनात्मक समष्टिता सिद्धांत में प्रमेय है। [[लेस्ली वैलेंट]] एवं [[ विजय वज़ीरानी ]] ने 1986 में प्रकाशित NP शीर्षक वाले अपने पेपर में यह सिद्ध किया था, कि अद्वितीय समाधानों की जानकारी ज्ञात करना उतना ही सरल है।<ref>{{Cite journal | last1 = Valiant | first1 = L. | last2 = Vazirani | first2 = V.| doi = 10.1016/0304-3975(86)90135-0 | title = एनपी अनूठे समाधानों का पता लगाने जितना आसान है| url = http://www.cs.princeton.edu/courses/archive/fall05/cos528/handouts/NP_is_as.pdf| journal = [[Theoretical Computer Science (journal)|Theoretical Computer Science]] | volume = 47 | pages = 85–93 | year = 1986 | doi-access = free }}</ref> प्रमेय बताता है कि असंदिग्ध-SAT बहुपद समय एल्गोरिथ्म है, तो NP=RP (समष्टिता)। प्रमाण मुलमुले-वज़ीरानी [[ अलगाव लेम्मा |अलगाव लेम्मा]] पर आधारित है, जिसे पश्चात में [[सैद्धांतिक कंप्यूटर विज्ञान]] में कई महत्वपूर्ण अनुप्रयोगों के लिए उपयोग किया गया था। | ||
===सिप्सर-लौटेमैन प्रमेय=== | ===सिप्सर-लौटेमैन प्रमेय=== | ||
| Line 33: | Line 33: | ||
===सैविच का प्रमेय=== | ===सैविच का प्रमेय=== | ||
{{main|Savitch's theorem}} | {{main|Savitch's theorem}} | ||
सैविच का प्रमेय, 1970 में [[वाल्टर सैविच]] द्वारा सिद्ध किया गया, नियतिवादी एवं गैर-नियतात्मक [[अंतरिक्ष जटिलता]] के मध्य संबंध देता है। इसमें कहा गया है कि किसी भी फलन के लिए <math>f\in\Omega(\log(n))</math> है। | सैविच का प्रमेय, 1970 में [[वाल्टर सैविच]] द्वारा सिद्ध किया गया, नियतिवादी एवं गैर-नियतात्मक [[अंतरिक्ष जटिलता|अंतरिक्ष समष्टिता]] के मध्य संबंध देता है। इसमें कहा गया है कि किसी भी फलन के लिए <math>f\in\Omega(\log(n))</math> है। | ||
:<math>\mathsf{NSPACE}\left(f\left(n\right)\right) \subseteq \mathsf{DSPACE}\left(\left(f\left(n\right)\right)^2\right).</math> | :<math>\mathsf{NSPACE}\left(f\left(n\right)\right) \subseteq \mathsf{DSPACE}\left(\left(f\left(n\right)\right)^2\right).</math> | ||
| Line 40: | Line 40: | ||
{{main|टोडा का प्रमेय}} | {{main|टोडा का प्रमेय}} | ||
टोडा का प्रमेय परिणाम है जिसे [[होशिनोसुके टोडा]] ने अपने पेपर पीपी इज एज़ हार्ड एज़ द पोलिनोमियल-टाइम हायरार्की (1991) में सिद्ध किया था एवं उन्हें 1998 का गोडेल पुरस्कार दिया गया था। प्रमेय बताता है, कि संपूर्ण PH ( | टोडा का प्रमेय परिणाम है जिसे [[होशिनोसुके टोडा]] ने अपने पेपर पीपी इज एज़ हार्ड एज़ द पोलिनोमियल-टाइम हायरार्की (1991) में सिद्ध किया था एवं उन्हें 1998 का गोडेल पुरस्कार दिया गया था। प्रमेय बताता है, कि संपूर्ण PH (समष्टिता) P<sup>PP</sup> में समाहित है; इसका तात्पर्य निकट से संबंधित कथन से है, कि PH, P<sup>#P</sup> में समाहित है। | ||
===इम्मरमैन-स्लीपेकेनी प्रमेय=== | ===इम्मरमैन-स्लीपेकेनी प्रमेय=== | ||
{{main|इमरमैन-स्ज़ेलेपेसेनी प्रमेय}} | {{main|इमरमैन-स्ज़ेलेपेसेनी प्रमेय}} | ||
इमरमैन-स्ज़ेलेपसेनी प्रमेय को 1987 में [[नील इमरमैन]] एवं रॉबर्ट सज़ेलेपसेनी द्वारा स्वतंत्र रूप से सिद्ध किया गया था, जिसके लिए उन्होंने 1995 का गोडेल पुरस्कार साझा किया था। अपने सामान्य रूप में प्रमेय बताता है कि किसी भी फलन s(n) ≥ log n के लिए [[NSPACE]](s(n)) = सह-NSPACE(s(n)) है। परिणाम को समान रूप से [[एनएल (जटिलता)|NL = co-NL ( | इमरमैन-स्ज़ेलेपसेनी प्रमेय को 1987 में [[नील इमरमैन]] एवं रॉबर्ट सज़ेलेपसेनी द्वारा स्वतंत्र रूप से सिद्ध किया गया था, जिसके लिए उन्होंने 1995 का गोडेल पुरस्कार साझा किया था। अपने सामान्य रूप में प्रमेय बताता है कि किसी भी फलन s(n) ≥ log n के लिए [[NSPACE]](s(n)) = सह-NSPACE(s(n)) है। परिणाम को समान रूप से [[एनएल (जटिलता)|NL = co-NL (समष्टिता)]] के रूप में बताया गया है; चूंकि यह विशेष विषय है, जब s(n) = log n, यह मानक [[पैडिंग तर्क]] द्वारा सामान्य प्रमेय का तात्पर्य करता है। परिणाम से दूसरी LBA समस्या हल हो गई। | ||
==शोध विषय== | ==शोध विषय== | ||
इस क्षेत्र में अनुसंधान की प्रमुख दिशाओं में सम्मिलित हैं:<ref name=jha/>* | इस क्षेत्र में अनुसंधान की प्रमुख दिशाओं में सम्मिलित हैं:<ref name=jha/>*समष्टिता वर्गों के विषय में विभिन्न अप्रचलित समस्याओं से उत्पन्न निहितार्थों का अध्ययन, | ||
*विभिन्न प्रकार की संसाधन-प्रतिबंधित [[कमी (जटिलता)]] एवं संबंधित पूर्ण भाषाओं का अध्ययन | *विभिन्न प्रकार की संसाधन-प्रतिबंधित [[कमी (जटिलता)|कमी (समष्टिता)]] एवं संबंधित पूर्ण भाषाओं का अध्ययन | ||
*डेटा के भंडारण एवं पहुंच के प्रणाली एवं विभिन्न प्रतिबंधों के परिणामों का अध्ययन | *डेटा के भंडारण एवं पहुंच के प्रणाली एवं विभिन्न प्रतिबंधों के परिणामों का अध्ययन | ||
Revision as of 15:47, 8 August 2023
कंप्यूटर विज्ञान के संरचनात्मक समष्टिता सिद्धांत में, संरचनात्मक समष्टिता सिद्धांत या बस संरचनात्मक समष्टिता व्यक्तिगत समस्याओं एवं एल्गोरिदम की संरचनात्मक समष्टिता के अतिरिक्त समष्टिता वर्गों का अध्ययन है। इसमें विभिन्न समष्टिता वर्गों की आंतरिक संरचनाओं एवं विभिन्न समष्टिता वर्गों के मध्य संबंधों का अनुसंधान सम्मिलित है।[1]
इतिहास
यह सिद्धांत इस प्रकार के पूर्व एवं अभी भी सबसे महत्वपूर्ण प्रश्न, P = NP समस्या को हल करने के प्रयासों (अभी भी विफल) के परिणामस्वरूप उभरा है। अधिकांश शोध P की धारणा के आधार पर किया जाता है, जो NP के समान नहीं है, एवं अधिक दूरगामी अनुमान पर आधारित है कि समष्टिता वर्गों का बहुपद समय पदानुक्रम अनंत है।[1]
महत्वपूर्ण परिणाम
संपीड़न प्रमेय
संपीड़न प्रमेय गणना योग्य कार्यों की समष्टिता के विषय में महत्वपूर्ण प्रमेय है।
प्रमेय बताता है, कि गणना योग्य सीमा के साथ कोई सबसे बड़ा समष्टिता वर्ग उपस्थित नहीं है, जिसमें सभी गणना योग्य कार्य सम्मिलित हैं।
अंतरिक्ष पदानुक्रम प्रमेय
अंतरिक्ष पदानुक्रम प्रमेय पृथक्करण परिणाम हैं, जो दिखाते हैं कि नियतात्मक एवं गैर-नियतात्मक दोनों मशीनें कुछ नियमो के अधीन, अधिक स्थान में (असममित रूप से) अधिक समस्याओं को हल कर सकती हैं। उदाहरण के लिए, नियतात्मक ट्यूरिंग मशीन स्पेस एन की तुलना में स्पेस n लॉग n में अधिक निर्णय समस्याओं को हल कर सकती है। समय के लिए कुछ सीमा तक शक्तिहीन अनुरूप प्रमेय समय पदानुक्रम प्रमेय हैं।
समय पदानुक्रम प्रमेय
समय पदानुक्रम प्रमेय ट्यूरिंग मशीनों पर समयबद्ध गणना के विषय में महत्वपूर्ण कथन हैं। अनौपचारिक रूप से, ये प्रमेय कहते हैं, कि अधिक समय दिए जाने पर, ट्यूरिंग मशीन अधिक समस्याओं का समाधान कर सकती है। उदाहरण के लिए, ऐसी समस्याएं हैं जिन्हें n2 समय के साथ हल किया जा सकता है, किन्तु n के साथ नहीं किया जा सकता है।
बहादुर-वज़ीरानी प्रमेय
वैलेंट-वज़ीरानी प्रमेय संरचनात्मक समष्टिता सिद्धांत में प्रमेय है। लेस्ली वैलेंट एवं विजय वज़ीरानी ने 1986 में प्रकाशित NP शीर्षक वाले अपने पेपर में यह सिद्ध किया था, कि अद्वितीय समाधानों की जानकारी ज्ञात करना उतना ही सरल है।[2] प्रमेय बताता है कि असंदिग्ध-SAT बहुपद समय एल्गोरिथ्म है, तो NP=RP (समष्टिता)। प्रमाण मुलमुले-वज़ीरानी अलगाव लेम्मा पर आधारित है, जिसे पश्चात में सैद्धांतिक कंप्यूटर विज्ञान में कई महत्वपूर्ण अनुप्रयोगों के लिए उपयोग किया गया था।
सिप्सर-लौटेमैन प्रमेय
सिप्सर-लौटेमैन प्रमेय या सिप्सर-गैक्स-लौटेमैन प्रमेय में कहा गया है कि परिबद्ध-त्रुटि संभाव्य बहुपद सीमा-त्रुटि संभाव्य बहुपद (BPP) समय, बहुपद पदानुक्रम में निहित है, एवं अधिक विशेष रूप से Σ2 ∩ Π2 है।
सैविच का प्रमेय
सैविच का प्रमेय, 1970 में वाल्टर सैविच द्वारा सिद्ध किया गया, नियतिवादी एवं गैर-नियतात्मक अंतरिक्ष समष्टिता के मध्य संबंध देता है। इसमें कहा गया है कि किसी भी फलन के लिए है।
टोडा का प्रमेय
टोडा का प्रमेय परिणाम है जिसे होशिनोसुके टोडा ने अपने पेपर पीपी इज एज़ हार्ड एज़ द पोलिनोमियल-टाइम हायरार्की (1991) में सिद्ध किया था एवं उन्हें 1998 का गोडेल पुरस्कार दिया गया था। प्रमेय बताता है, कि संपूर्ण PH (समष्टिता) PPP में समाहित है; इसका तात्पर्य निकट से संबंधित कथन से है, कि PH, P#P में समाहित है।
इम्मरमैन-स्लीपेकेनी प्रमेय
इमरमैन-स्ज़ेलेपसेनी प्रमेय को 1987 में नील इमरमैन एवं रॉबर्ट सज़ेलेपसेनी द्वारा स्वतंत्र रूप से सिद्ध किया गया था, जिसके लिए उन्होंने 1995 का गोडेल पुरस्कार साझा किया था। अपने सामान्य रूप में प्रमेय बताता है कि किसी भी फलन s(n) ≥ log n के लिए NSPACE(s(n)) = सह-NSPACE(s(n)) है। परिणाम को समान रूप से NL = co-NL (समष्टिता) के रूप में बताया गया है; चूंकि यह विशेष विषय है, जब s(n) = log n, यह मानक पैडिंग तर्क द्वारा सामान्य प्रमेय का तात्पर्य करता है। परिणाम से दूसरी LBA समस्या हल हो गई।
शोध विषय
इस क्षेत्र में अनुसंधान की प्रमुख दिशाओं में सम्मिलित हैं:[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.
