संरचनात्मक सम्मिश्र सिद्धांत: 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 के समान नहीं है, एवं अधिक दूरगामी अनुमान पर आधारित है कि जटिलता वर्गों का [[बहुपद समय पदानुक्रम]] अनंत है।<ref name=jha/> | ||
== महत्वपूर्ण परिणाम == | == महत्वपूर्ण परिणाम == | ||
| Line 11: | Line 11: | ||
[[संपीड़न प्रमेय]] [[गणना योग्य कार्य]]ों की जटिलता के बारे में महत्वपूर्ण प्रमेय है। | [[संपीड़न प्रमेय]] [[गणना योग्य कार्य]]ों की जटिलता के बारे में महत्वपूर्ण प्रमेय है। | ||
प्रमेय बताता है कि गणना योग्य सीमा के साथ कोई सबसे बड़ा जटिलता वर्ग मौजूद नहीं है, जिसमें सभी गणना योग्य कार्य | प्रमेय बताता है कि गणना योग्य सीमा के साथ कोई सबसे बड़ा जटिलता वर्ग मौजूद नहीं है, जिसमें सभी गणना योग्य कार्य सम्मिलित हैं। | ||
===अंतरिक्ष पदानुक्रम प्रमेय=== | ===अंतरिक्ष पदानुक्रम प्रमेय=== | ||
{{main|Space hierarchy theorem}} | {{main|Space hierarchy theorem}} | ||
[[अंतरिक्ष पदानुक्रम प्रमेय]] पृथक्करण परिणाम हैं जो दिखाते हैं कि नियतात्मक | [[अंतरिक्ष पदानुक्रम प्रमेय]] पृथक्करण परिणाम हैं जो दिखाते हैं कि नियतात्मक एवं गैर-नियतात्मक दोनों मशीनें कुछ शर्तों के अधीन, अधिक स्थान में (असममित रूप से) अधिक समस्याओं को हल कर सकती हैं। उदाहरण के लिए, [[नियतात्मक ट्यूरिंग मशीन]] स्पेस एन की तुलना में स्पेस एन लॉग एन में अधिक [[निर्णय समस्या]]ओं को हल कर सकती है। समय के लिए कुछ हद तक कमजोर अनुरूप प्रमेय [[समय पदानुक्रम प्रमेय]] हैं। | ||
===समय पदानुक्रम प्रमेय=== | ===समय पदानुक्रम प्रमेय=== | ||
| Line 23: | Line 23: | ||
===बहादुर-वज़ीरानी प्रमेय=== | ===बहादुर-वज़ीरानी प्रमेय=== | ||
{{main|Valiant–Vazirani theorem}} | {{main|Valiant–Vazirani theorem}} | ||
वैलेंट-वज़ीरानी प्रमेय | वैलेंट-वज़ीरानी प्रमेय संरचनात्मक जटिलता सिद्धांत में प्रमेय है। [[लेस्ली वैलेंट]] एवं [[ विजय वज़ीरानी ]] ने 1986 में प्रकाशित एनपी नामक अपने पेपर में यह साबित किया था कि अद्वितीय समाधानों का पता लगाना उतना ही आसान है।<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|अस्पष्ट-SAT के विस्तार के लिए P (जटिलता) है, तो NP (जटिलता)=RP (जटिलता)। | प्रमेय बताता है कि यदि बूलियन संतुष्टि समस्या#SAT|अस्पष्ट-SAT के विस्तार के लिए P (जटिलता) है, तो NP (जटिलता)=RP (जटिलता)। | ||
प्रमाण मुलमुले-वज़ीरानी [[ अलगाव लेम्मा ]] पर आधारित है, जिसे बाद में [[सैद्धांतिक कंप्यूटर विज्ञान]] में कई महत्वपूर्ण अनुप्रयोगों के लिए उपयोग किया गया था। | प्रमाण मुलमुले-वज़ीरानी [[ अलगाव लेम्मा ]] पर आधारित है, जिसे बाद में [[सैद्धांतिक कंप्यूटर विज्ञान]] में कई महत्वपूर्ण अनुप्रयोगों के लिए उपयोग किया गया था। | ||
| Line 29: | Line 29: | ||
===सिप्सर-लौटेमैन प्रमेय=== | ===सिप्सर-लौटेमैन प्रमेय=== | ||
{{main|Sipser–Lautemann theorem}} | {{main|Sipser–Lautemann theorem}} | ||
सिप्सर-लौटेमैन प्रमेय या सिप्सर-गैक्स-लौटेमैन प्रमेय में कहा गया है कि [[परिबद्ध-त्रुटि संभाव्य बहुपद]]|सीमा-त्रुटि संभाव्य बहुपद (बीपीपी) समय, [[बहुपद पदानुक्रम]] में निहित है, | सिप्सर-लौटेमैन प्रमेय या सिप्सर-गैक्स-लौटेमैन प्रमेय में कहा गया है कि [[परिबद्ध-त्रुटि संभाव्य बहुपद]]|सीमा-त्रुटि संभाव्य बहुपद (बीपीपी) समय, [[बहुपद पदानुक्रम]] में निहित है, एवं अधिक विशेष रूप से Σ<sub>2</sub> ∩ पी<sub>2</sub>. | ||
===सैविच का प्रमेय=== | ===सैविच का प्रमेय=== | ||
{{main|Savitch's theorem}} | {{main|Savitch's theorem}} | ||
सैविच का प्रमेय, 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 39: | Line 39: | ||
'''टोडा का प्रमेय''' | '''टोडा का प्रमेय''' | ||
{{main|Toda's theorem}} | {{main|Toda's theorem}} | ||
टोडा का प्रमेय परिणाम है जिसे [[होशिनोसुके टोडा]] ने अपने पेपर पीपी इज एज़ हार्ड एज़ द पोलिनोमियल-टाइम हायरार्की (1991) में सिद्ध किया था | टोडा का प्रमेय परिणाम है जिसे [[होशिनोसुके टोडा]] ने अपने पेपर पीपी इज एज़ हार्ड एज़ द पोलिनोमियल-टाइम हायरार्की (1991) में सिद्ध किया था एवं उन्हें 1998 का गोडेल पुरस्कार दिया गया था। प्रमेय बताता है कि संपूर्ण PH (जटिलता) P में समाहित है<sup>पीपी</sup>; इसका तात्पर्य निकट से संबंधित कथन से है, कि PH, P में समाहित है<sup>#पी</sup>. | ||
===इम्मरमैन-स्लीपेकेनी प्रमेय=== | ===इम्मरमैन-स्लीपेकेनी प्रमेय=== | ||
{{main|Immerman–Szelepcsényi theorem}} | {{main|Immerman–Szelepcsényi theorem}} | ||
इमरमैन-स्ज़ेलेपसेनी प्रमेय को 1987 में [[नील इमरमैन]] | इमरमैन-स्ज़ेलेपसेनी प्रमेय को 1987 में [[नील इमरमैन]] एवं रॉबर्ट सज़ेलेपसेनी द्वारा स्वतंत्र रूप से सिद्ध किया गया था, जिसके लिए उन्होंने 1995 का गोडेल पुरस्कार साझा किया था। अपने सामान्य रूप में प्रमेय बताता है कि किसी भी फ़ंक्शन s(n) ≥ log n के लिए [[NSPACE]](s(n)) = सह-NSPACE(s(n))। परिणाम को समान रूप से [[एनएल (जटिलता)]] = सह-एनएल के रूप में बताया गया है; हालाँकि यह विशेष मामला है जब s(n) = log n, यह मानक [[पैडिंग तर्क]] द्वारा सामान्य प्रमेय का तात्पर्य करता है{{Citation needed|date=July 2010}}. परिणाम ने रैखिक परिबद्ध ऑटोमेटन#एलबीए समस्याओं को हल कर दिया। | ||
==शोध विषय== | ==शोध विषय== | ||
इस क्षेत्र में अनुसंधान की प्रमुख दिशाओं में | इस क्षेत्र में अनुसंधान की प्रमुख दिशाओं में सम्मिलित हैं:<ref name=jha/>*जटिलता वर्गों के बारे में विभिन्न अनसुलझी समस्याओं से उत्पन्न निहितार्थों का अध्ययन | ||
*विभिन्न प्रकार की संसाधन-प्रतिबंधित [[कमी (जटिलता)]] | *विभिन्न प्रकार की संसाधन-प्रतिबंधित [[कमी (जटिलता)]] एवं संबंधित पूर्ण भाषाओं का अध्ययन | ||
*डेटा के भंडारण | *डेटा के भंडारण एवं पहुंच के तंत्र एवं विभिन्न प्रतिबंधों के परिणामों का अध्ययन | ||
==संदर्भ== | ==संदर्भ== | ||
Revision as of 15:15, 8 August 2023
कंप्यूटर विज्ञान के संरचनात्मक जटिलता सिद्धांत में, संरचनात्मक जटिलता सिद्धांत या बस संरचनात्मक जटिलता व्यक्तिगत समस्याओं एवं एल्गोरिदम की संरचनात्मक जटिलता के अतिरिक्त जटिलता वर्गों का अध्ययन है। इसमें विभिन्न जटिलता वर्गों की आंतरिक संरचनाओं एवं विभिन्न जटिलता वर्गों के मध्य संबंधों का अनुसंधान सम्मिलित है।[1]
इतिहास
यह सिद्धांत इस प्रकार के पूर्व एवं अभी भी सबसे महत्वपूर्ण प्रश्न, P = NP समस्या को हल करने के प्रयासों (अभी भी विफल) के परिणामस्वरूप उभरा है। अधिकांश शोध P की धारणा के आधार पर किया जाता है, जो NP के समान नहीं है, एवं अधिक दूरगामी अनुमान पर आधारित है कि जटिलता वर्गों का बहुपद समय पदानुक्रम अनंत है।[1]
महत्वपूर्ण परिणाम
संपीड़न प्रमेय
संपीड़न प्रमेय गणना योग्य कार्यों की जटिलता के बारे में महत्वपूर्ण प्रमेय है।
प्रमेय बताता है कि गणना योग्य सीमा के साथ कोई सबसे बड़ा जटिलता वर्ग मौजूद नहीं है, जिसमें सभी गणना योग्य कार्य सम्मिलित हैं।
अंतरिक्ष पदानुक्रम प्रमेय
अंतरिक्ष पदानुक्रम प्रमेय पृथक्करण परिणाम हैं जो दिखाते हैं कि नियतात्मक एवं गैर-नियतात्मक दोनों मशीनें कुछ शर्तों के अधीन, अधिक स्थान में (असममित रूप से) अधिक समस्याओं को हल कर सकती हैं। उदाहरण के लिए, नियतात्मक ट्यूरिंग मशीन स्पेस एन की तुलना में स्पेस एन लॉग एन में अधिक निर्णय समस्याओं को हल कर सकती है। समय के लिए कुछ हद तक कमजोर अनुरूप प्रमेय समय पदानुक्रम प्रमेय हैं।
समय पदानुक्रम प्रमेय
समय पदानुक्रम प्रमेय ट्यूरिंग मशीनों पर समयबद्ध गणना के बारे में महत्वपूर्ण कथन हैं। अनौपचारिक रूप से, ये प्रमेय कहते हैं कि अधिक समय दिए जाने पर, ट्यूरिंग मशीन अधिक समस्याओं का समाधान कर सकती है। उदाहरण के लिए, ऐसी समस्याएं हैं जिन्हें n से हल किया जा सकता है2समय लेकिन nसमय नहीं।
बहादुर-वज़ीरानी प्रमेय
वैलेंट-वज़ीरानी प्रमेय संरचनात्मक जटिलता सिद्धांत में प्रमेय है। लेस्ली वैलेंट एवं विजय वज़ीरानी ने 1986 में प्रकाशित एनपी नामक अपने पेपर में यह साबित किया था कि अद्वितीय समाधानों का पता लगाना उतना ही आसान है।[2] प्रमेय बताता है कि यदि बूलियन संतुष्टि समस्या#SAT|अस्पष्ट-SAT के विस्तार के लिए P (जटिलता) है, तो NP (जटिलता)=RP (जटिलता)। प्रमाण मुलमुले-वज़ीरानी अलगाव लेम्मा पर आधारित है, जिसे बाद में सैद्धांतिक कंप्यूटर विज्ञान में कई महत्वपूर्ण अनुप्रयोगों के लिए उपयोग किया गया था।
सिप्सर-लौटेमैन प्रमेय
सिप्सर-लौटेमैन प्रमेय या सिप्सर-गैक्स-लौटेमैन प्रमेय में कहा गया है कि परिबद्ध-त्रुटि संभाव्य बहुपद|सीमा-त्रुटि संभाव्य बहुपद (बीपीपी) समय, बहुपद पदानुक्रम में निहित है, एवं अधिक विशेष रूप से Σ2 ∩ पी2.
सैविच का प्रमेय
सैविच का प्रमेय, 1970 में वाल्टर सैविच द्वारा सिद्ध किया गया, नियतिवादी एवं गैर-नियतात्मक अंतरिक्ष जटिलता के मध्य संबंध देता है। इसमें कहा गया है कि किसी भी फंक्शन के लिए ,
टोडा का प्रमेय
टोडा का प्रमेय परिणाम है जिसे होशिनोसुके टोडा ने अपने पेपर पीपी इज एज़ हार्ड एज़ द पोलिनोमियल-टाइम हायरार्की (1991) में सिद्ध किया था एवं उन्हें 1998 का गोडेल पुरस्कार दिया गया था। प्रमेय बताता है कि संपूर्ण PH (जटिलता) P में समाहित हैपीपी; इसका तात्पर्य निकट से संबंधित कथन से है, कि PH, P में समाहित है#पी.
इम्मरमैन-स्लीपेकेनी प्रमेय
इमरमैन-स्ज़ेलेपसेनी प्रमेय को 1987 में नील इमरमैन एवं रॉबर्ट सज़ेलेपसेनी द्वारा स्वतंत्र रूप से सिद्ध किया गया था, जिसके लिए उन्होंने 1995 का गोडेल पुरस्कार साझा किया था। अपने सामान्य रूप में प्रमेय बताता है कि किसी भी फ़ंक्शन s(n) ≥ log n के लिए NSPACE(s(n)) = सह-NSPACE(s(n))। परिणाम को समान रूप से एनएल (जटिलता) = सह-एनएल के रूप में बताया गया है; हालाँकि यह विशेष मामला है जब s(n) = log n, यह मानक पैडिंग तर्क द्वारा सामान्य प्रमेय का तात्पर्य करता है[citation needed]. परिणाम ने रैखिक परिबद्ध ऑटोमेटन#एलबीए समस्याओं को हल कर दिया।
शोध विषय
इस क्षेत्र में अनुसंधान की प्रमुख दिशाओं में सम्मिलित हैं:[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.
