संरचनात्मक सम्मिश्र सिद्धांत: Difference between revisions

From Vigyanwiki
No edit summary
 
(18 intermediate revisions by 3 users not shown)
Line 1: Line 1:
{{about|कंप्यूटर विज्ञान का क्षेत्र|अनुप्रयुक्त गणित का क्षेत्र|संरचनात्मक जटिलता (अनुप्रयुक्त गणित)}}
[[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>


== इतिहास ==
== इतिहास ==
यह सिद्धांत इस प्रकार के पूर्व एवं अभी भी सबसे महत्वपूर्ण प्रश्न, P = NP समस्या को हल करने के प्रयासों (अभी भी विफल) के परिणामस्वरूप उभरा है। अधिकांश शोध P की धारणा के आधार पर किया जाता है, जो NP के समान नहीं है, एवं अधिक दूरगामी अनुमान पर आधारित है कि जटिलता वर्गों का [[बहुपद समय पदानुक्रम]] अनंत है।<ref name=jha/>
यह थ्योरी इस प्रकार के पूर्व एवं अभी भी सबसे महत्वपूर्ण प्रश्न, P = NP समस्या का समाधान करने के प्रयासों (अभी भी विफल) के परिणामस्वरूप है। रिसर्च, P की धारणा के आधार पर किया जाता है, जो NP के समान नहीं है, एवं अधिक फॉर रीचिंग कन्जेक्टर पर आधारित है कि कॉम्प्लेक्सिटी क्लासेज का [[बहुपद समय पदानुक्रम|पोलीनोमिकल्स टाइम हायरार्की]] अनंत है।<ref name=jha/>


== महत्वपूर्ण परिणाम ==
== महत्वपूर्ण परिणाम ==


===संपीड़न प्रमेय===
===कम्प्रेशन थ्योरम===
{{main|संपीड़न प्रमेय}}
{{main|कम्प्रेशन थ्योरम}}
[[संपीड़न प्रमेय]] [[गणना योग्य कार्य|गणना योग्य कार्यों]] की जटिलता के विषय में महत्वपूर्ण प्रमेय है।
[[संपीड़न प्रमेय|कम्प्रेशन थ्योरम]] [[गणना योग्य कार्य|कम्प्युटेबल फंक्शन]] की कॉम्प्लेक्सिटी के विषय में महत्वपूर्ण थ्योरम है।


प्रमेय बताता है, कि गणना योग्य सीमा के साथ कोई सबसे बड़ा जटिलता वर्ग उपस्थित नहीं है, जिसमें सभी गणना योग्य कार्य सम्मिलित हैं।
थ्योरम बताता है, कि कम्प्युटेबल सीमा के साथ कोई सबसे बड़ा कॉम्प्लेक्सिटी क्लास उपस्थित नहीं है, जिसमें सभी कम्प्युटेबल फंक्शन सम्मिलित हैं।


===अंतरिक्ष पदानुक्रम प्रमेय===
===स्पेस हायरार्की थ्योरम===
{{main|अंतरिक्ष पदानुक्रम प्रमेय}}
{{main|स्पेस हायरार्की थ्योरम}}
[[अंतरिक्ष पदानुक्रम प्रमेय]] पृथक्करण परिणाम हैं जो दिखाते हैं कि नियतात्मक एवं गैर-नियतात्मक दोनों मशीनें कुछ शर्तों के अधीन, अधिक स्थान में (असममित रूप से) अधिक समस्याओं को हल कर सकती हैं। उदाहरण के लिए, [[नियतात्मक ट्यूरिंग मशीन]] स्पेस एन की तुलना में स्पेस एन लॉग एन में अधिक [[निर्णय समस्या]]ओं को हल कर सकती है। समय के लिए कुछ हद तक कमजोर अनुरूप प्रमेय [[समय पदानुक्रम प्रमेय]] हैं।
[[अंतरिक्ष पदानुक्रम प्रमेय|स्पेस हायरार्की थ्योरम]] पृथक्करण परिणाम हैं, जो दिखाते हैं कि डेटर्मीनिस्टिक एवं नॉन-डेटर्मीनिस्टिक दोनों मशीनें कुछ नियमो के अधीन, अधिक स्पेस में (असममित रूप से) अधिक समस्याओं का समाधान कर सकती हैं। उदाहरण के लिए, [[नियतात्मक ट्यूरिंग मशीन|डेटर्मीनिस्टिक ट्यूरिंग मशीन]] स्पेस n की अपेक्षा में स्पेस n log n में अधिक [[निर्णय समस्या|डिसीजन प्रॉब्लम्स]] का समाधान कर सकती है। टाइम के लिए कुछ सीमा तक वीकर एनालोगस थ्योरम [[समय पदानुक्रम प्रमेय|टाइम हायरार्की थ्योरम]] हैं।


===समय पदानुक्रम प्रमेय===
===टाइम हायरार्की थ्योरम===
{{main|Time hierarchy theorem}}
{{main|टाइम हायरार्की थ्योरम}}
समय पदानुक्रम प्रमेय [[ट्यूरिंग मशीन]]ों पर समयबद्ध गणना के बारे में महत्वपूर्ण कथन हैं। अनौपचारिक रूप से, ये प्रमेय कहते हैं कि अधिक समय दिए जाने पर, ट्यूरिंग मशीन अधिक समस्याओं का समाधान कर सकती है। उदाहरण के लिए, ऐसी समस्याएं हैं जिन्हें n से हल किया जा सकता है<sup>2</sup>समय लेकिन nसमय नहीं।
टाइम हायरार्की थ्योरम [[ट्यूरिंग मशीन|ट्यूरिंग मशीनों]] पर समयबद्ध गणना के विषय में महत्वपूर्ण कथन हैं। अनौपचारिक रूप से, ये थ्योरम कहते हैं, कि अधिक टाइम दिए जाने पर, ट्यूरिंग मशीन अधिक समस्याओं का समाधान कर सकती है। उदाहरण के लिए, ऐसी समस्याएं हैं जिन्हें n<sup>2</sup> टाइम के साथ समाधान किया जा सकता है, किन्तु n के साथ नहीं किया जा सकता है।


===बहादुर-वज़ीरानी प्रमेय===
===वैलेंट-वज़ीरानी थ्योरम===
{{main|Valiant–Vazirani theorem}}
{{main|वैलेंट-वज़ीरानी थ्योरम}}
वैलेंट-वज़ीरानी प्रमेय संरचनात्मक जटिलता सिद्धांत में  प्रमेय है। [[लेस्ली वैलेंट]] एवं [[ विजय वज़ीरानी ]] ने 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 (जटिलता)।
प्रमाण मुलमुले-वज़ीरानी [[ अलगाव लेम्मा ]] पर आधारित है, जिसे बाद में [[सैद्धांतिक कंप्यूटर विज्ञान]] में कई महत्वपूर्ण अनुप्रयोगों के लिए उपयोग किया गया था।


===सिप्सर-लौटेमैन प्रमेय===
वैलेंट-वज़ीरानी थ्योरम स्ट्रक्चरल कॉम्प्लेक्सिटी थ्योरी में थ्योरम है। [[लेस्ली वैलेंट]] एवं [[ विजय वज़ीरानी |विजय वज़ीरानी]] ने 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|Sipser–Lautemann theorem}}
सिप्सर-लौटेमैन प्रमेय या सिप्सर-गैक्स-लौटेमैन प्रमेय में कहा गया है कि [[परिबद्ध-त्रुटि संभाव्य बहुपद]]|सीमा-त्रुटि संभाव्य बहुपद (बीपीपी) समय, [[बहुपद पदानुक्रम]] में निहित है, एवं अधिक विशेष रूप से Σ<sub>2</sub> ∩ पी<sub>2</sub>.


===सैविच का प्रमेय===
===सिप्सर-लौटेमैन थ्योरम===
{{main|Savitch's theorem}}
{{main|
सैविच का प्रमेय, 1970 में [[वाल्टर सैविच]] द्वारा सिद्ध किया गया, नियतिवादी एवं गैर-नियतात्मक [[अंतरिक्ष जटिलता]] के मध्य संबंध देता है। इसमें कहा गया है कि किसी भी फंक्शन के लिए <math>f\in\Omega(\log(n))</math>,
सिप्सर-लौटेमैन थ्योरम}}
सिप्सर-लौटेमैन थ्योरम या सिप्सर-गैक्स-लौटेमैन थ्योरम में कहा गया है कि [[परिबद्ध-त्रुटि संभाव्य बहुपद|बाउंडेड-एरर प्रोबेबिलिस्टिक पॉलिनोमियल]] (बीपीपी) टाइम, [[बहुपद पदानुक्रम|पोलीनोमिकल्स हायरार्की]] में निहित है, एवं अधिक विशेष रूप से Σ<sub>2</sub> ∩ Π<sub>2</sub> है। 
 
===सैविच का थ्योरम===
{{main|सैविच का थ्योरम}}
सैविच का थ्योरम, 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|टोडा का प्रमेय}}
 
टोडा का थ्योरम परिणाम है जिसे [[होशिनोसुके टोडा]] ने अपने पेपर पीपी इज एज़ हार्ड एज़ द पोलिनोमियल-टाइम हायरार्की (1991) में प्रूव किया था एवं उन्हें 1998 का ​​गोडेल पुरस्कार दिया गया था। थ्योरम बताता है, कि संपूर्ण PH (कॉम्प्लेक्सिटी) P<sup>PP</sup> में कंटेन है; इसका तात्पर्य संबंधित कथन से है, कि PH, P<sup>#P</sup> में कंटेन है।


'''टोडा का प्रमेय'''
===इम्मरमैन-स्ज़ेलेपेसेनी थ्योरम===
{{main|Toda's theorem}}
{{main|इमरमैन-स्ज़ेलेपेसेनी थ्योरम}}
टोडा का प्रमेय  परिणाम है जिसे [[होशिनोसुके टोडा]] ने अपने पेपर पीपी इज एज़ हार्ड एज़ द पोलिनोमियल-टाइम हायरार्की (1991) में सिद्ध किया था एवं उन्हें 1998 का ​​गोडेल पुरस्कार दिया गया था। प्रमेय बताता है कि संपूर्ण PH (जटिलता) P में समाहित है<sup>पीपी</sup>; इसका तात्पर्य निकट से संबंधित कथन से है, कि PH, P में समाहित है<sup>#पी</sup>.
इमरमैन-स्ज़ेलेपसेनी थ्योरम को 1987 में [[नील इमरमैन]] एवं रॉबर्ट सज़ेलेपसेनी द्वारा स्वतंत्र रूप से प्रूव किया गया था, जिसके लिए उन्होंने 1995 का गोडेल पुरस्कार प्रदान किया गया था। अपने सामान्य रूप में थ्योरम बताता है कि किसी भी फंक्शन s(n) ≥ log n के लिए [[NSPACE]](s(n)) = co-NSPACE(s(n)) है। परिणाम को समान रूप से [[एनएल (जटिलता)|NL = co-NL (कॉम्प्लेक्सिटी)]] के रूप में बताया गया है; चूंकि यह विशेष विषय है, जब s(n) = log n, यह मानक [[पैडिंग तर्क]] द्वारा सामान्य थ्योरम का तात्पर्य करता है। परिणाम से दूसरी एलबीए समस्या सॉल्व हो गई है।


===इम्मरमैन-स्लीपेकेनी प्रमेय===
==रिसर्च विषय==
{{main|Immerman–Szelepcsényi theorem}}
इस क्षेत्र में रिसर्च की प्रमुख दिशाओं में सम्मिलित हैं:<ref name=jha/>                                                                                                                                                   
इमरमैन-स्ज़ेलेपसेनी प्रमेय को 1987 में [[नील इमरमैन]] एवं रॉबर्ट सज़ेलेपसेनी द्वारा स्वतंत्र रूप से सिद्ध किया गया था, जिसके लिए उन्होंने 1995 का गोडेल पुरस्कार साझा किया था। अपने सामान्य रूप में प्रमेय बताता है कि किसी भी फ़ंक्शन s(n) ≥ log n के लिए [[NSPACE]](s(n)) = सह-NSPACE(s(n))। परिणाम को समान रूप से [[एनएल (जटिलता)]] = सह-एनएल के रूप में बताया गया है; हालाँकि यह विशेष मामला है जब s(n) = log n, यह  मानक [[पैडिंग तर्क]] द्वारा सामान्य प्रमेय का तात्पर्य करता है{{Citation needed|date=July 2010}}. परिणाम ने रैखिक परिबद्ध ऑटोमेटन#एलबीए समस्याओं को हल कर दिया।


==शोध विषय==
कॉम्प्लेक्सिटी क्लासेज के विषय में विभिन्न अनसॉल्वड प्रॉब्लम्स से उत्पन्न इम्प्लीकेशन का अध्ययन है।
इस क्षेत्र में अनुसंधान की प्रमुख दिशाओं में सम्मिलित हैं:<ref name=jha/>*जटिलता वर्गों के बारे में विभिन्न अनसुलझी समस्याओं से उत्पन्न निहितार्थों का अध्ययन
*विभिन्न प्रकार की रिसोर्स-रिस्ट्रिक्टेड [[कमी (जटिलता)|रिडक्शन (कॉम्प्लेक्सिटी)]] एवं संबंधित पूर्ण लैंग्वेज का अध्ययन है।
*विभिन्न प्रकार की संसाधन-प्रतिबंधित [[कमी (जटिलता)]] एवं संबंधित पूर्ण भाषाओं का अध्ययन
*स्टोरेज एवं डेटा तक पहुंच के प्रणाली एवं विभिन्न प्रतिबंधों के परिणामों का अध्ययन है।
*डेटा के भंडारण एवं पहुंच के तंत्र एवं विभिन्न प्रतिबंधों के परिणामों का अध्ययन


==संदर्भ==
==संदर्भ==
Line 58: Line 60:
[[Category: Machine Translated Page]]
[[Category: Machine Translated Page]]
[[Category:Created On 25/07/2023]]
[[Category:Created On 25/07/2023]]
[[Category:Vigyan Ready]]

Latest revision as of 22:34, 2 February 2024

पोलीनोमिकल्स टाइम हायरार्की का सचित्र प्रतिनिधित्व। एरो समावेशन को दर्शाते हैं।

कंप्यूटर विज्ञान के संरचनात्मक सम्मिश्र सिद्धांत (स्ट्रक्चरल कॉम्प्लेक्सिटी थ्योरी) में, स्ट्रक्चरल कॉम्प्लेक्सिटी थ्योरी या बस स्ट्रक्चरल कॉम्प्लेक्सिटी व्यक्तिगत समस्याओं एवं एल्गोरिदम की स्ट्रक्चरल कॉम्प्लेक्सिटी के अतिरिक्त कॉम्प्लेक्सिटी क्लासेज का अध्ययन है। इसमें विभिन्न कॉम्प्लेक्सिटी क्लासेज की इंटरनल स्ट्रक्चर एवं विभिन्न कॉम्प्लेक्सिटी क्लासेज के मध्य संबंधों का रिसर्च सम्मिलित है।[1]

इतिहास

यह थ्योरी इस प्रकार के पूर्व एवं अभी भी सबसे महत्वपूर्ण प्रश्न, P = NP समस्या का समाधान करने के प्रयासों (अभी भी विफल) के परिणामस्वरूप है। रिसर्च, P की धारणा के आधार पर किया जाता है, जो NP के समान नहीं है, एवं अधिक फॉर रीचिंग कन्जेक्टर पर आधारित है कि कॉम्प्लेक्सिटी क्लासेज का पोलीनोमिकल्स टाइम हायरार्की अनंत है।[1]

महत्वपूर्ण परिणाम

कम्प्रेशन थ्योरम

Main article: कम्प्रेशन थ्योरम

कम्प्रेशन थ्योरम कम्प्युटेबल फंक्शन की कॉम्प्लेक्सिटी के विषय में महत्वपूर्ण थ्योरम है।

थ्योरम बताता है, कि कम्प्युटेबल सीमा के साथ कोई सबसे बड़ा कॉम्प्लेक्सिटी क्लास उपस्थित नहीं है, जिसमें सभी कम्प्युटेबल फंक्शन सम्मिलित हैं।

स्पेस हायरार्की थ्योरम

Main article: स्पेस हायरार्की थ्योरम

स्पेस हायरार्की थ्योरम पृथक्करण परिणाम हैं, जो दिखाते हैं कि डेटर्मीनिस्टिक एवं नॉन-डेटर्मीनिस्टिक दोनों मशीनें कुछ नियमो के अधीन, अधिक स्पेस में (असममित रूप से) अधिक समस्याओं का समाधान कर सकती हैं। उदाहरण के लिए, डेटर्मीनिस्टिक ट्यूरिंग मशीन स्पेस n की अपेक्षा में स्पेस n log n में अधिक डिसीजन प्रॉब्लम्स का समाधान कर सकती है। टाइम के लिए कुछ सीमा तक वीकर एनालोगस थ्योरम टाइम हायरार्की थ्योरम हैं।

टाइम हायरार्की थ्योरम

Main article: टाइम हायरार्की थ्योरम

टाइम हायरार्की थ्योरम ट्यूरिंग मशीनों पर समयबद्ध गणना के विषय में महत्वपूर्ण कथन हैं। अनौपचारिक रूप से, ये थ्योरम कहते हैं, कि अधिक टाइम दिए जाने पर, ट्यूरिंग मशीन अधिक समस्याओं का समाधान कर सकती है। उदाहरण के लिए, ऐसी समस्याएं हैं जिन्हें n2 टाइम के साथ समाधान किया जा सकता है, किन्तु n के साथ नहीं किया जा सकता है।

वैलेंट-वज़ीरानी थ्योरम

Main article: वैलेंट-वज़ीरानी थ्योरम

वैलेंट-वज़ीरानी थ्योरम स्ट्रक्चरल कॉम्प्लेक्सिटी थ्योरी में थ्योरम है। लेस्ली वैलेंट एवं विजय वज़ीरानी ने 1986 में प्रकाशित NP टाइटल वाले अपने पेपर में यह प्रूव किया था, कि अद्वितीय समाधानों की जानकारी ज्ञात करना सरल है।[2] थ्योरम बताता है कि अनअंबिगुअस-सैट पोलीनोमिकल्स टाइम एल्गोरिथ्म है, तो NP=RP होता है। प्रमाण मुलमुले-वज़ीरानी आइसोलेशन लेम्मा पर आधारित है, जिसे पश्चात में सैद्धांतिक कंप्यूटर विज्ञान में कई महत्वपूर्ण अनुप्रयोगों के लिए उपयोग किया गया था।

सिप्सर-लौटेमैन थ्योरम

Main article: सिप्सर-लौटेमैन थ्योरम

सिप्सर-लौटेमैन थ्योरम या सिप्सर-गैक्स-लौटेमैन थ्योरम में कहा गया है कि बाउंडेड-एरर प्रोबेबिलिस्टिक पॉलिनोमियल (बीपीपी) टाइम, पोलीनोमिकल्स हायरार्की में निहित है, एवं अधिक विशेष रूप से Σ2 ∩ Π2 है।

सैविच का थ्योरम

Main article: सैविच का थ्योरम

सैविच का थ्योरम, 1970 में वाल्टर सैविच द्वारा प्रूव किया गया, निश्चयात्मक एवं नॉन-डेटर्मीनिस्टिक स्पेस कॉम्प्लेक्सिटी के मध्य संबंध प्रदान करता है। इसमें कहा गया है कि किसी भी फंक्शन के लिए

होता है।

टोडा का थ्योरम

Main article: टोडा का प्रमेय

टोडा का थ्योरम परिणाम है जिसे होशिनोसुके टोडा ने अपने पेपर पीपी इज एज़ हार्ड एज़ द पोलिनोमियल-टाइम हायरार्की (1991) में प्रूव किया था एवं उन्हें 1998 का ​​गोडेल पुरस्कार दिया गया था। थ्योरम बताता है, कि संपूर्ण PH (कॉम्प्लेक्सिटी) PPP में कंटेन है; इसका तात्पर्य संबंधित कथन से है, कि PH, P#P में कंटेन है।

इम्मरमैन-स्ज़ेलेपेसेनी थ्योरम

Main article: इमरमैन-स्ज़ेलेपेसेनी थ्योरम

इमरमैन-स्ज़ेलेपसेनी थ्योरम को 1987 में नील इमरमैन एवं रॉबर्ट सज़ेलेपसेनी द्वारा स्वतंत्र रूप से प्रूव किया गया था, जिसके लिए उन्होंने 1995 का गोडेल पुरस्कार प्रदान किया गया था। अपने सामान्य रूप में थ्योरम बताता है कि किसी भी फंक्शन s(n) ≥ log n के लिए NSPACE(s(n)) = co-NSPACE(s(n)) है। परिणाम को समान रूप से NL = co-NL (कॉम्प्लेक्सिटी) के रूप में बताया गया है; चूंकि यह विशेष विषय है, जब s(n) = log n, यह मानक पैडिंग तर्क द्वारा सामान्य थ्योरम का तात्पर्य करता है। परिणाम से दूसरी एलबीए समस्या सॉल्व हो गई है।

रिसर्च विषय

इस क्षेत्र में रिसर्च की प्रमुख दिशाओं में सम्मिलित हैं:[1]

कॉम्प्लेक्सिटी क्लासेज के विषय में विभिन्न अनसॉल्वड प्रॉब्लम्स से उत्पन्न इम्प्लीकेशन का अध्ययन है।

  • विभिन्न प्रकार की रिसोर्स-रिस्ट्रिक्टेड रिडक्शन (कॉम्प्लेक्सिटी) एवं संबंधित पूर्ण लैंग्वेज का अध्ययन है।
  • स्टोरेज एवं डेटा तक पहुंच के प्रणाली एवं विभिन्न प्रतिबंधों के परिणामों का अध्ययन है।

संदर्भ

  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.
  2. ↑ Valiant, L.; Vazirani, V. (1986). "एनपी अनूठे समाधानों का पता लगाने जितना आसान है" (PDF). Theoretical Computer Science. 47: 85–93. doi:10.1016/0304-3975(86)90135-0.
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=संरचनात्मक_सम्मिश्र_सिद्धांत&oldid=281523’