संरचनात्मक सम्मिश्र सिद्धांत: Difference between revisions
(Created page with "{{about|the area in computer science|the area in applied mathematics|Structural complexity (applied mathematics)}} Image:Polynomial time hierarchy.svg|250px|thumb|right|ब...") |
No edit summary |
||
| Line 2: | Line 2: | ||
[[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> | [[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> | ||
== इतिहास == | |||
==इतिहास== | |||
यह सिद्धांत इस प्रकार के पहले और अभी भी सबसे महत्वपूर्ण प्रश्न, पी = एनपी समस्या को हल करने के प्रयासों (अभी भी विफल) के परिणामस्वरूप उभरा है। अधिकांश शोध पी के एनपी के बराबर नहीं होने की धारणा और अधिक दूरगामी अनुमान के आधार पर किया जाता है कि जटिलता वर्गों का [[बहुपद समय पदानुक्रम]] अनंत है।<ref name=jha/> | यह सिद्धांत इस प्रकार के पहले और अभी भी सबसे महत्वपूर्ण प्रश्न, पी = एनपी समस्या को हल करने के प्रयासों (अभी भी विफल) के परिणामस्वरूप उभरा है। अधिकांश शोध पी के एनपी के बराबर नहीं होने की धारणा और अधिक दूरगामी अनुमान के आधार पर किया जाता है कि जटिलता वर्गों का [[बहुपद समय पदानुक्रम]] अनंत है।<ref name=jha/> | ||
== महत्वपूर्ण परिणाम == | |||
==महत्वपूर्ण परिणाम== | |||
===संपीड़न प्रमेय=== | ===संपीड़न प्रमेय=== | ||
{{main|Compression theorem}} | {{main|Compression theorem}} | ||
[[संपीड़न प्रमेय]] [[गणना योग्य कार्य]]ों की जटिलता के बारे में | [[संपीड़न प्रमेय]] [[गणना योग्य कार्य]]ों की जटिलता के बारे में महत्वपूर्ण प्रमेय है। | ||
प्रमेय बताता है कि गणना योग्य सीमा के साथ कोई सबसे बड़ा जटिलता वर्ग मौजूद नहीं है, जिसमें सभी गणना योग्य कार्य शामिल हैं। | प्रमेय बताता है कि गणना योग्य सीमा के साथ कोई सबसे बड़ा जटिलता वर्ग मौजूद नहीं है, जिसमें सभी गणना योग्य कार्य शामिल हैं। | ||
| Line 17: | Line 15: | ||
===अंतरिक्ष पदानुक्रम प्रमेय=== | ===अंतरिक्ष पदानुक्रम प्रमेय=== | ||
{{main|Space hierarchy theorem}} | {{main|Space hierarchy theorem}} | ||
[[अंतरिक्ष पदानुक्रम प्रमेय]] पृथक्करण परिणाम हैं जो दिखाते हैं कि नियतात्मक और गैर-नियतात्मक दोनों मशीनें कुछ शर्तों के अधीन, अधिक स्थान में (असममित रूप से) अधिक समस्याओं को हल कर सकती हैं। उदाहरण के लिए, | [[अंतरिक्ष पदानुक्रम प्रमेय]] पृथक्करण परिणाम हैं जो दिखाते हैं कि नियतात्मक और गैर-नियतात्मक दोनों मशीनें कुछ शर्तों के अधीन, अधिक स्थान में (असममित रूप से) अधिक समस्याओं को हल कर सकती हैं। उदाहरण के लिए, [[नियतात्मक ट्यूरिंग मशीन]] स्पेस एन की तुलना में स्पेस एन लॉग एन में अधिक [[निर्णय समस्या]]ओं को हल कर सकती है। समय के लिए कुछ हद तक कमजोर अनुरूप प्रमेय [[समय पदानुक्रम प्रमेय]] हैं। | ||
===समय पदानुक्रम प्रमेय=== | ===समय पदानुक्रम प्रमेय=== | ||
{{main|Time hierarchy theorem}} | {{main|Time hierarchy theorem}} | ||
समय पदानुक्रम प्रमेय [[ट्यूरिंग मशीन]]ों पर समयबद्ध गणना के बारे में महत्वपूर्ण कथन हैं। अनौपचारिक रूप से, ये प्रमेय कहते हैं कि अधिक समय दिए जाने पर, | समय पदानुक्रम प्रमेय [[ट्यूरिंग मशीन]]ों पर समयबद्ध गणना के बारे में महत्वपूर्ण कथन हैं। अनौपचारिक रूप से, ये प्रमेय कहते हैं कि अधिक समय दिए जाने पर, ट्यूरिंग मशीन अधिक समस्याओं का समाधान कर सकती है। उदाहरण के लिए, ऐसी समस्याएं हैं जिन्हें n से हल किया जा सकता है<sup>2</sup>समय लेकिन nसमय नहीं। | ||
===बहादुर-वज़ीरानी प्रमेय=== | ===बहादुर-वज़ीरानी प्रमेय=== | ||
{{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 35: | Line 33: | ||
===सैविच का प्रमेय=== | ===सैविच का प्रमेय=== | ||
{{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> | ||
'''टोडा का प्रमेय''' | |||
{{main|Toda's theorem}} | {{main|Toda's theorem}} | ||
टोडा का प्रमेय | टोडा का प्रमेय परिणाम है जिसे [[होशिनोसुके टोडा]] ने अपने पेपर पीपी इज एज़ हार्ड एज़ द पोलिनोमियल-टाइम हायरार्की (1991) में सिद्ध किया था और उन्हें 1998 का गोडेल पुरस्कार दिया गया था। प्रमेय बताता है कि संपूर्ण PH (जटिलता) P में समाहित है<sup>पीपी</sup>; इसका तात्पर्य निकट से संबंधित कथन से है, कि PH, P में समाहित है<sup>#पी</sup>. | ||
===इम्मरमैन-स्लीपेकेनी प्रमेय=== | ===इम्मरमैन-स्लीपेकेनी प्रमेय=== | ||
{{main|Immerman–Szelepcsényi theorem}} | {{main|Immerman–Szelepcsényi theorem}} | ||
इमरमैन-स्ज़ेलेपसेनी प्रमेय को 1987 में [[नील इमरमैन]] और रॉबर्ट सज़ेलेपसेनी द्वारा स्वतंत्र रूप से सिद्ध किया गया था, जिसके लिए उन्होंने 1995 का गोडेल पुरस्कार साझा किया था। अपने सामान्य रूप में प्रमेय बताता है कि किसी भी फ़ंक्शन s(n) ≥ log n के लिए [[NSPACE]](s(n)) = सह-NSPACE(s(n))। परिणाम को समान रूप से [[एनएल (जटिलता)]] = सह-एनएल के रूप में बताया गया है; हालाँकि यह विशेष मामला है जब s(n) = log n, यह | इमरमैन-स्ज़ेलेपसेनी प्रमेय को 1987 में [[नील इमरमैन]] और रॉबर्ट सज़ेलेपसेनी द्वारा स्वतंत्र रूप से सिद्ध किया गया था, जिसके लिए उन्होंने 1995 का गोडेल पुरस्कार साझा किया था। अपने सामान्य रूप में प्रमेय बताता है कि किसी भी फ़ंक्शन s(n) ≥ log n के लिए [[NSPACE]](s(n)) = सह-NSPACE(s(n))। परिणाम को समान रूप से [[एनएल (जटिलता)]] = सह-एनएल के रूप में बताया गया है; हालाँकि यह विशेष मामला है जब s(n) = log n, यह मानक [[पैडिंग तर्क]] द्वारा सामान्य प्रमेय का तात्पर्य करता है{{Citation needed|date=July 2010}}. परिणाम ने रैखिक परिबद्ध ऑटोमेटन#एलबीए समस्याओं को हल कर दिया। | ||
==शोध विषय== | ==शोध विषय== | ||
Revision as of 23:51, 4 August 2023
कंप्यूटर विज्ञान के कम्प्यूटेशनल जटिलता सिद्धांत में, संरचनात्मक जटिलता सिद्धांत या बस संरचनात्मक जटिलता व्यक्तिगत समस्याओं और एल्गोरिदम की कम्प्यूटेशनल जटिलता के बजाय जटिलता वर्गों का अध्ययन है। इसमें विभिन्न जटिलता वर्गों की आंतरिक संरचनाओं और विभिन्न जटिलता वर्गों के बीच संबंधों का अनुसंधान शामिल है।[1]
इतिहास
यह सिद्धांत इस प्रकार के पहले और अभी भी सबसे महत्वपूर्ण प्रश्न, पी = एनपी समस्या को हल करने के प्रयासों (अभी भी विफल) के परिणामस्वरूप उभरा है। अधिकांश शोध पी के एनपी के बराबर नहीं होने की धारणा और अधिक दूरगामी अनुमान के आधार पर किया जाता है कि जटिलता वर्गों का बहुपद समय पदानुक्रम अनंत है।[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.
