संरचनात्मक सम्मिश्र सिद्धांत: 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/> | ||
== महत्वपूर्ण परिणाम == | == महत्वपूर्ण परिणाम == | ||
=== | ===कम्प्रेशन प्रमेय=== | ||
{{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> प्रमेय बताता है कि असंदिग्ध-सैट बहुपद समय एल्गोरिथ्म है, तो NP=RP (कॉम्प्लेक्सिटी)। प्रमाण मुलमुले-वज़ीरानी [[ अलगाव लेम्मा |अलगाव लेम्मा]] पर आधारित है, जिसे पश्चात में [[सैद्धांतिक कंप्यूटर विज्ञान]] में कई महत्वपूर्ण अनुप्रयोगों के लिए उपयोग किया गया था। | ||
===सिप्सर-लौटेमैन प्रमेय=== | ===सिप्सर-लौटेमैन प्रमेय=== | ||
{{main| | {{main| | ||
सिप्सर- | सिप्सर-लौटेमैन प्रमेय}} | ||
सिप्सर-लौटेमैन प्रमेय या सिप्सर-गैक्स-लौटेमैन प्रमेय में कहा गया है कि [[परिबद्ध-त्रुटि संभाव्य बहुपद]] सीमा- | सिप्सर-लौटेमैन प्रमेय या सिप्सर-गैक्स-लौटेमैन प्रमेय में कहा गया है कि [[परिबद्ध-त्रुटि संभाव्य बहुपद|परिबद्ध-एरर संभाव्य बहुपद]] सीमा-एरर संभाव्य बहुपद (बीपीपी) समय, [[बहुपद पदानुक्रम]] में निहित है, एवं अधिक विशेष रूप से Σ<sub>2</sub> ∩ Π<sub>2</sub> है। | ||
===सैविच का प्रमेय=== | ===सैविच का प्रमेय=== | ||
{{main|सैविच का प्रमेय}} | {{main|सैविच का प्रमेय}} | ||
सैविच का प्रमेय, 1970 में [[वाल्टर सैविच]] द्वारा सिद्ध किया गया, नियतिवादी एवं गैर-नियतात्मक [[अंतरिक्ष जटिलता|स्पेस | सैविच का प्रमेय, 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)) = co-NSPACE(s(n)) है। परिणाम को समान रूप से [[एनएल (जटिलता)|NL = co-NL ( | इमरमैन-स्ज़ेलेपसेनी प्रमेय को 1987 में [[नील इमरमैन]] एवं रॉबर्ट सज़ेलेपसेनी द्वारा स्वतंत्र रूप से सिद्ध किया गया था, जिसके लिए उन्होंने 1995 का गोडेल पुरस्कार प्रदान किया गया था। अपने सामान्य रूप में प्रमेय बताता है कि किसी भी फंक्शन s(n) ≥ log n के लिए [[NSPACE]](s(n)) = co-NSPACE(s(n)) है। परिणाम को समान रूप से [[एनएल (जटिलता)|NL = co-NL (कॉम्प्लेक्सिटी)]] के रूप में बताया गया है; चूंकि यह विशेष विषय है, जब s(n) = log n, यह मानक [[पैडिंग तर्क]] द्वारा सामान्य प्रमेय का तात्पर्य करता है। परिणाम से दूसरी एलबीए समस्या हल हो गई है। | ||
==शोध विषय== | ==शोध विषय== | ||
इस क्षेत्र में अनुसंधान की प्रमुख दिशाओं में सम्मिलित हैं:<ref name=jha/> | इस क्षेत्र में अनुसंधान की प्रमुख दिशाओं में सम्मिलित हैं:<ref name=jha/> कॉम्प्लेक्सिटी वर्गों के विषय में विभिन्न अप्रचलित समस्याओं से उत्पन्न निहितार्थों का अध्ययन है। | ||
*विभिन्न प्रकार की संसाधन-प्रतिबंधित [[कमी (जटिलता)|कमी ( | *विभिन्न प्रकार की संसाधन-प्रतिबंधित [[कमी (जटिलता)|कमी (कॉम्प्लेक्सिटी)]] एवं संबंधित पूर्ण लैंग्वेज का अध्ययन है। | ||
*स्टोरेज एवं डेटा तक पहुंच के प्रणाली एवं विभिन्न प्रतिबंधों के परिणामों का अध्ययन है। | *स्टोरेज एवं डेटा तक पहुंच के प्रणाली एवं विभिन्न प्रतिबंधों के परिणामों का अध्ययन है। | ||
Revision as of 13:24, 18 August 2023
कंप्यूटर विज्ञान के स्ट्रक्चरल कॉम्प्लेक्सिटी थ्योरी में, संरचनात्मक कॉम्प्लेक्सिटी सिद्धांत या बस संरचनात्मक कॉम्प्लेक्सिटी व्यक्तिगत समस्याओं एवं एल्गोरिदम की संरचनात्मक कॉम्प्लेक्सिटी के अतिरिक्त कॉम्प्लेक्सिटी वर्गों का अध्ययन है। इसमें विभिन्न कॉम्प्लेक्सिटी वर्गों की आंतरिक संरचनाओं एवं विभिन्न कॉम्प्लेक्सिटी वर्गों के मध्य संबंधों का अनुसंधान सम्मिलित है।[1]
इतिहास
यह सिद्धांत इस प्रकार के पूर्व एवं अभी भी सबसे महत्वपूर्ण प्रश्न, P = NP समस्या को हल करने के प्रयासों (अभी भी विफल) के परिणामस्वरूप उभरा है। अधिकांश शोध P की धारणा के आधार पर किया जाता है, जो NP के समान नहीं है, एवं अधिक दूरगामी अनुमान पर आधारित है कि कॉम्प्लेक्सिटी वर्गों का बहुपद समय पदानुक्रम अनंत है।[1]
महत्वपूर्ण परिणाम
कम्प्रेशन प्रमेय
कम्प्रेशन प्रमेय गणना योग्य कार्यों की कॉम्प्लेक्सिटी के विषय में महत्वपूर्ण प्रमेय है।
प्रमेय बताता है, कि गणना योग्य सीमा के साथ कोई सबसे बड़ा कॉम्प्लेक्सिटी वर्ग उपस्थित नहीं है, जिसमें सभी गणना योग्य कार्य सम्मिलित हैं।
स्पेस पदानुक्रम प्रमेय
स्पेस पदानुक्रम प्रमेय पृथक्करण परिणाम हैं, जो दिखाते हैं कि नियतात्मक एवं गैर-नियतात्मक दोनों मशीनें कुछ नियमो के अधीन, अधिक स्थान में (असममित रूप से) अधिक समस्याओं को हल कर सकती हैं। उदाहरण के लिए, नियतात्मक ट्यूरिंग मशीन स्पेस n की अपेक्षा में स्पेस n log n में अधिक निर्णय समस्याओं को हल कर सकती है। समय के लिए कुछ सीमा तक शक्तिहीन अनुरूप प्रमेय समय पदानुक्रम प्रमेय हैं।
समय पदानुक्रम प्रमेय
समय पदानुक्रम प्रमेय ट्यूरिंग मशीनों पर समयबद्ध गणना के विषय में महत्वपूर्ण कथन हैं। अनौपचारिक रूप से, ये प्रमेय कहते हैं, कि अधिक समय दिए जाने पर, ट्यूरिंग मशीन अधिक समस्याओं का समाधान कर सकती है। उदाहरण के लिए, ऐसी समस्याएं हैं जिन्हें n2 समय के साथ हल किया जा सकता है, किन्तु n के साथ नहीं किया जा सकता है।
बहादुर-वज़ीरानी प्रमेय
वैलेंट-वज़ीरानी प्रमेय संरचनात्मक कॉम्प्लेक्सिटी सिद्धांत में प्रमेय है। लेस्ली वैलेंट एवं विजय वज़ीरानी ने 1986 में प्रकाशित NP शीर्षक वाले अपने पेपर में यह सिद्ध किया था, कि अद्वितीय समाधानों की जानकारी ज्ञात करना सरल है।[2] प्रमेय बताता है कि असंदिग्ध-सैट बहुपद समय एल्गोरिथ्म है, तो NP=RP (कॉम्प्लेक्सिटी)। प्रमाण मुलमुले-वज़ीरानी अलगाव लेम्मा पर आधारित है, जिसे पश्चात में सैद्धांतिक कंप्यूटर विज्ञान में कई महत्वपूर्ण अनुप्रयोगों के लिए उपयोग किया गया था।
सिप्सर-लौटेमैन प्रमेय
सिप्सर-लौटेमैन प्रमेय या सिप्सर-गैक्स-लौटेमैन प्रमेय में कहा गया है कि परिबद्ध-एरर संभाव्य बहुपद सीमा-एरर संभाव्य बहुपद (बीपीपी) समय, बहुपद पदानुक्रम में निहित है, एवं अधिक विशेष रूप से Σ2 ∩ Π2 है।
सैविच का प्रमेय
सैविच का प्रमेय, 1970 में वाल्टर सैविच द्वारा सिद्ध किया गया, नियतिवादी एवं गैर-नियतात्मक स्पेस कॉम्प्लेक्सिटी के मध्य संबंध देता है। इसमें कहा गया है कि किसी भी फंक्शन के लिए है।
टोडा का प्रमेय
टोडा का प्रमेय परिणाम है जिसे होशिनोसुके टोडा ने अपने पेपर पीपी इज एज़ हार्ड एज़ द पोलिनोमियल-टाइम हायरार्की (1991) में सिद्ध किया था एवं उन्हें 1998 का गोडेल पुरस्कार दिया गया था। प्रमेय बताता है, कि संपूर्ण PH (कॉम्प्लेक्सिटी) PPP में समाहित है; इसका तात्पर्य संबंधित कथन से है, कि 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.
