Vigyanwiki - User contributions [en-gb]

हॉट स्पॉट (कंप्यूटर प्रोग्रामिंग)

2024-02-02T17:07:54Z

Indicwiki: 9 revisions imported from :alpha:हॉट_स्पॉट_(कंप्यूटर_प्रोग्रामिंग)

{{Other uses|हॉटस्पॉट (बहुविकल्पी)#कंप्यूटिंग}}
[[कंप्यूटर विज्ञान|कंप्यूटर साइंस]] में '''हॉट स्पॉट''' को सामान्यतः [[कंप्यूटर प्रोग्राम]] के क्षेत्र के रूप में परिभाषित किया जाता है जहां एक्सेक्यूटेड इंस्ट्रक्शन का हाई प्रोपोरशन होता है या जहां प्रोग्राम के एक्सेक्यूशन के टाइम सबसे अधिक टाइम स्पेंट होता है (आवश्यक नहीं कि वही वर्णन हो क्योंकि कुछ इंस्ट्रक्शन दूसरों की अपेक्षा फ़ास्ट होते हैं)।

यदि किसी प्रोग्राम को रैंडम टाइप से इंटेरपटेड किया जाता है, तो [[ कार्यक्रम गणक |प्रोग्राम काउंटर]] (एक्सेक्यूटेड किए जाने वाले अगले इंस्ट्रक्शन के लिए [[ सूचक (कंप्यूटर प्रोग्रामिंग) |पॉइंटर (कंप्यूटर प्रोग्रामिंग)]] ) में प्रायः निश्चित लिमिट के अंदर इंस्ट्रक्शन का एड्रेस सम्मिलित होता है, जो संभवतः उस कोड को इंडीकेट करता है जिसे ऑप्टिमाइजेशन की आवश्यकता होती है या यहां तक कि 'टाइट' [[ CPU |सीपीयू]] [[लूप (कंप्यूटिंग)]] के प्रजेंस का सिग्नल भी मिलता है। यह सरल टेक्निक अत्यधिक उपयोग किए जाने वाले इंस्ट्रक्शन का ज्ञात कर सकती है, चूँकि अधिक सोफिस्टिकेटेड मेथड, जैसे इंस्ट्रक्शन सेट सिमुलेटर या [[प्रोफाइलिंग (कंप्यूटर प्रोग्रामिंग)]], इसे अधिक करेक्ट और कोंस्टीटेंटली से प्राप्त करते हैं।

==हॉट स्पॉट को ज्ञात करने का इतिहास==
कंप्यूटर साइंटिस्ट [[डोनाल्ड नुथ]] ने 1996 में डॉ. डॉब्स जर्नल के लिए साक्षात्कार में जम्प ट्रेस के साथ अपनी प्रथम आकस्मिक भेंट का वर्णन करते हुए कहा:

60 के दशक में, किसी ने 'जंप ट्रेस' की अवधारणा का आविष्कार किया था। यह प्रोग्राम के [[मशीन कोड]] को परिवर्तित करने का उपाय था जिससे यह नियंत्रण बनाए रखने के लिए ब्रांच या जंप इंस्ट्रक्शन को परिवर्तित करे, जिससे आप टाइम में प्रत्येक इंस्ट्रक्शन की व्याख्या करने के अतिरिक्त प्रोग्राम को अधिक तीव्र गति से एक्सेक्यूटेड कर सकें और फ़ाइल में रिकॉर्ड कर सकें जहां प्रोग्राम अनुक्रमिकता से पृथक हो गया है। इस फ़ाइल को संसाधित करके आप यह ज्ञात कर सकते हैं कि प्रोग्राम अपना अधिकांश टाइम कहाँ व्यतीत कर रहा है। इसलिए प्रथम दिन जब हमारे पास यह सॉफ़्टवेयर चल रहा था, हमने इसे अपने [[फोरट्रान]] [[ संकलक |संकलक]] पर प्रारम्भ किया, जो मुझे लगता है कि उन दिनों [[नियंत्रण डेटा निगम]] द्वारा आपूर्ति किया गया था। हमने पाया कि यह अपना 87 प्रतिशत टाइम [[टिप्पणी (कंप्यूटर प्रोग्रामिंग)]] पढ़ने में व्यतीत कर रहा था I इसका कारण यह था कि यह कोड सिस्टम से दूसरे कोड सिस्टम में अनुवाद कर रहा था।<ref>[http://www.ntg.nl/maps/16/14.pdf Jack Woehr: An interview with Donald Knuth, April 1996.]</ref>

===पुनरावृत्ति===
ऊपर दिया गया उदाहरण यह स्पष्ट करता है कि प्रभावी हॉट स्पॉट को ज्ञात करना प्रायः पुनरावृत्ति प्रक्रिया है और इसे सदैव किया जाना चाहिए (केवल यह स्वीकार करने के अतिरिक्त कि प्रोग्राम उचित प्रदर्शन कर रहा है)। सभी बाह्य प्रसंस्करण को समाप्त करने के पश्चात् (उदाहरण के लिए सभी एम्बेडेड टिप्पणियों को विस्थापित करके), नया रनटाइम विश्लेषण अनुवाद में वास्तविक हॉट स्पॉट का अधिक त्रुटिहीन रूप से ज्ञात करेगा। यदि किसी भी हॉट स्पॉट का ज्ञात नहीं किया गया होता, तो संभवतः अनेक मशीनों पर अनेक वर्षों तक प्रोग्राम ने आवश्यकता से कहीं अधिक संसाधनों का उपभोग किया होता, बिना किसी को भी इसके सम्बन्ध में पूर्ण रूप से ज्ञात चले ही।

==हॉट स्पॉट डिटेक्टर के रूप में अनुदेश सेट सिमुलेशन==
इंस्ट्रक्शन सेट सिम्युलेटर का उपयोग किसी विशेष इंस्ट्रक्शन के एक्सेक्यूटेड होने पर प्रत्येक कैलकुलेशन करने के लिए किया जा सकता है और पश्चात् में या तो ऑन-स्क्रीन डिस्प्ले, प्रिंटेड प्रोग्राम लिस्टिंग (कैलकुलेशन और कुल इंस्ट्रक्शन पाथ लंबाई की प्रतिशतता के साथ) या भिन्न रिपोर्ट बनाई जा सकती है, जो त्रुटिहीन रूप से प्रदर्शित करती है कि सबसे अधिक संख्या में इंस्ट्रक्शन कहां हुए है। यह केवल हॉट स्पॉट का सापेक्ष दृश्य प्रदान करता है (इंस्ट्रक्शन स्टेप पर्सपेक्टिव से) क्योंकि अधिकांश इंस्ट्रक्शन में अनेक मशीनों पर भिन्न-भिन्न टाइम होता है। तत्पश्चात भी यह अत्यधिक उपयोग किए जाने वाले कोड का माप प्रदान करता है और एल्गोरिथ्म को ट्यून करते टाइम अपने आप में अधिक उपयोगी होता है।

==यह भी देखें==
*प्रोफाइलिंग (कंप्यूटर प्रोग्रामिंग)

==संदर्भ==
{{Reflist}}
[[Category: सॉफ्टवेयर अनुकूलन]]

[[Category: Machine Translated Page]]
[[Category:Created On 25/07/2023]]
[[Category:Vigyan Ready]]

हाउसकीपिंग (कंप्यूटिंग)

2024-02-02T17:07:50Z

Indicwiki: 8 revisions imported from :alpha:हाउसकीपिंग_(कंप्यूटिंग)

[[कंप्यूटर प्रोग्रामिंग]] में, '''हाउसकीपिंग''' या तो यूजर द्वारा रीटर्न कोड के ब्लॉक (जैसे [[सबरूटीन]] या फ़ंक्शन (कंप्यूटर विज्ञान), कभी-कभी फ़ंक्शन प्रस्तावना के रूप में) के एंट्री और एग्जिट पर या किसी अन्य ऑटोमेटेड या मैन्युअल सॉफ़्टवेयर प्रोसेस से जुड़ा होता है जिसके द्वारा उपयोग के पश्चात कंप्यूटर को साफ किया जाता है (उदाहरण के लिए [[ आभासी मेमोरी |वर्चुअल मेमोरी]] जैसे रिसोर्सेज को फ्री करना)। इसमें यूजर की गतिविधियों के परिणामस्वरूप सिस्टम द्वारा बनाए गए लॉग को रिमूव या स्टोर करने, या टेम्पररी फ़ाइलों में रिमूव जैसी गतिविधियां सम्मिलित हो सकती हैं जो अन्यथा केवल स्थान ले सकती हैं। हाउसकीपिंग को आवश्यक कार्य के रूप में वर्णित किया जा सकता है, जो किसी विशेष कंप्यूटर की सामान्य गतिविधि को करने के लिए आवश्यक है किंतु आवश्यक नहीं कि यह [[कलन विधि|एल्गोरिथम विधि]] का भाग हो।<ref>[http://www.computerhope.com/jargon/h/housekee.htm "Housekeeping"], ComputerHope.Com. Accessed July 20, 2009</ref> [[डिस्क भंडारण|डिस्क स्टोर]] को साफ़ करने के लिए, यूटिलिटी सॉफ़्टवेयर सामान्यतः इस उद्देश्य के लिए उपस्थित होते हैं जैसे डेटा कम्प्रेशन सॉफ़्टवेयर - फ़ाइलों को रिलीज़ और डिस्क स्थान और [[defragmentation|डीफ़्रेग्मेंटेशन]] प्रोग्राम को फ्री करने के लिए, डिस्क प्रदर्शन को इम्प्रूव करने के लिए किया जाता है।<ref>[http://www.namastecafe.com/computer/housekeep.htm "Basic Computer Housekeeping Tips"]. Accessed July 20, 2009</ref>

== उदाहरण ==
हाउसकीपिंग में निम्नलिखित गतिविधियाँ सम्मिलित हो सकती हैं (किंतु यह इन्हीं तक सीमित नहीं है):
* सेविंग और रिस्टोरिंग के लिए प्रोग्राम स्थिति को सेव और रिस्टोर करना (सामान्य प्रयोजन रजिस्टर और रिटर्न एड्रेस सहित)।
* स्टैक पर लोकल मेमोरी प्राप्त करना।
* किसी प्रोग्राम या फ़ंक्शन के प्रारंभ में लोकल वेरिएबल्स को प्रारंभ करना।
* किसी फ़ंक्शन से बाहर निकलने पर स्टैक पर लोकल मेमोरी को फ्री करना।
*[[कचरा संग्रहण (कंप्यूटर विज्ञान)|गार्बेज कलेक्शन (कंप्यूटर विज्ञान)]]
* [[डेटा रूपांतरण|डेटा कन्वर्शन]]
* [[बैकअप]] और/या अनावश्यक फ़ाइलों और [[सॉफ़्टवेयर]] को रिमूव करना।
* डिस्क मेंटेनेंस यूटिलिटी का एक्सेक्यूशन (उदाहरण के लिए [[माइक्रोसॉफ्ट स्कैनडिस्क]], हार्ड ड्राइव डीफ्रैग्मेंटर्स, [[एंटीवायरस सॉफ्टवेयर]])

==यह भी देखें==
* [[कम्प्यूटेशनल ओवरहेड]]
* सबरूटीन

== संदर्भ ==
<references/>
[[Category: कंप्यूटर का प्रदर्शन]]

{{computing-stub}}

[[Category: Machine Translated Page]]
[[Category:Created On 25/07/2023]]
[[Category:Vigyan Ready]]

सैट सॉल्वर

2024-02-02T17:07:44Z

Indicwiki: 23 revisions imported from :alpha:सैट_सॉल्वर

{{Short description|Computer program for the Boolean satisfiability problem}}
[[कंप्यूटर विज्ञान]] एवं फॉर्मल मेथड्स में, '''सैट सॉल्वर''' [[कंप्यूटर प्रोग्राम]] है जिसका उद्देश्य बूलियन [[संतुष्टि|सेटिस्फिअबिलिटी प्रॉब्लम]] को सॉल्व करना है। [[बूलियन डेटा प्रकार|बूलियन डेटा टाइप]] वेरिएबल, जैसे (''x'' या ''y'') एवं (''x'' या ''y'' नहीं) पर फार्मूला इनपुट करने पर, सैट सॉल्वर आउटपुट देता है कि क्या फार्मूला सेटिसफीएबल है, जिसका अर्थ है कि ''x'' एवं ''y'' की पॉसिबल वैल्यूज हैं जो फॉर्मूले को ट्रू या अनसेटिसफीएबल बनाती हैं, जिसका अर्थ है कि ''x'' एवं ''y'' की ऐसी कोई वैल्यूज नहीं हैं। इस विषय में, ''x'' ट्रू होने पर फार्मूला सेटिसफीएबल होता है, इसलिए सॉल्वर को सेटिसफीएबल रिटर्न करना चाहिए। 1960 के दशक में सैट के लिए [[कलन विधि|एल्गोरिदम]] के प्रारम्भ के पश्चात से, आधुनिक सैट सॉल्वर कुशलतापूर्वक कार्य करने के लिए अधिक संख्या में हयूरिस्टिक्स एवं प्रोग्राम ऑप्टिमाइजेशन को सम्मिलित करते हुए काम्प्लेक्स [[सॉफ़्टवेयर]] आर्टिफैक्ट्स में विकसित हो गए हैं।

कुक-लेविन थ्योरम के रूप में जाने जाने वाले परिणाम के अनुसार, बूलियन सटिस्फाबिलिटी सामान्य रूप से एनपी-पूर्ण प्रॉब्लम है। परिणामस्वरूप, केवल घातीय वर्स्ट केस कम्प्लेक्सिटी एल्गोरिदम ही ज्ञात हैं। इसके अतिरिक्त, 2000 के दशक के समय सैट के लिए एफिशिएंट एवं स्केलेबल एल्गोरिदम विकसित किए गए, जिन्होंने हजारों वेरिएबल एवं लाखों कंस्ट्रेंट्स से जुड़े प्रॉब्लम उदाहरणों को स्वचालित रूप से सॉल्व करने की क्षमता में आकस्मिक प्रगति में योगदान दिया है।<ref name="Codish.Ohrimenko.Stuckey.2007">{{citation|title=Principles and Practice of Constraint Programming – CP 2007|series=Lecture Notes in Computer Science|volume=4741|year=2007|pages=544–558|contribution=Propagation = Lazy Clause Generation|first1=Olga|last1=Ohrimenko|first2=Peter J.|last2=Stuckey|first3=Michael|last3=Codish|doi=10.1007/978-3-540-74970-7_39|quote=modern SAT solvers can often handle problems with millions of constraints and hundreds of thousands of variables|citeseerx=10.1.1.70.5471}}</ref> सैट सॉल्वर प्रायः फार्मूला को [[संयोजक सामान्य रूप|कंजेक्टिव नॉरमल फॉर्म]] में परिवर्तित करके प्रारम्भ करते हैं। वे प्रायः [[डीपीएलएल एल्गोरिदम]] जैसे कोर एल्गोरिदम पर आधारित होते हैं, किन्तु इसमें कई एक्सटेंशन एवं सुविधाएं सम्मिलित होती हैं। अधिकांश सैट सॉल्वरों में टाइम-आउट सम्मिलित होता है, इसलिए वे ट्रू समय में समाप्त हो जाएंगे, अपितु वे "अननोन" जैसे आउटपुट के साथ सोलुशन प्राप्त नहीं कर सकते है। प्रायः, सैट सॉल्वर केवल उत्तर ही नहीं देते हैं, अपितु यदि फॉर्मूला सटिसफाईइंग है तो उदाहरण असाइनमेंट (x, y, आदि के लिए मान) या फॉर्मूला असंतोषजनक होने पर असंतोषजनक क्लॉसेस का न्यूनतम सेट सहित अधिक जानकारी प्रदान कर सकते हैं।

आधुनिक सैट सॉल्वरों का [[सॉफ़्टवेयर सत्यापन|सॉफ़्टवेयर वेरिफिकेशन]], प्रोग्राम एनालिसिस, [[बाधा संतुष्टि समस्या|कन्सट्रैन्ट सॉल्विंग]], आर्टिफिशियल इंटेलिजेंस, [[इलेक्ट्रॉनिक डिजाइन स्वचालन|इलेक्ट्रॉनिक डिजाइन ऑटोमेशन]] एवं ऑपरेशन रिसर्च सहित क्षेत्रों पर महत्वपूर्ण प्रभाव पड़ा है। पावरफुल सॉल्वर [[मुफ़्त और ओपन-सोर्स सॉफ़्टवेयर|फ्री एवं ओपन-सोर्स सॉफ़्टवेयर]] के रूप में सरलता से उपलब्ध हैं एवं कुछ प्रोग्रामिंग लैंग्वेज में निर्मित होते हैं जैसे कि सैट सॉल्वर को [[बाधा तर्क प्रोग्रामिंग|कंस्ट्रेंट लॉजिक प्रोग्रामिंग]] में कंस्ट्रेंट्स के रूप में प्रदर्शित करना है।

== अवलोकन ==

=== डीपीएलएल सॉल्वर ===
{{main|डीपीएलएल एल्गोरिदम}}

डीपीएलएल सैट सॉल्वर सटिसफाईइंग असाइनमेंट की सर्च में परिवर्तनीय असाइनमेंट के (घातीय आकार के) स्पेस को ज्ञात करने के लिए व्यवस्थित बैकट्रैकिंग सर्च प्रक्रिया को नियोजित करता है। मूलरूपी सर्च प्रक्रिया 1960 दशक के प्रारम्भ में दो प्राथमिक पेपर्स में प्रस्तावित की गई थी (नीचे रिफरेन्स देखें) एवं अब इसे सामान्यतः डेविस-पुटनम-लोगमैन-लवलैंड एल्गोरिदम (डीपीएलएल या डीएलएल) के रूप में जाना जाता है।<ref>{{Cite journal | last1 = Davis | first1 = M. | last2 = Putnam | first2 = H. | title = परिमाणीकरण सिद्धांत के लिए एक कंप्यूटिंग प्रक्रिया| journal = Journal of the ACM | volume = 7 | issue = 3 | page = 201 | year = 1960 | doi = 10.1145/321033.321034| s2cid = 31888376 }}</ref><ref>{{Cite journal | last1 = Davis | first1 = M. |author-link1=Martin Davis (mathematician)| last2 = Logemann | first2 = G. | last3 = Loveland | first3 = D. | title = प्रमेय सिद्ध करने के लिए एक मशीन प्रोग्राम| journal = [[Communications of the ACM]]| volume = 5 | issue = 7 | pages = 394–397 | year = 1962 | url = http://www.ensiie.fr/~blazy/ipr/article2.pdf| doi = 10.1145/368273.368557| hdl = 2027/mdp.39015095248095 | s2cid = 15866917 | hdl-access = free }}</ref> प्रैक्टिकल सैट सोलुशन के लिए कई आधुनिक अप्प्रोचेस डीपीएलएल एल्गोरिथ्म से प्राप्त हुए हैं एवं समान संरचना सम्मिलित करते हैं। प्रायः वे केवल सैट समस्याओं के कुछ क्लासेज की एफिशिएंसी में सुधार करते हैं जैसे कि टेक्निकल अनुप्रयोगों में प्रदर्शित होने वाले उदाहरण या यादृच्छिक रूप से उत्पन्न उदाहरण है।<ref name=":3" /> सैद्धांतिक रूप से, एल्गोरिदम के डीपीएलएल फैमिली के लिए घातांकीय निचली सीमाएं प्रमाणित हो चुकी हैं।

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

इसके विपरीत, पटुरी, पुडलक, साक्स एवं ज़ेन द्वारा पीपीएसजेड एल्गोरिदम जैसे यादृच्छिक एल्गोरिदम कुछ अनुमानों के अनुसार रैंडमली वेरिएबल सेट करते हैं, उदाहरण के लिए बॉण्डेड विड्थ रिज़ॉल्यूशन है। यदि ह्यूरिस्टिक को ट्रू सेटिंग नहीं प्राप्त होती है, तो वेरिएबल को यादृच्छिक रूप से असाइन किया जाता है। PPSZ एल्गोरिथ्म में <math>O(1.308^n)</math> 3-सैट के लिए {{clarify span|runtime|I guess, for randomized algorithm, 'runtime' means 'expected runtime' or something similar, rather than 'worst case runtime'? Please qualify, and add a link to the definition, if possible.|date=February 2020}} होता है। यह 2019 तक इस प्रॉब्लम के लिए सबसे प्रसिद्ध रनटाइम था, जब हैनसेन, कपलान, ज़मीर एवं ज़्विक ने रनटाइम <math>O(1.307^n)</math> 3-सैट के लिए मॉडिफिकेशन प्रकाशित किया, उत्तरार्द्ध वर्तमान में k के सभी मानों पर k-सैट के लिए सबसे फास्टेस्ट नोन एल्गोरिदम है। कई सटिसफाईइंग असाइनमेंट वाली सेटिंग में स्कोनिंग द्वारा रैंडमाइज्ड एल्गोरिदम की सीमा उत्तम है।<ref name="Schoning.1999">{{cite book | last1 = Schöning | first1 = Uwe| chapter = A Probabilistic Algorithm for ''k''-SAT and Constraint Satisfaction Problems | title = Proc. 40th Ann. Symp. Foundations of Computer Science| pages = 410–414 | date=Oct 1999 | chapter-url=http://homepages.cwi.nl/~rdewolf/schoning99.pdf| doi = 10.1109/SFFCS.1999.814612| isbn = 0-7695-0409-4| s2cid = 123177576}}</ref><ref name="ppsz_algorithm">[http://dl.acm.org/cition.cfm?id=1066101 k-SAT के लिए एक बेहतर घातांक-समय एल्गोरिथ्म], पटुरी, पुडलक, सैक्स, ज़ानी</ref><ref name="biased_ppsz_algorithm">[http://dl.acm.org/cation.cfm?id=3316359 बायस्ड-पीपीएसजेड का उपयोग करते हुए तेज़ के-एसएटी एल्गोरिदम], हैनसेन, कपलान, ज़मीर, ज़्विक</ref>

=== सीडीसीएल सॉल्वर ===
{{main|कनफ्लिक्ट-ड्रिवेन क्लॉज़ लर्निंग}}

आधुनिक सैट सॉल्वर (2000 के दशक में विकसित) दो प्रकारों में आते हैं: कनफ्लिक्ट-ड्रिवेन एवं आगे की ओर देखने वाले। दोनों एप्रोच डीपीएलएल से उत्पन हुए हैं।<ref name=":3">{{Citation|last1=Zhang|first1=Lintao|title=The Quest for Efficient Boolean Satisfiability Solvers|date=2002|work=Computer Aided Verification|pages=17–36|publisher=Springer Berlin Heidelberg|isbn=978-3-540-43997-4|last2=Malik|first2=Sharad|doi=10.1007/3-540-45657-0_2|doi-access=free}}</ref> कनफ्लिक्ट-ड्रिवेन सॉल्वर, जैसे कनफ्लिक्ट-ड्रिवेन क्लॉज लर्निंग (सीडीसीएल), एफिशिएंट कनफ्लिक्ट एनालिसिस, क्लॉज लर्निंग, नॉन-क्रोनोलॉजिकल [[कालानुक्रमिक बैकट्रैकिंग|बैकट्रैकिंग]] के साथ-साथ वाटचेड लिटरल्स यूनिट प्रोपोगेशन, अनुकूली ब्रांच एवं यादृच्छिक पुनरारंभ के साथ मूलरूपी डीपीएलएल सर्च एल्गोरिदम को बढ़ाते हैं। मूलरूपी व्यवस्थित सर्च के लिए ये अतिरिक्त अनुभवजन्य रूप से इलेक्ट्रॉनिक डिज़ाइन ऑटोमेशन (EDA) में उत्पन्न होने वाले बड़े सैट उदाहरणों के लिए आवश्यक दिखाए गए हैं।<ref>{{Cite journal | last1 = Vizel | first1 = Y. | last2 = Weissenbacher | first2 = G. | last3 = Malik | first3 = S. | journal = Proceedings of the IEEE | volume = 103 | issue = 11 | year = 2015 | doi = 10.1109/JPROC.2015.2455034|title=बूलियन संतुष्टि समाधानकर्ता और मॉडल जाँच में उनके अनुप्रयोग| pages = 2021–2035 | s2cid = 10190144 }}</ref> सुप्रसिद्ध कार्यान्वयनों में [[भूसा एल्गोरिथ्म|ग्रास्प एल्गोरिथ्म]] सम्मिलित है I<ref>{{Cite book|last1=Moskewicz|first1=M. W.|title=Proceedings of the 38th conference on Design automation (DAC)|last2=Madigan|first2=C. F.|last3=Zhao|first3=Y.|last4=Zhang|first4=L.|last5=Malik|first5=S.|year=2001|isbn=1581132972|page=530|chapter=Chaff: Engineering an Efficient SAT Solver|doi=10.1145/378239.379017|s2cid=9292941|chapter-url=http://www.princeton.edu/~chaff/publication/DAC2001v56.pdf}}</ref><ref>{{Cite journal|last1=Marques-Silva|first1=J. P.|last2=Sakallah|first2=K. A.|year=1999|title=GRASP: a search algorithm for propositional satisfiability|url=http://embedded.eecs.berkeley.edu/Alumni/wjiang/ee219b/grasp.pdf|journal=IEEE Transactions on Computers|volume=48|issue=5|page=506|doi=10.1109/12.769433|access-date=2015-08-28|archive-url=https://web.archive.org/web/20161104020512/http://embedded.eecs.berkeley.edu/Alumni/wjiang/ee219b/grasp.pdf|archive-date=2016-11-04|url-status=dead}}</ref> लुक-फॉरवर्ड सॉल्वर्स ने विशेष रूप से रिडक्शन (यूनिट-क्लॉज प्रोपोगेशन से परे) एवं अनुमानों को सशक्त किया है, एवं वे सामान्यतः कठिन उदाहरणों पर कनफ्लिक्ट-ड्रिवेन सॉल्वरों की अपेक्षा में अधिक सशक्त होते हैं (जबकि कनफ्लिक्ट-ड्रिवेन सॉल्वर बड़े उदाहरणों पर अधिक उत्तम हो सकते हैं जिनके अंदर रियल में सरल उदाहरण होता है)।

कनफ्लिक्ट-ड्रिवेन मिनीसैट, जो 2005 सैट प्रतियोगिता में अपेक्षाकृत सफल रहा, में कोड की केवल 600 लाइनें हैं। आधुनिक पैरेलल सैट सॉल्वर मैनीसैट है।<ref>http://www.cril.univ-artois.fr/~jabbour/manysat.htm {{Bare URL inline|date=September 2022}}</ref> यह समस्याओं के महत्वपूर्ण क्लासेज पर सुपर लीनियर स्पीड-अप प्राप्त कर सकता है। आगे बढ़ने वाले सॉल्वरों का उदाहरण मार्च_डीएल है, जिसने 2007 सैट प्रतियोगिता में पुरस्कार जीता था। गूगल के सीपी-सैट सॉल्वर, [[या-उपकरण|या डिवाइस]] के शेयर्ड, ने 2018, 2019, 2020 एवं 2021 में मिनिजिंक कन्सट्रैन्ट प्रोग्रामिंग कॉन्टेस्ट्स में स्वर्ण पदक जीते थे।

सैट के कुछ प्रकार के बड़े यादृच्छिक सटिसफाईइंग उदाहरणों का सर्वेक्षण प्रोपोगेशन (एसपी) द्वारा सॉल्व किया जा सकता है। विशेष रूप से [[हार्डवेयर डिज़ाइन]] एवं [[हार्डवेयर सत्यापन|हार्डवेयर वेरिफिकेशन]] अनुप्रयोगों में, किसी दिए गए प्रस्ताव फार्मूला की संतुष्टि एवं अन्य लॉजिक गुणों को कभी-कभी [[द्विआधारी निर्णय आरेख|बाइनरी डिसीजन डायग्राम]] (बीडीडी) के रूप में फार्मूला के प्रतिनिधित्व के आधार पर सुनिश्चित किया जाता है।

भिन्न-भिन्न सैट सॉल्वर भिन्न-भिन्न उदाहरणों को सरल या कठिन पाएंगे, एवं कुछ अनसटिस्फाइयबिलिटी प्रमाणित करने में एवं अन्य सोलुशन सर्च में इन्सटेंसेस प्राप्त करेंगे। ये सभी बिहेवियर सैट सोलुशन कांटेस्ट में देखे जा सकते हैं।<ref>{{cite web|url=http://www.satcompetition.org/ |title=अंतर्राष्ट्रीय SAT प्रतियोगिता वेब पेज|access-date=2007-11-15}}</ref>

'''पैरेलल सैट-सॉल्विंग'''

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

अंतर्राष्ट्रीय सैट सॉल्वर प्रतियोगिता में पैरेलल ट्रैक है जो पैरेलल सैट सोलुशन में वर्तमान की प्रगति को प्रदर्शित करता है। 2016 में,<ref>{{cite web|url=https://baldur.iti.kit.edu/sat-competition-2016/index.php?cat=tracks|title=SAT Competition 2016|website=baldur.iti.kit.edu|access-date=2020-02-13}}</ref> 2017<ref>{{cite web|url=https://baldur.iti.kit.edu/sat-competition-2017/index.php?cat=tracks|title=SAT Competition 2017|website=baldur.iti.kit.edu|access-date=2020-02-13}}</ref> एवं 2018,<ref>{{cite web|url=http://sat2018.forsyte.tuwien.ac.at/index.php?cat=tracks|title=SAT Competition 2018|website=sat2018.forsyte.tuwien.ac.at|access-date=2020-02-13}}</ref> बेंचमार्क 24 [[सेंट्रल प्रोसेसिंग यूनिट]] के साथ शेयर्ड-मेमोरी सिस्टम पर चलाए गए थे, इसलिए वितरित मेमोरी या कई [[कईकोर प्रोसेसर|कोर प्रोसेसर]] के लिए सॉल्वर कम पड़ गए थे।

=== पोर्टफोलियो ===
सामान्यतः ऐसा कोई सैट सॉल्वर नहीं है जो सभी सैट समस्याओं पर अन्य सभी सॉल्वरों से उत्तम प्रदर्शन करता हो। एल्गोरिदम उन प्रॉब्लम उदाहरणों के लिए ट्रू प्रदर्शन कर सकता है जिसके लिए अन्य लोग कनफ्लिक्ट कर रहे हैं, किन्तु अन्य उदाहरणों के साथ यह व्यर्थ प्रदर्शन करता है। इसके अतिरिक्त, सैट उदाहरण को देखते हुए, यह अनुमान लगाने का कोई विश्वसनीय उपाय नहीं है कि कौन सा एल्गोरिदम इस उदाहरण में विशेष रूप से तीव्रता से सॉल्व करेगा। ये सीमाएँ पैरेलल पोर्टफोलियो एप्रोच को प्रेरित करती हैं। पोर्टफोलियो विभिन्न एल्गोरिदम या एल्गोरिदम के विभिन्न कॉन्फ़िगरेशन का सेट है। पैरेलल पोर्टफोलियो में सभी सॉल्वर प्रॉब्लम को सॉल्व करने के लिए भिन्न-भिन्न प्रोसेसर पर चलते हैं। यदि सॉल्वर समाप्त हो जाता है, तो पोर्टफोलियो सॉल्वर इस सॉल्वर के अनुसार प्रॉब्लम को सटिस्फाइयबल या अनसटिस्फाइयबल बताता है। अन्य सभी सॉल्वरों को समाप्त कर दिया गया है। विभिन्न प्रकार के सॉल्वरों को सम्मिलित करके पोर्टफोलियो में विविधता लाने से, जिनमें से प्रत्येक प्रॉब्लम के भिन्न-भिन्न सेट पर ट्रू प्रदर्शन करता है, सॉल्वर की पॉवर बढ़ जाती है।<ref name=":1">{{Citation|last1=Balyo|first1=Tomáš|title=Parallel Satisfiability|date=2018|work=Handbook of Parallel Constraint Reasoning|pages=3–29|publisher=Springer International Publishing|isbn=978-3-319-63515-6|last2=Sinz|first2=Carsten|doi=10.1007/978-3-319-63516-3_1}}</ref> कई सॉल्वर आंतरिक रूप से रैंडम नंबर जनरेटर का उपयोग करते हैं। अपने [[यादृच्छिक बीज|सीड्स]] में विविधता लाना पोर्टफोलियो में विविधता लाने का सरल उपाय है। अन्य विविधीकरण रणनीतियों में अनुक्रमिक सॉल्वर में कुछ अनुमानों को सक्षम करना, अक्षम करना या विविधता लाना सम्मिलित है।<ref>{{cite web|url=https://baldur.iti.kit.edu/sat-race-2010/descriptions/solver_1+2+3+6.pdf|title=Lingeling, Plingeling, PicoSAT and PrecoSAT at SAT Race 2010|last=Biere|first=Armin|website=SAT-RACE 2010}}</ref> पैरेलल पोर्टफोलियो का ड्राबैक डुप्लिकेट कार्य की मात्रा है। यदि सीक्वेंशियल सॉल्वरों में क्लॉज लर्निंग का उपयोग किया जाता है, तो पैरेलल चलने वाले सॉल्वरों के मध्य सीखे गए क्लॉज को शेयर्ड करने से डुप्लिकेट कार्य को कम किया जा सकता है एवं प्रदर्शन में वृद्धि हो सकती है। अपितु, केवल बेस्ट सॉल्वरों का पोर्टफोलियो पैरेलल में चलाने से भी कॉम्पिटेटिव पैरेलल सॉल्वर बन जाता है। ऐसे सॉल्वर का उदाहरण पीपीफ़ोलियो है।<ref>{{cite web|url=http://www.cril.univ-artois.fr/~roussel/ppfolio/|title=पीपीफ़ोलियो सॉल्वर|website=www.cril.univ-artois.fr|access-date=2019-12-29}}</ref><ref>{{cite web|url=http://www.cril.univ-artois.fr/SAT11/results/ranking.php?idev=58|title=SAT 2011 Competition: 32 cores track: ranking of solvers|website=www.cril.univ-artois.fr|access-date=2020-02-13}}</ref> इसे उस प्रदर्शन के लिए निचली सीमा के लिए डिज़ाइन किया गया था जो पैरेलल सैट सॉल्वर प्रदान करने में सक्षम होना चाहिए। ऑप्टिमाइजेशन के अभाव के कारण अधिक मात्रा में डुप्लिकेट कार्य के अतिरिक्त, इसने शेयर्ड मेमोरी मशीन पर ट्रू प्रदर्शन किया है। होर्डेसैट<ref>{{Citation|last1=Balyo|first1=Tomáš|title=HordeSat: A Massively Parallel Portfolio SAT Solver|date=2015|work=Lecture Notes in Computer Science|pages=156–172|publisher=Springer International Publishing|isbn=978-3-319-24317-7|last2=Sanders|first2=Peter|last3=Sinz|first3=Carsten|doi=10.1007/978-3-319-24318-4_12|arxiv=1505.03340|s2cid=11507540}}</ref> कंप्यूटिंग नोड्स के बड़े समूहों के लिए पैरेलल पोर्टफोलियो सॉल्वर है। यह अपने मूल में अनुक्रमिक सॉल्वर के भिन्न-भिन्न कॉन्फ़िगर किए गए उदाहरणों का उपयोग करता है। विशेष रूप से कठिन सैट उदाहरणों के लिए होर्डेसैट लीनियर स्पीडअप उत्पन्न कर सकता है एवं इसलिए रनटाइम को अधिक कम कर सकता है।

वर्तमान के वर्षों में पैरेलल पोर्टफोलियो सैट सॉल्वरों ने अंतर्राष्ट्रीय सैट सॉल्वर कॉन्टेस्ट्स के पैरेलल ट्रैक पर अपना प्रतिनिधित्व बना लिया है। ऐसे सॉल्वरों के उल्लेखनीय उदाहरणों में प्लिंगलिंग एवं पेनलेस-एमकॉमस्प्स सम्मिलित हैं।<ref>{{cite web|url=http://sat2018.forsyte.tuwien.ac.at/|title=SAT Competition 2018|website=sat2018.forsyte.tuwien.ac.at|access-date=2020-02-13}}</ref>

'''डिवाइड-एंड-कॉनकर'''

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

[[File:Cube and Conquer example.svg|alt=Tree illustrating the look-आगे चरण और परिणामी घन.|अंगूठा|348x348px|सूत्र के लिए घन चरण <math>F</math>. निर्णय अनुमानी चुनता है कि कौन से चर (सर्कल) निर्दिष्ट करने हैं। कटऑफ हेयुरिस्टिक द्वारा आगे की शाखाओं को रोकने का निर्णय लेने के बाद, सीडीसीएल का उपयोग करके आंशिक समस्याओं (आयत) को स्वतंत्र रूप से हल किया जाता है।]]

नॉन-क्रोनोलॉजिकल बैकट्रैकिंग के कारण, कनफ्लिक्ट-ड्रिवेन क्लॉज सीखने का समानांतरीकरण अधिक कठिन है। इस पर कंट्रोल करने का उपाय क्यूब एंड कॉनकर पैराडिग्म है।<ref name=":0">{{Citation|last1=Heule|first1=Marijn J. H.|author-link=Marijn Heule|title=Cube and Conquer: Guiding CDCL SAT Solvers by Lookaheads|date=2012|work=Hardware and Software: Verification and Testing|pages=50–65|publisher=Springer Berlin Heidelberg|isbn=978-3-642-34187-8|last2=Kullmann|first2=Oliver|last3=Wieringa|first3=Siert|last4=Biere|first4=Armin|doi=10.1007/978-3-642-34188-5_8}}</ref> यह दो चरण में सोलुशन करने का विचार देता है। क्यूब चरण में प्रॉब्लम को हजारों, लाखों तक क्लासेज में विभाजित किया जाता है। यह लुक-फॉरवर्ड सॉल्वर द्वारा किया जाता है, जो क्यूब्स नामक पार्शियल कॉन्फ़िगरेशन का सेट ढूंढता है। क्यूब को मूल फार्मूला के वेरिएबलों के सबसेट के [[तार्किक संयोजन|लॉजिक संयोजन]] के रूप में भी देखा जा सकता है। फार्मूला के संयोजन में, प्रत्येक क्यूब नया फार्मूला बनाता है। इन फार्मूलों को कनफ्लिक्ट-ड्रिवेन सॉल्वर्स द्वारा स्वतंत्र रूप से एवं समवर्ती रूप से सॉल्व किया जा सकता है। चूंकि इन फार्मूलों का [[तार्किक विच्छेद|लॉजिक]] डिस्जंक्शन मूल फार्मूला के लिए [[तार्किक तुल्यता|एक्विवैलेन्ट]] है, इसलिए प्रॉब्लम को सटिसफाईइंग माना जाता है, यदि कोई फार्मूला सटिसफाईइंग है। आगे की ओर देखने वाला सॉल्वर छोटी किन्तु कठिन समस्याओं के लिए अनुकूल है,<ref>{{Cite book|last1=Heule|first1=Marijn J. H.|author-link=Marijn Heule|title=संतुष्टि की पुस्तिका|last2=van Maaren|first2=Hans|publisher=IOS Press|year=2009|isbn=978-1-58603-929-5|pages=155–184|chapter=Look-Ahead Based SAT Solvers|chapter-url=https://www.cs.utexas.edu/~marijn/publications/p01c05_lah.pdf}}</ref> इसलिए इसका उपयोग प्रॉब्लम को धीरे-धीरे कई उप-समस्याओं में विभाजित करने के लिए किया जाता है। ये उप-समस्याएँ सरल हैं अपितु अधिक हैं जो कनफ्लिक्ट-ड्रिवेन सॉल्वर के लिए आइडियल फॉर्म है। इसके अतिरिक्त आगे की सोच वाले सॉल्वर पूरी प्रॉब्लम पर विचार करते हैं जबकि कनफ्लिक्टप्रेरित सॉल्वर अधिक लोकल जानकारी के आधार पर निर्णय लेते हैं। क्यूब चरण में तीन अनुमान सम्मिलित हैं। क्यूब्स में वेरिएबलों का डिसीजन हेयूरिस्टिक के अनुसार चयन होता है। दिशा अनुमान यह सुनिश्चित करता है कि किस वेरिएबल असाइनमेंट (ट्रू या फॉल्स) को ज्ञात करना है। सटिसफाईइंग प्रॉब्लम वाले विषयों में, सटिसफाईइंग ब्रांच का चयन लाभकारी होता है। कटऑफ अनुमान यह सुनिश्चित करता है कि कब क्यूब का विस्तार रोकना है एवं इसके अतिरिक्त इसे अनुक्रमिक कनफ्लिक्ट-ड्रिवेन सॉल्वर को फॉरवर्ड करना है। अधिमानतः क्यूब्स का सॉल्व करना समान रूप से काम्प्लेक्स है।<ref name=":0" />

ट्रींजलिंग पैरेलल सॉल्वर का उदाहरण है जो क्यूब-एंड-कॉनकर पैराडिग्म प्रस्तावित करता है। 2012 में इसके प्रारम्भ के पश्चात से इसे अंतर्राष्ट्रीय सैट सॉल्वर प्रतियोगिता में कई सफलताएँ प्राप्त हुई हैं। [[बूलियन पायथागॉरियन त्रिगुण समस्या|बूलियन पायथागॉरियन ट्रिपल्स प्रॉब्लम]] का सॉल्व करने के लिए क्यूब-एंड-कॉन्कर का उपयोग किया गया था।<ref name=":2">{{Citation|last1=Heule|first1=Marijn J. H.|author-link=Marijn Heule|title=Solving and Verifying the Boolean Pythagorean Triples Problem via Cube-and-Conquer|date=2016|work=Theory and Applications of Satisfiability Testing – SAT 2016|pages=228–245|publisher=Springer International Publishing|isbn=978-3-319-40969-6|last2=Kullmann|first2=Oliver|last3=Marek|first3=Victor W.|doi=10.1007/978-3-319-40970-2_15|arxiv=1605.00723|s2cid=7912943}}</ref>

'''लोकल सर्च'''

सैट सॉल्विंग के लिए पैरेलल लोकल सर्च एल्गोरिदम की दिशा में स्ट्रेटेजी विभिन्न प्रोसेसिंग यूनिट्स पर साथ मल्टीपल वेरिएबल फ़्लिप्स को ट्राई करना है।<ref>{{Citation|last=Roli|first=Andrea|title=Principles and Practice of Constraint Programming - CP 2002|chapter=Criticality and Parallelism in Structured SAT Instances|volume=2470|date=2002|pages=714–719|publisher=Springer Berlin Heidelberg|isbn=978-3-540-44120-5|doi=10.1007/3-540-46135-3_51|series=Lecture Notes in Computer Science}}</ref> दूसरा, उपर्युक्त पोर्टफोलियो एप्रोच को प्रस्तावित करना है, चूँकि क्लॉज सम्मिलित करना संभव नहीं है क्योंकि लोकल सर्च सॉल्वर क्लॉज का उत्पादन नहीं करते हैं। वैकल्पिक रूप से, लोकल स्तर पर उत्पादित कॉन्फ़िगरेशन को सम्मिलित करना संभव है। जब कोई लोकल सॉल्वर सर्च को रीस्टार्ट करने का निर्णय लेता है तो इन कॉन्फ़िगरेशन का उपयोग नए इनिशियल कॉन्फ़िगरेशन के उत्पादन को निर्देशित करने के लिए किया जा सकता है।<ref>{{Citation|last1=Arbelaez|first1=Alejandro|title=Improving Parallel Local Search for SAT|date=2011|work=Lecture Notes in Computer Science|pages=46–60|publisher=Springer Berlin Heidelberg|isbn=978-3-642-25565-6|last2=Hamadi|first2=Youssef|doi=10.1007/978-3-642-25566-3_4|s2cid=14735849 }}</ref>

== यह भी देखें ==
* बूलियन सेटिस्फिएबिलिटी प्रॉब्लम
* [[संतुष्टि मॉड्यूलो सिद्धांत|सेटिस्फिएबिलिटी मॉड्यूलो थेओरीज़]]
* केटेगरी:सैट सॉल्वर
* [[कंप्यूटर-समर्थित प्रमाण|कंप्यूटर-अस्सीस्टेड प्रूफ]]

== संदर्भ ==
{{Reflist}}

{{Program analysis}}[[Category: औपचारिक तरीके]] [[Category: कंप्यूटर विज्ञान में तर्क]] [[Category: संतुष्टि की समस्या]]

[[Category: Machine Translated Page]]
[[Category:Created On 25/07/2023]]
[[Category:Vigyan Ready]]

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

2024-02-02T17:06:29Z

Indicwiki: 29 revisions imported from :alpha:समष्टि_पदानुक्रम_प्रमेय

{{short description|Both deterministic and nondeterministic machines can solve more problems given more space}}[[कम्प्यूटेशनल जटिलता सिद्धांत|कम्प्यूटेशनल कम्प्लेक्सिटी थ्योरी]] में, '''स्पेस हायरार्की थ्योरम''' ऐसे सेपरेशन रिजल्ट्स हैं जो प्रदर्शित करते हैं कि डेटर्मीनिस्टिक एवं नॉन-डेटर्मीनिस्टिक दोनों मशीनें कुछ कंडीशंस के अधीन (अस्पष्ट रूप से) अधिक स्पेस में अधिक प्रोब्लेम्स को सॉल्व कर सकती हैं। उदाहरण के लिए, [[नियतात्मक ट्यूरिंग मशीन|डेटर्मीनिस्टिक ट्यूरिंग मशीन]] स्पेस ''n'' की अपेक्षा स्पेस ''n'' log ''n'' में [[निर्णय समस्या|डिसिशन प्रोब्लेम्स]] को सॉल्व कर सकती है। टाइम के लिए कुछ सीमा तक वीकर एनलॉगस थेओरेम्स [[समय पदानुक्रम प्रमेय|टाइम हायरार्की थेओरेम्स]] हैं।

हायरार्की थेओरेम्स के आधार के इंटूइशन में निहित है कि अधिक टाइम या अधिक स्पेस के साथ कंप्यूट करने की क्षमता होती है। हायरार्की थेओरेम्स का उपयोग यह प्रदर्शित करने के लिए किया जाता है कि टाइम एवं स्पेस कम्प्लेक्सिटी क्लासेज हायरार्की बनाते हैं जहां टाइटर बॉन्ड्स में अधिक रिलैक्स्ड बॉन्ड्स की अपेक्षा कम लैंग्वेजेज होती हैं। यहां स्पेस हायरार्की थ्योरम को परिभाषित एवं प्रूफ किया जाता है।

स्पेस हायरार्की थ्योरम [[अंतरिक्ष-निर्माण योग्य कार्य|स्पेस-कंस्ट्रक्टिबल फंक्शन्स]] की अवधारणा पर निर्भर करते हैं। डेटर्मीनिस्टिक एवं नॉन-डेटर्मीनिस्टिक स्पेस हायरार्की थ्योरम बताते हैं कि सभी स्पेस-कंस्ट्रक्टिबल फंक्शन्स के लिए ''f''(''n''), इस प्रकार है:

:<math>\mathsf{SPACE}\left(o(f(n))\right) \subsetneq \mathsf{SPACE}(f(n))</math>,
जहां स्पेस का तात्पर्य [[DSPACE|डीस्पेस]] या [[NSPACE|एनस्पेस]] है, और {{mvar|o}} छोटे o नोटेशन को रेफेर करता है।

== स्टेटमेंट ==

औपचारिक रूप से, फंक्शन <math>f:\mathbb{N} \longrightarrow \mathbb{N}</math> स्पेस-कंस्ट्रक्टीबल है यदि <math>f(n) \ge \log~n</math> एवं वहाँ ट्यूरिंग मशीन उपस्थित है जो फंक्शन <math>f(n)</math> की कंप्यूट स्पेस <math>O(f(n))</math> में इनपुट <math>1^n</math> के साथ प्रारंभ करते टाइम करता है, जहाँ <math>1^n</math> n क्रमागत 1s की स्ट्रिंग का प्रतिनिधित्व करता है। अधिकांश सामान्य फंक्शन जिनके साथ हम कार्य करते हैं, वे स्पेस-कंस्ट्रक्टीबल हैं, जिनमें बहुपद, घातांक एवं लघुगणक सम्मिलित हैं।

प्रत्येक स्पेस-कंस्ट्रक्टीबल फंक्शन <math>f:\mathbb{N} \longrightarrow
\mathbb{N}</math> के लिए, वहाँ लैंग्वेज {{mvar|L}} उपस्थित है जो स्पेस <math>O(f(n))</math> में निर्णय लेने योग्य है किन्तु स्पेस <math>o(f(n))</math> में नहीं है।

== प्रूफ ==

गोल ऐसी लैंग्वेज को परिभाषित करना है जिसे स्पेस <math>o(f(n))</math> में नहीं अपितु <math>O(f(n))</math> में निश्चित किया जा सकता है। लैंग्वेज को L के रूप में परिभाषित किया गया है, <math>L = \{~ (\langle M \rangle, 10^k): M \mbox{ uses space } \le f(|\langle M \rangle, 10^k|) \mbox{ and time } \le 2^{f(|\langle M \rangle, 10^k|)} \mbox{ and } M \mbox{ does not accept } (\langle M \rangle,
10^k) ~ \}</math>

किसी भी मशीन {{mvar|M}} के लिए जो स्पेस <math>o(f(n))</math> में लैंग्वेज सुनिश्चित करता है, {{mvar|L}} {{mvar|M}} की लैंग्वेज से कम से कम स्पेस पर भिन्न होगा, अर्थात्, कुछ बड़े पर्याप्त {{mvar|k}} के लिए, {{mvar|M}} स्पेस का उपयोग करेगा <math>\le f(|\langle M \rangle, 10^k|)</Math> on <math>(\langle M \rangle, 10^k)</Math> और इसलिए इसके मूल्य में भिन्नता होगी।

दूसरी ओर, {{mvar|L}}, <math>\mathsf{SPACE}(f(n))</math>में है। लैंग्वेज {{mvar|L}} सुनिश्चित करने के लिए एल्गोरिदम इस प्रकार है:

# इनपुट {{mvar|x}} पर, <math>f(|x|)</math> स्पेस-निर्माणशीलता का उपयोग और मार्क ऑफ करके कंप्यूट की जाती है, एवं <math>f(|x|)</math> टेप की सेल को चिह्नित किया जाता है, जब भी इससे अधिक प्रयोग करने का प्रयास किया जाता है तो <math>f(|x|)</math>सेल इसे अस्वीकार कर देती है।
# यदि {{mvar|x}}, <math>\langle M \rangle, 10^k</math> का स्वरूप नहीं है, तो कुछ TM के लिए {{mvar|M}}, अस्वीकार किया जाता है।
# अधिक से अधिक इनपुट {{mvar|x}} पर {{mvar|M}} का अनुकरण करता है, <math>2^{f(|x|)}</math>चरण ( <math>f(|x|)</math> स्पेस का उपयोग करके) है। यदि सिमुलेशन <math>f(|x|)</math> स्पेस से अधिक या उससे अधिक <math>2^{f(|x|)}</math> ऑपरेशन का उपयोग करने का प्रयास करता है तो इसे अस्वीकार कर दिया जाता है।
# यदि इस अनुकरण के टाइम {{mvar|M}} ने {{mvar|x}} को स्वीकार कर लिया है, तो इसे अस्वीकार अन्यथा स्वीकार कर लिया जाता है।

चरण 3 पर ध्यान दें: निष्पादन यहीं तक सीमित है, उस स्थिति से बचने के लिए <math>2^{f(|x|)}</math>चरण जहां {{mvar|M}} इनपुट {{mvar|x}} पर नहीं रुकता है। अर्थात्, वह स्थिति जहाँ {{mvar|M}} केवल स्थान का उपभोग करता है। <math>O(f(x))</math> आवश्यकतानुसार, किन्तु अनंत टाइम तक उपयोग होता है।

उपरोक्त प्रूफ पीस्पेस की स्थिति में मान्य है, किन्तु एनपीस्पेस की स्थिति में कुछ परिवर्तन करने की आवश्यकता है। महत्वपूर्ण बिंदु यह है कि नियतात्मक TM पर, स्वीकृति एवं अस्वीकृति को विपरीत किया जा सकता है (चरण 4 के लिए महत्वपूर्ण), अन्य-नियतात्मक मशीन पर यह संभव नहीं है।

एनपीस्पेस की स्थिति में, {{mvar|L}} को पुनः परिभाषित करने की आवश्यकता है:

<math>L = \{~ (\langle M \rangle, 10^k): M \mbox{ uses space } \le f(|\langle M \rangle, 10^k|) \mbox{ and } M \mbox{ accepts } (\langle M \rangle,
10^k) ~ \}</math>

अब, चरण 4 को संशोधित करके {{mvar|L}} को स्वीकार करने के लिए एल्गोरिदम को परिवर्तित करने की आवश्यकता है:

* यदि इस अनुकरण के टाइम {{mvar|M}} ने {{mvar|x}} को स्वीकार कर लिया है, तो स्वीकार करें; अन्यथा, अस्वीकार करें।

{{mvar|L}} का उपयोग TM द्वारा <math>o(f(n))</math> का उपयोग नहीं किया जा सकता है। यह मानते हुए कि {{mvar|L}} का निर्णय कुछ TM {{mvar|M}} उपयोग करके किया जा सकता है <math>o(f(n))</math> सेल एवं इमरमैन-स्ज़ेलेपीसीसेनी थ्योरम का अनुसरण करते हुए, <math>\overline L</math> को TM (जिसे <math>\overline M</math>कहा जाता है) द्वारा <math>o(f(n))</math> सेल का उपयोग करके भी निर्धारित किया जा सकता है। यहाँ विरोधाभास है, इसलिए धारणा असत्य होनी चाहिए:
# यदि <math>w = (\langle \overline M \rangle, 10^k)</math> (कुछ बड़े पर्याप्त {{mvar|k}} के लिए) <math>\overline L</math> में नहीं है इसलिए {{mvar|M}} इसे स्वीकार करेगा, इसलिए <math>\overline M</math> {{mvar|w}} को अस्वीकार करता है, इसलिए {{mvar|w}} <math>\overline L</math> में है (विरोधाभास)।
# यदि <math>w = (\langle \overline M \rangle, 10^k)</math> (कुछ बड़े पर्याप्त {{mvar|k}} के लिए) <math>\overline L</math> में है इसलिए {{mvar|M}} इसे अस्वीकार कर देगा <math>\overline M</math> {{mvar|w}} को स्वीकार करता है, इसलिए {{mvar|w}}, <math>\overline L</math> में नहीं है (विरोधाभास)।

== कम्पेरिज़न और इम्प्रोवेमेन्ट्स ==

स्पेस हायरार्की थ्योरम कई विषयों में अनुरूप टाइम हायरार्की थेओरेम्स से अधिक सशक्त है:
* इसके लिए केवल s(n) को कम से कम n के अतिरिक्त कम से कम log n होना आवश्यक है।
* यह किसी भी स्पर्शोन्मुख अंतर के साथ वर्गों को भिन्न कर सकता है, जबकि टाइम हायरार्की थ्योरम के लिए उन्हें लोगरिथम फैक्टर द्वारा भिन्न करने की आवश्यकता होती है।
* इसके लिए फंक्शन को टाइम-कंस्ट्रक्टीबल नहीं अपितु स्पेस-कंस्ट्रक्टीबल होना आवश्यक है।

टाइम की अपेक्षा में स्पेस में वर्गों को भिन्न करना सरल लगता है। वास्तव में, जबकि टाइम हायरार्की थ्योरम ने अपनी स्थापना के पश्चात से उल्लेखनीय सुधार देखा है, नॉन डिटरमिनिस्टिक स्पेस हायरार्की थ्योरम में कम से कम महत्वपूर्ण सुधार देखा गया है जिसे [[ विलियम गेफ़र्ट |विलियम गेफ़र्ट]] ने अपने 2003 के पेपर स्पेस हायरार्की थ्योरम में संशोधित किया है। इस पेपर ने थ्योरम के कई सामान्यीकरण किये है:

* यह स्पेस-निर्माण योग्यता की आवश्यकता को शिथिल करता है। केवल संघ वर्गों {{tmath|\mathsf{DSPACE}(O(s(n))}} एवं {{tmath|\mathsf{DSPACE}(o(s(n))}} को भिन्न करने के अतिरिक्त यह {{tmath|\mathsf{DSPACE}(f(n))}} से {{tmath|\mathsf{DSPACE}(g(n))}} को भिन्न करता है, जहाँ {{tmath|f(n)}} आर्बिटरी है {{tmath|O(s(n))}} फंक्शन एवं g(n) कंप्यूट योग्य {{tmath|o(s(n))}} फंक्शन है। इन फंक्शन को स्पेस-कंस्ट्रक्टीबल या मोनोटोन बढ़ाने की आवश्यकता नहीं है।
* यह यूनरी लैंग्वेज या टैली लैंग्वेज की पहचान करता है, जो वर्ग में है किन्तु दूसरे में नहीं है। मूल थ्योरम में, भिन्न करने वाली लैंग्वेज आर्बिटरी थी।
* इसकी आवश्यकता नहीं है, {{tmath|s(n)}} कम से कम log n होना चाहिए; यह कोई भी अन्य-नियतात्मक रूप से पूर्णतः स्पेस-कंस्ट्रक्टीबल कार्य हो सकता है।

==रिफाइनमेंट स्पेस हायरार्की ==

यदि स्पेस को वर्णमाला के आकार पर विचार किए बिना उपयोग की गई सेल की नंबर के रूप में मापा जाता है, तो {{tmath|1=\mathsf{SPACE}(f(n)) = \mathsf{SPACE}(O(f(n)))}} होता है, क्योंकि कोई भी बड़े वर्णमाला पर स्विच करके किसी भी रैखिक कम्प्रेशन को प्राप्त कर सकता है। चूँकि, बिट्स में स्पेस को मापने से, नियतात्मक स्पेस के लिए अधिक तीव्र पृथक्करण प्राप्त किया जा सकता है। गुणात्मक स्थिरांक तक परिभाषित होने के अतिरिक्त, स्पेस को अब योगात्मक स्थिरांक तक परिभाषित किया गया है। चूँकि, क्योंकि एक्सटर्नल स्पेस की किसी भी स्थिर मात्रा को कंटेंट्स को आंतरिक स्थिति में संग्रहीत करके बचाया जा सकता है, हमारे पास अभी भी {{tmath|1=\mathsf{SPACE}(f(n)) = \mathsf{SPACE}(f(n)+O(1))}}है।

मान लें कि f स्पेस-कंस्ट्रक्टीबल है। स्पेस निर्धारणात्मक है।
* ट्यूरिंग मशीनों सहित अनुक्रमिक कम्प्यूटेशनल मॉडल की विस्तृत विविधता के लिए, SPACE(f(n)-Big O Notation|ω(log(f(n)+n))) ⊊ SPACE(f(n)) है। यह तब भी मान्य है जब SPACE(f(n)-ω(log(f(n)+n))) को {{tmath|\mathsf{SPACE}(f(n))}} से किसी भिन्न कम्प्यूटेशनल मॉडल का उपयोग करके परिभाषित किया गया हो क्योंकि विभिन्न मॉडल {{tmath|O(\log(f(n)+n))}} स्पेस के साथ दूसरे का अनुकरण कर सकते हैं।
* कुछ कम्प्यूटेशनल मॉडल के लिए, हमारे पास SPACE(f(n)-ω(1)) ⊊ SPACE(f(n)) भी है। विशेष रूप से, यह ट्यूरिंग मशीनों के लिए प्रस्तावित होता है यदि हम वर्णमाला, इनपुट टेप पर हेड्स की नंबर, वर्कटेप पर हेड्स की नंबर (वर्कटेप का उपयोग करके) को उचित बनाते हैं, एवं वर्कटेप के विज़िट किए गए भाग के लिए सीमांकक जोड़ते हैं (जिसे स्पेस उपयोग में वृद्धि के बिना चेक किया जा सकता है)। SPACE(f(n)) इस विषय पर निर्भर नहीं करता है कि वर्कटेप अनंत है या अर्ध-अनंत है। हमारे पास निश्चित नंबर में वर्कटेप भी हो सकते हैं यदि f(n) या तो प्रति-टेप स्पेस उपयोग देने वाला स्पेस कंस्ट्रक्टीबल टपल है, या SPACE(f(n)-ω(log(f(n))) - कुल स्पेस उपयोग देने वाली कंस्ट्रक्टीबल नंबर है (प्रत्येक टेप की लंबाई को संग्रहीत करने के लिए ओवरहेड की गिनती नहीं है)।

प्रूफ स्पेस हायरार्की थ्योरम के प्रूफ के समान है, किन्तु दो कॉम्प्लिकेशन के साथ: सार्वभौमिक ट्यूरिंग मशीन को स्पेस-कुशल होना चाहिए, एवं विपरीत स्पेस-कुशल होना चाहिए। कोई सामान्यतः {{tmath|O(\log(space))}} स्पेस ओवरहेड, एवं उचित धारणाओं के अंतर्गत, {{tmath|O(1)}} स्पेस ओवरहेड (जो मशीन के सिम्युलेटेड होने पर निर्भर हो सकता है) के साथ सार्वभौमिक ट्यूरिंग मशीनों का निर्माण कर सकता है। रिवर्सल के लिए, मुख्य विषय यह है कि कैसे ज्ञात किया जाए कि सिम्युलेटेड मशीन अनंत (स्पेस-बाधित) लूप में प्रवेश करके अस्वीकार कर देती है। केवल चरणों की नंबर गिनने से स्पेस का उपयोग लगभग {{tmath|f(n)}} बढ़ जाता है। संभावित रूप से एक्सपोनेंशियल टाइम वृद्धि की कीमत पर, लूप को स्पेस-एफिशिएंसी से निम्नानुसार ज्ञात किया जा सकता है:<ref>{{cite conference | first = Michael | last = Sipser | title = अंतरिक्ष-बद्ध संगणनाओं को रोकना| book-title = Proceedings of the 19th Annual Symposium on Foundations of Computer Science | date = 1978}}</ref>

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

यह भी निर्धारित किया जा सकता है कि क्या मशीन स्पेस सीमा से अधिक हो गई है (स्पेस सीमा के अंदर लूपिंग के विपरीत) सभी कॉन्फ़िगरेशन पर पुनरावृत्ति करके एवं परीक्षण करके (पुनः [[गहराई-पहली खोज|डेप्थ-फर्स्ट सर्च]] का उपयोग करके) कि क्या इनिशियल कॉन्फ़िगरेशन उनमें से किसी की ओर ले जाता है।

== परिणाम ==

=== परिणाम 1 ===

किन्हीं दो फंक्शन <math>f_1</math>, <math>f_2: \mathbb{N} \longrightarrow
\mathbb{N}</math>, के लिए जहाँ <math>f_1(n)</math>, <math>o(f_2(n))</math> है, एवं <math>f_2</math> स्पेस-कंस्ट्रक्टिबल <math>\mathsf{SPACE}(f_1(n)) \subsetneq \mathsf{SPACE}(f_2(n))</math> है,

यह परिणाम हमें विभिन्न स्पेस कॉम्प्लेक्सिटी वर्गों को भिन्न करने की सुविधा देता है। किसी भी फंक्शन <math>n^k</math> के लिए किसी भी नेचुरल नंबर k के लिए स्पेस-कंस्ट्रक्टीबल है। इसलिए किन्हीं दो नेचुरल नंबर <math>k_1 < k_2</math> के लिए हम <math>\mathsf{SPACE}(n^{k_1}) \subsetneq \mathsf{SPACE}(n^{k_2})</math> प्रूफ कर सकते हैं। इस विचार को निम्नलिखित परिणाम में रियल नंबर्स के लिए बढ़ाया जा सकता है। यह पीस्पेस वर्ग के अंदर विस्तृत हायरार्की को प्रदर्शित करता है।

=== परिणाम 2 ===

किन्हीं दो नॉन नेगेटिव रियल नंबर्स के लिए <math>a_1 < a_2, \mathsf{SPACE}(n^{a_1})
\subsetneq \mathsf{SPACE}(n^{a_2})</math> है।

=== परिणाम 3 ===

:[[एनएल (जटिलता)|NL]]⊊ [[पीस्पेस|PSPACE]]

==== प्रूफ ====

सैविच का थ्योरम यह प्रदर्शित करता है <math>\mathsf{NL} \subseteq \mathsf{SPACE}(\log^2n)</math>, जबकि स्पेस हायरार्की थ्योरम <math>\mathsf{SPACE}(\log^2n) \subsetneq \mathsf{SPACE}(n)</math> प्रदर्शित करता है। इसका परिणाम इस तथ्य के साथ है कि TQBF ∉ NL क्योंकि टीक्यूबीएफ पीस्पेस-पूर्ण है।

यह दिखाने के लिए नॉन-डिटरमिनिस्टिक स्पेस हायरार्की थ्योरम का उपयोग करके भी प्रूफ किया जा सकता है कि एनएल ⊊ एनपीस्पेस, और सैविच के थ्योरम का उपयोग करके यह दिखाया जा सकता है कि पीस्पेस = एनपीस्पेस होता है।

=== परिणाम 4 ===

:PSPACE ⊊ [[एक्सस्पेस|EXPSPACE]]

यह अंतिम परिणाम उन डीसीडबल प्रोब्लेम्स के अस्तित्व को प्रदर्शित करता है जो कठिन हैं। दूसरे शब्दों में, उनके डिसिशन प्रोसीजर को पोलीनोमिअल स्पेस से अधिक उपयोग करना चाहिए।

=== परिणाम 5 ===

{{sans-serif|पीस्पेस}} में ऐसी प्रोब्लेम्स हैं जिनको सॉल्व करने के लिए आर्बिटरी रूप से बड़े घातांक की आवश्यकता होती है; इसलिए {{sans-serif|पीस्पेस}}, कुछ स्थिरांक k के लिए {{sans-serif|डीस्पेस}}(n<sup>k</sup>) में परिवर्तित नहीं होता है।

== यह भी देखें ==
* टाइम हायरार्की थ्योरम

== संदर्भ ==
{{reflist}}
*{{cite book | zbl=1193.68112 | last1=Arora | first1=Sanjeev | author-link1=Sanjeev Arora | last2=Barak | first2=Boaz | title=Computational complexity. A modern approach | publisher=[[Cambridge University Press]] | year=2009 | isbn=978-0-521-42426-4 }}
* [[Luca Trevisan]]. [http://www.cs.berkeley.edu/~luca/cs172-04/noteh.pdf Notes on Hierarchy Theorems]. Handout 7. CS172: Automata, Computability and Complexity. U.C. Berkeley. April 26, 2004.
* [[Viliam Geffert]]. [http://portal.acm.org/citation.cfm?id=763728 Space hierarchy theorem revised]. ''Theoretical Computer Science'', volume 295, number 1–3, p. 171-187. February 24, 2003.
* {{cite book | first = Michael | last = Sipser | author-link = Michael Sipser | year = 1997 | title = Introduction to the Theory of Computation | publisher = PWS Publishing | isbn = 0-534-94728-X | url-access = registration | url = https://archive.org/details/introductiontoth00sips }} Pages 306–310 of section 9.1: Hierarchy theorems.
* {{cite book | first=Christos | last=Papadimitriou | author-link = Christos Papadimitriou | year = 1993 | title = Computational Complexity | publisher = Addison Wesley | edition = 1st | isbn = 0-201-53082-1}} Section 7.2: The Hierarchy Theorem, pp. 143–146.

[[Category: प्रमाण युक्त लेख]] [[Category: संरचनात्मक जटिलता सिद्धांत]] [[Category: कम्प्यूटेशनल जटिलता सिद्धांत में प्रमेय]]

[[Category: Machine Translated Page]]
[[Category:Created On 25/07/2023]]
[[Category:Vigyan Ready]]