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

Revision as of 15:28, 8 August 2023

बहुपद समय पदानुक्रम का सचित्र प्रतिनिधित्व। तीर समावेशन को दर्शाते हैं।

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

इतिहास

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

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

संपीड़न प्रमेय

संपीड़न प्रमेय गणना योग्य कार्यों की जटिलता के विषय में महत्वपूर्ण प्रमेय है।

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

अंतरिक्ष पदानुक्रम प्रमेय

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

समय पदानुक्रम प्रमेय

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

बहादुर-वज़ीरानी प्रमेय

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

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

सिप्सर-लौटेमैन प्रमेय या सिप्सर-गैक्स-लौटेमैन प्रमेय में कहा गया है कि परिबद्ध-त्रुटि संभाव्य बहुपद|सीमा-त्रुटि संभाव्य बहुपद (बीपीपी) समय, बहुपद पदानुक्रम में निहित है, एवं अधिक विशेष रूप से Σ₂ ∩ पी₂.

सैविच का प्रमेय

सैविच का प्रमेय, 1970 में वाल्टर सैविच द्वारा सिद्ध किया गया, नियतिवादी एवं गैर-नियतात्मक अंतरिक्ष जटिलता के मध्य संबंध देता है। इसमें कहा गया है कि किसी भी फंक्शन के लिए $f\in \Omega (\log(n))$ ,

{\mathsf {NSPACE}}\left(f\left(n\right)\right)\subseteq {\mathsf {DSPACE}}\left(\left(f\left(n\right)\right)^{2}\right).

टोडा का प्रमेय

टोडा का प्रमेय परिणाम है जिसे होशिनोसुके टोडा ने अपने पेपर पीपी इज एज़ हार्ड एज़ द पोलिनोमियल-टाइम हायरार्की (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.

[jha-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.

[1]

[2]

@@ Line 15: / Line 15: @@
 ===अंतरिक्ष पदानुक्रम प्रमेय===
 {{main|अंतरिक्ष पदानुक्रम प्रमेय}}
-[[अंतरिक्ष पदानुक्रम प्रमेय]] पृथक्करण परिणाम हैं जो दिखाते हैं कि नियतात्मक एवं गैर-नियतात्मक दोनों मशीनें कुछ शर्तों के अधीन, अधिक स्थान में (असममित रूप से) अधिक समस्याओं को हल कर सकती हैं। उदाहरण के लिए,  [[नियतात्मक ट्यूरिंग मशीन]] स्पेस एन की तुलना में स्पेस एन लॉग एन में अधिक [[निर्णय समस्या]]ओं को हल कर सकती है। समय के लिए कुछ हद तक कमजोर अनुरूप प्रमेय [[समय पदानुक्रम प्रमेय]] हैं।
+[[अंतरिक्ष पदानुक्रम प्रमेय]] पृथक्करण परिणाम हैं, जो दिखाते हैं कि नियतात्मक एवं गैर-नियतात्मक दोनों मशीनें कुछ नियमो के अधीन, अधिक स्थान में (असममित रूप से) अधिक समस्याओं को हल कर सकती हैं। उदाहरण के लिए, [[नियतात्मक ट्यूरिंग मशीन]] स्पेस एन की तुलना में स्पेस n लॉग 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> प्रमेय बताता है कि असंदिग्ध-SAT बहुपद समय एल्गोरिथ्म है, तो NP=RP (जटिलता)। प्रमाण मुलमुले-वज़ीरानी [[ अलगाव लेम्मा |अलगाव लेम्मा]] पर आधारित है, जिसे पश्चात में [[सैद्धांतिक कंप्यूटर विज्ञान]] में कई महत्वपूर्ण अनुप्रयोगों के लिए उपयोग किया गया था।
-प्रमाण मुलमुले-वज़ीरानी [[ अलगाव लेम्मा ]] पर आधारित है, जिसे बाद में [[सैद्धांतिक कंप्यूटर विज्ञान]] में कई महत्वपूर्ण अनुप्रयोगों के लिए उपयोग किया गया था।
 ===सिप्सर-लौटेमैन प्रमेय===
-{{main|Sipser–Lautemann theorem}}
+{{main|
+सिप्सर-लुटेमैन प्रमेय}}
 सिप्सर-लौटेमैन प्रमेय या सिप्सर-गैक्स-लौटेमैन प्रमेय में कहा गया है कि [[परिबद्ध-त्रुटि संभाव्य बहुपद]]|सीमा-त्रुटि संभाव्य बहुपद (बीपीपी) समय, [[बहुपद पदानुक्रम]] में निहित है, एवं अधिक विशेष रूप से Σ<sub>2</sub> ∩ पी<sub>2</sub>.

Anonymous

Search

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

Namespaces

More

Page actions

Revision as of 15:28, 8 August 2023

Contents

इतिहास

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

संपीड़न प्रमेय

अंतरिक्ष पदानुक्रम प्रमेय

समय पदानुक्रम प्रमेय

बहादुर-वज़ीरानी प्रमेय

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

सैविच का प्रमेय

इम्मरमैन-स्लीपेकेनी प्रमेय

शोध विषय

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Revision as of 15:28, 8 August 2023

इतिहास

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

संपीड़न प्रमेय

अंतरिक्ष पदानुक्रम प्रमेय

समय पदानुक्रम प्रमेय

बहादुर-वज़ीरानी प्रमेय

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

सैविच का प्रमेय

इम्मरमैन-स्लीपेकेनी प्रमेय

शोध विषय

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Hidden categories