संरचनात्मक सम्मिश्र सिद्धांत: 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|संपीड़न प्रमेय}} | ||
[[संपीड़न प्रमेय]] [[गणना योग्य कार्य|गणना योग्य कार्यों]] की | [[संपीड़न प्रमेय]] [[गणना योग्य कार्य|गणना योग्य कार्यों]] की कम्प्लेक्सिटी के विषय में महत्वपूर्ण प्रमेय है। | ||
प्रमेय बताता है, कि गणना योग्य सीमा के साथ कोई सबसे बड़ा | प्रमेय बताता है, कि गणना योग्य सीमा के साथ कोई सबसे बड़ा कम्प्लेक्सिटी वर्ग उपस्थित नहीं है, जिसमें सभी गणना योग्य कार्य सम्मिलित हैं। | ||
=== | ===स्पेस पदानुक्रम प्रमेय=== | ||
{{main|अंतरिक्ष पदानुक्रम प्रमेय}} | {{main|अंतरिक्ष पदानुक्रम प्रमेय}} | ||
[[अंतरिक्ष पदानुक्रम प्रमेय]] पृथक्करण परिणाम हैं, जो दिखाते हैं कि नियतात्मक एवं गैर-नियतात्मक दोनों मशीनें कुछ नियमो के अधीन, अधिक स्थान में (असममित रूप से) अधिक समस्याओं को हल कर सकती हैं। उदाहरण के लिए, [[नियतात्मक ट्यूरिंग मशीन]] स्पेस | [[अंतरिक्ष पदानुक्रम प्रमेय|स्पेस पदानुक्रम प्रमेय]] पृथक्करण परिणाम हैं, जो दिखाते हैं कि नियतात्मक एवं गैर-नियतात्मक दोनों मशीनें कुछ नियमो के अधीन, अधिक स्थान में (असममित रूप से) अधिक समस्याओं को हल कर सकती हैं। उदाहरण के लिए, [[नियतात्मक ट्यूरिंग मशीन]] स्पेस n की अपेक्षा में स्पेस n log n में अधिक [[निर्णय समस्या|निर्णय समस्याओं]] को हल कर सकती है। समय के लिए कुछ सीमा तक शक्तिहीन अनुरूप प्रमेय [[समय पदानुक्रम प्रमेय]] हैं। | ||
===समय पदानुक्रम प्रमेय=== | ===समय पदानुक्रम प्रमेय=== | ||
| 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 का गोडेल पुरस्कार | इमरमैन-स्ज़ेलेपसेनी प्रमेय को 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 12:12, 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.
