2-संतोषजनकता: Difference between revisions

[[कंप्यूटर विज्ञान]] में, '''2-संतोषजनकता''', 2-एसएटी या सिर्फ 2एसएटी वेरिएबल के जोड़े पर [[बाधा (गणित)]] की प्रणाली को संतुष्ट करने के लिए, वेरिएबल को मान निर्दिष्ट करने की [[कम्प्यूटेशनल समस्या]] है, जिनमें से प्रत्येक में दो संभावित मान होते हैं। यह सामान्य [[बूलियन संतुष्टि समस्या]] का विशेष स्तिथि है, जिसमें दो से अधिक वेरिएबल पर बाधाएं और [[बाधा संतुष्टि समस्या]]एं सम्मिलित हो सकती हैं, जो प्रत्येक वेरिएबल के मान के लिए दो से अधिक विकल्पों की अनुमति दे सकती हैं। किन्तु उन अधिक सामान्य समस्याओं के विपरीत, जो NP-पूर्ण हैं, जिसको कि 2-संतोषजनकता को बहुपद समय में हल किया जा सकता है।

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

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

[[कम्प्यूटेशनल जटिलता सिद्धांत|कम्प्यूटेशनल सम्मिश्रता सिद्धांत]] में, 2-संतोषजनकता [[एनएल-पूर्ण]] समस्या का उदाहरण प्रदान करती है, जिसे संचयन की लघुगणकीय मात्रा का उपयोग करके गैर-नियतात्मक रूप से हल किया जा सकता है और यह इस संसाधन में हल करने योग्य सबसे कठिन समस्याओं में से है। 2-संतोषजनकता उदाहरण के सभी समाधानों के सेट को [[माध्यिका ग्राफ]] की संरचना दी जा सकती है, किन्तु इन समाधानों की गिनती शार्प-P-पूर्ण| या P-पूर्ण है और इसलिए बहुपद-समय समाधान की उम्मीद नहीं है। यादृच्छिक उदाहरणों को हल करने योग्य से अघुलनशील उदाहरणों में तेज चरण संक्रमण से गुजरना पड़ता है क्योंकि वेरिएबल के लिए बाधाओं का अनुपात 1 से अधिक बढ़ जाता है, घटना अनुमानित है किन्तु संतुष्टि समस्या के अधिक सम्मिश्र रूपों के लिए अप्रमाणित है। 2-संतोषजनकता की कम्प्यूटेशनल रूप से कठिन विविधता, सत्य असाइनमेंट खोजता जो संतुष्ट बाधाओं की संख्या को अधिकतम करता है, अनुमानित एल्गोरिदम है जिसकी अधिकतमता अद्वितीय गेम अनुमान पर निर्भर करती है, और और कठिन भिन्नता, वास्तविक वेरिएबल की संख्या को कम करने वाला संतोषजनक असाइनमेंट खोजता , [[पैरामीटरयुक्त जटिलता|पैरामीटर युक्त सम्मिश्रता]] के लिए महत्वपूर्ण परीक्षण स्तिथि है।            

==समस्या प्रतिनिधित्व                                           ==

[[File:Implication graph.svg|thumb|upright=1.35|इस खंड में दिखाए गए उदाहरण 2-संतोषजनकता उदाहरण के लिए निहितार्थ ग्राफ़।]]इस प्रकार के विशेष प्रतिबंधित रूप के साथ [[बूलियन अभिव्यक्ति]] का उपयोग करके 2-संतोषजनकता समस्या का वर्णन किया जा सकता है। यह क्लॉज (तर्क) का [[तार्किक संयोजन]] ( बूलियन और ऑपरेशन) है, जहां प्रत्येक क्लॉज दो वेरिएबल या ऋणात्मक वेरिएबल का वियोजन ( बूलियन या ऑपरेशन) है। इस सूत्र में आने वाले वेरिएबल या उनके निषेधन को [[शाब्दिक (गणितीय तर्क)]] कहा जाता है।<ref name="cnf">{{citation|chapter=2. CNF Encodings|pages=75–98|first=Steven|last=Prestwich|title=Handbook of Satisfiability|volume=185|issue=Handbook of Satisfiability|series=Frontiers in Artificial Intelligence and Applications|publisher=IOS Press|editor1-first=Armin|editor1-last=Biere|editor2-first=Marijn|editor2-last=Heule|editor2-link=Marijn Heule|editor3-first=Hans|editor3-last=van Maaren|editor4-first=Toby|editor4-last=Walsh|chapter-url=https://books.google.com/books?id=YVSM3sxhBhcC&pg=PA75|year=2009|doi=10.3233/978-1-58603-929-5-75|isbn=978-1-58603-929-5|s2cid=31666330 }}.</ref> उदाहरण के लिए, निम्नलिखित सूत्र संयोजक सामान्य रूप में है, जिसमें सात वेरिएबल , ग्यारह उपवाक्य और 22 अक्षर हैं:

2-संतोषजनकता की समस्या इन वेरिएबलों के लिए [[सत्य असाइनमेंट|ट्रूथ असाइनमेंट]] खोजता है जो पूरे सूत्र को सत्य बनाता है। ऐसा असाइनमेंट यह चुनता है कि प्रत्येक वेरिएबल को सही या गलत बनाया जाए, जिससे कि प्रत्येक खंड में कम से कम अक्षर सत्य हो जाए। ऊपर दिखाए गए अभिव्यक्ति के लिए, संभावित संतोषजनक असाइनमेंट वह है जो सभी सात वेरिएबलों को सत्य पर सेट करता है। प्रत्येक खंड में कम से कम गैर-ऋणात्मक वेरिएबल होता है, इसलिए यह असाइनमेंट प्रत्येक खंड को संतुष्ट करता है। सभी वेरिएबल्स को सेट करने की 15 अन्य विधियाँ भी हैं जिससे सूत्र सत्य हो जाए। इसलिए, इस अभिव्यक्ति द्वारा दर्शाया गया 2-संतोषजनक उदाहरण संतोषजनक है।

इस रूप में सूत्रों को 2-सीएनएफ सूत्र के रूप में जाना जाता है। इस नाम में 2 प्रति खंड शाब्दिकों की संख्या को दर्शाता है, और सीएनएफ संयोजक सामान्य रूप के लिए है, विच्छेदन के संयोजन के रूप में प्रकार की बूलियन अभिव्यक्ति है।<ref name="cnf"/> कैलिफ़ोर्निया विश्वविद्यालय, डेविस के गणितज्ञ मेल्वेन आर. क्रॉम के कार्य के पश्चात, उन्हें क्रॉम सूत्र भी कहा जाता है, जिनका 1967 का पेपर 2-संतोषजनकता समस्या पर सबसे प्रारम्भिक कार्यों में से था।<ref name="Krom1967">{{citation

 

2-सीएनएफ सूत्र में प्रत्येक खंड वेरिएबल या अस्वीकृत वेरिएबल से दूसरे में निहितार्थ के लिए [[तार्किक तुल्यता]] है। उदाहरण के लिए, उदाहरण में दूसरा खंड तीन समकक्ष विधियों में से किसी में लिखा जा सकता है:

<math display="block">(x_0\lor\lnot x_3) \;\equiv\; (\lnot x_0\Rightarrow\lnot x_3) \;\equiv\; (x_3\Rightarrow x_0).</math>

इन विभिन्न प्रकार के ऑपरेशनों के मध्य इस तुल्यता के कारण, 2-संतोषजनकता उदाहरण को निहितार्थ सामान्य रूप में भी लिखा जा सकता है, जिसमें हम संयोजनात्मक सामान्य रूप में प्रत्येक या खंड को उन दो निहितार्थों से प्रतिस्थापित करते हैं जिनके लिए यह समतुल्य है।<ref>{{citation|title=Artificial Intelligence: A Modern Approach|page=282|series=Prentice Hall series in artificial intelligence|first1=Stuart Jonathan|last1=Russell|first2=Peter|last2=Norvig|publisher=Prentice Hall|year=2010|isbn=978-0-13-604259-4}}.</ref>

 

2-संतोषजनकता उदाहरण का वर्णन करने का तीसरा, अधिक ग्राफिकल विधि निहितार्थ ग्राफ के रूप में है। निहितार्थ ग्राफ निर्देशित ग्राफ है जिसमें प्रति वेरिएबल या ऋणात्मक वेरिएबल में शीर्ष (ग्राफ सिद्धांत) होता है, और शीर्ष को दूसरे से जोड़ने वाला किनारा होता है जब भी संबंधित वेरिएबल उदाहरण के निहितार्थ सामान्य रूप में निहितार्थ से संबंधित होते हैं। निहितार्थ ग्राफ [[तिरछा-सममित ग्राफ|विषम -सममित ग्राफ]] होना चाहिए, जिसका अर्थ है कि इसमें [[ग्राफ ऑटोमोर्फिज्म]] है जो प्रत्येक वेरिएबल को उसके निषेध में ले जाता है और सभी किनारों के झुकाव को विपरीत कर देता है।<ref name="APT79">{{citation

2-संतोषजनकता समस्या को हल करने के लिए अनेक एल्गोरिदम ज्ञात हैं। उनमें से सबसे कुशल रैखिक समय लेते हैं।<ref name="Krom1967"/><ref name="APT79"/><ref name="EIS76"/>

{{harvtxt|क्रोम|1967}} 2-संतोषजनक उदाहरणों को हल करने के लिए निम्नलिखित बहुपद समय निर्णय प्रक्रिया का वर्णन किया गया है।<ref name="Krom1967"/>

मान लीजिए कि 2-संतोषजनक उदाहरण में दो खंड हैं जो दोनों ही वेरिएबल x का उपयोग करते हैं, किन्तु x को खंड में नकार दिया गया है और दूसरे में नहीं। फिर दोनों खंडों को मिलाकर तीसरा खंड तैयार किया जा सकता है, जिसमें दो खंडों में दो अन्य शाब्दिक अर्थ होंगे; जब पहले दो खंड संतुष्ट हों तो यह तीसरा खंड भी संतुष्ट होना चाहिए। उदाहरण के लिए, हम खंडों <math>(a\lor b)</math> और <math>(\lnot b\lor\lnot c)</math> को जोड़ सकते हैं इस प्रकार <math>(a\lor\lnot c)</math> उपवाक्य का निर्माण करें . 2-सीएनएफ सूत्र के निहितार्थ रूप के संदर्भ में, यह नियम दो निहितार्थ खोजने <math>\lnot a\Rightarrow b</math> और <math>b\Rightarrow \lnot c</math> के समान है, और [[सकर्मक संबंध]] द्वारा तीसरे निहितार्थ <math>\lnot a\Rightarrow \lnot c</math> का अनुमान लगाना होता है .<ref name="Krom1967"/>

क्रॉम लिखते हैं कि सूत्र <math>(x\lor x)</math> और <math> (\lnot x\lor\lnot x)</math> सुसंगत है यदि इस अनुमान नियम को निरंतर प्रयुक्त करने से दोनों खंड उत्पन्न नहीं हो सकते हैं , किसी भी <math> x</math>वेरिएबल के लिए. जैसा कि उन्होंने सिद्ध किया है, 2-सीएनएफ सूत्र तभी संतोषजनक है जब यह सुसंगत हो। क्योंकि, यदि कोई सूत्र सुसंगत नहीं है, तो दोनों खंडों को संतुष्ट करना संभव नहीं है <math> (x\lor x)</math> और <math>(\lnot x\lor\lnot x)</math> इसके साथ ही। और, यदि यह सुसंगत है, तो रूप के खंड को निरंतर जोड़कर सूत्र को बढ़ाया जा सकता है <math> (x\lor x)</math> या <math> (\lnot x\lor\lnot x)</math> समय में, प्रत्येक चरण में एकरूपता बनाए रखना, जब तक कि इसमें प्रत्येक वेरिएबल के लिए ऐसा खंड सम्मिलित न हो जाए। इन विस्तार चरणों में से प्रत्येक में, स्थिरता बनाए रखते हुए इन दो खंडों में से को सदैव जोड़ा जा सकता है, यदि नहीं तो अनुमान नियम का उपयोग करके अन्य खंड उत्पन्न किया जा सकता है। पुनः जब सभी वेरिएबल्स के सूत्र में इस रूप का खंड होता है, तो वेरिएबल सेट करके सभी <math> x</math> वेरिएबल्स का संतोषजनक असाइनमेंट उत्पन्न किया जा सकता है यदि सूत्र में खंड सम्मिलित है तो <math> (x\lor x)</math> सत्य है और यदि सूत्र में खंड सम्मिलित है तो इसे गलत पर सेट <math>(\lnot x\lor\lnot x)</math> करना होता है .<ref name="Krom1967"/>

क्रॉम मुख्य रूप से एल्गोरिदम की दक्षता के अतिरिक्त अनुमान नियमों की प्रणालियों की [[पूर्णता (तर्क)]] से चिंतित था। चूँकि, उनकी पद्धति 2-संतोषजनकता समस्याओं को हल करने के लिए बहुपद समयबद्धता की ओर ले जाती है। समान वेरिएबल का उपयोग करने वाले सभी खंडों को साथ समूहित करके, और खंडों की प्रत्येक जोड़ी पर अनुमान नियम प्रयुक्त करके, किसी दिए गए 2-सीएनएफ उदाहरण से संभव सभी अनुमान खोजता संभव है, और यह परीक्षण करना संभव है कि क्या यह सुसंगत है, कुल समय में {{math|O(''n''³)}},है जहाँ {{math|''n''}} उदाहरण में वेरिएबलों की संख्या है। यह सूत्र वेरिएबलों की संख्या को गुणा करने से {{math|O(''n''²)}} प्राप्त होता है किसी दिए गए वेरिएबल को सम्मिलित करने वाले खंडों के जोड़े की संख्या, जिस पर अनुमान नियम प्रयुक्त किया जा सकता है। इस प्रकार, यह निर्धारित करना संभव है कि दिया गया 2-सीएनएफ उदाहरण समय में संतोषजनक या नहीं {{math|O(''n''³)}} है . क्योंकि क्रॉम की विधि का उपयोग करके संतोषजनक असाइनमेंट खोजने में अनुक्रम सम्मिलित होता है {{math|O(''n'')}} निरंतरता की जांच, इसमें समय लगेगा {{math|O(''n''⁴)}}. {{harvtxt|इवेन |इटाई|शमीर|1976}} तेज़ समय सीमा का उद्धरण दें {{math|O(''n''²)}} इस एल्गोरिथम के लिए, इसके संचालन के अधिक सावधानीपूर्वक क्रम पर आधारित है। फिर भी, पश्चात के रैखिक समय एल्गोरिदम द्वारा इस छोटी समय सीमा में भी अधिक सुधार {{harvtxt|इवेन |इटाई|शमीर|1976}} और {{harvtxt|एस्पवॉल|प्लास|टारजन|1979}} के द्वारा किया गया था |

2-संतोषजनकता उदाहरण के निहितार्थ ग्राफ के संदर्भ में, क्रॉम के अनुमान नियम की व्याख्या ग्राफ के संक्रमणीय समापन के निर्माण के रूप में की जा सकती है। जैसा {{harvtxt|कुक |1971}} देखता है, इसे रिज़ॉल्यूशन (तर्क) के सिद्धांत का उपयोग करके संतुष्टि समस्याओं को हल करने के लिए डेविस-पुटनम एल्गोरिदम के उदाहरण के रूप में भी देखा जा सकता है। इसकी शुद्धता डेविस-पुटनम एल्गोरिथ्म की अधिक सामान्य शुद्धता से अनुसरण करती है। इसकी बहुपद समय सीमा इस तथ्य से उत्पन्न होती है कि प्रत्येक रिज़ॉल्यूशन चरण उदाहरण में खंडों की संख्या बढ़ाता है, जो कि वेरिएबल की संख्या के द्विघात फलन द्वारा ऊपरी सीमा पर होता है।<ref>{{citation|first=Stephen A.|last=Cook|author-link=Stephen Cook|contribution=The complexity of theorem-proving procedures|title=Proc. 3rd ACM Symp. Theory of Computing (STOC)|year=1971|pages=151–158|doi=10.1145/800157.805047|s2cid=7573663}}.</ref>

{{harvtxt|इवेन |इटाई|शमीर|1976}} [[बाइनरी डेटा]] और जोड़ीदार बाधाओं के साथ बाधा संतुष्टि समस्याओं को हल करने के लिए सीमित बैकट्रैकिंग से जुड़ी तकनीक का वर्णन करता है जहाँ वह इस तकनीक को कक्षा समय-निर्धारण की समस्या पर प्रयुक्त करते हैं, किन्तु वह यह भी देखते हैं कि यह 2-एसएटी सहित अन्य समस्याओं पर भी प्रयुक्त होती है।<ref name="EIS76">{{citation|first1=S.|last1=Even|author1-link=Shimon Even|first2=A.|last2=Itai|first3=A.|last3=Shamir|author3-link=Adi Shamir|title=On the complexity of time table and multi-commodity flow problems|journal=[[SIAM Journal on Computing]]|volume=5|issue=4|year=1976|pages=691–703|doi=10.1137/0205048}}.</ref>

उनके दृष्टिकोण का मूल विचार समय में वेरिएबल, आंशिक सत्य असाइनमेंट का निर्माण करना है। एल्गोरिदम के कुछ चरण चयन बिंदु हैं, ऐसे बिंदु जिन पर वेरिएबल को दो भिन्न -भिन्न सत्य मानों में से कोई दिया जा सकता है, और एल्गोरिदम के पश्चात के चरणों के कारण यह इन विकल्प बिंदुओं में से किसी पर पीछे जा सकता है। चूँकि , केवल सबसे आधुनिक विकल्प को ही वापस लिया जा सकता है। नवीनतम से पहले किए गए सभी विकल्प स्थायी हैं।<ref name="EIS76" />

*यदि कोई ऐसा खंड है जिसके दोनों वेरिएबल पहले से ही सेट हैं, इस तरह से जो खंड को गलत सिद्ध करता है, तो एल्गोरिदम अपने सबसे हालिया विकल्प बिंदु पर वापस आ जाता है, उस विकल्प के पश्चात से किए गए असाइनमेंट को पूर्ववत कर देता है, और उस विकल्प पर किए गए निर्णय को विपरीत देता है। यदि कोई विकल्प बिंदु नहीं है, या यदि एल्गोरिदम पहले से ही सबसे हालिया विकल्प बिंदु पर पीछे हट गया है, तो यह खोज को रोक देता है और रिपोर्ट करता है कि इनपुट 2-सीएनएफ सूत्र असंतोषजनक है।

*यदि कोई ऐसा खंड है जिसमें खंड के दो वेरिएबलों में से पहले ही सेट किया जा चुका है, और खंड अभी भी या तो सत्य या गलत हो सकता है, तो दूसरा वेरिएबल इस तरह से सेट किया जाता है जो खंड को सत्य बनने के लिए विवश करता है।

*शेष स्तिथि में, प्