2-संतोषजनकता: Difference between revisions
No edit summary |
No edit summary |
||
Line 1: | Line 1: | ||
{{short description|Logic problem, AND of pairwise ORs}} | {{short description|Logic problem, AND of pairwise ORs}} | ||
[[कंप्यूटर विज्ञान]] में, 2-संतुष्टि, 2- | [[कंप्यूटर विज्ञान]] में, 2-संतुष्टि, 2-एसएटी या सिर्फ 2एसएटी वेरिएबल के जोड़े पर [[बाधा (गणित)]] की प्रणाली को संतुष्ट करने के लिए, वेरिएबल को मान निर्दिष्ट करने की [[कम्प्यूटेशनल समस्या]] है, जिनमें से प्रत्येक में दो संभावित मान होते हैं। यह सामान्य [[बूलियन संतुष्टि समस्या]] का विशेष स्तिथि है, जिसमें दो से अधिक वेरिएबल पर बाधाएं और [[बाधा संतुष्टि समस्या]]एं सम्मिलित हो सकती हैं, जो प्रत्येक वेरिएबल के मान के लिए दो से अधिक विकल्पों की अनुमति दे सकती हैं। किन्तु उन अधिक सामान्य समस्याओं के विपरीत, जो एनपी-पूर्ण हैं, जिसको कि 2-संतुष्टि को बहुपद समय में हल किया जा सकता है। | ||
2-संतुष्टि समस्या के उदाहरणों को | 2-संतुष्टि समस्या के उदाहरणों को सामान्यतः विशेष प्रकार के [[बूलियन तर्क]] के रूप में व्यक्त किया जाता है, जिसे [[संयोजक सामान्य रूप]] (2-सीएनएफ) या क्रॉम सूत्र कहा जाता है। वैकल्पिक रूप से, उन्हें विशेष प्रकार के [[निर्देशित ग्राफ]], [[निहितार्थ ग्राफ]] के रूप में व्यक्त किया जा सकता है, जो उदाहरण के वेरिएबल और उनके निषेधों को ग्राफ में शीर्ष के रूप में व्यक्त करता है, और वेरिएबल के जोड़े पर बाधाओं को निर्देशित किनारों के रूप में व्यक्त करता है। इन दोनों प्रकार के इनपुट को [[रैखिक समय]] में हल किया जा सकता है, या तो [[ बैक ट्रैकिंग |बैक ट्रैकिंग]] पर आधारित विधि द्वारा या निहितार्थ ग्राफ के दृढ़ता से जुड़े अवयवों का उपयोग करके। रिज़ॉल्यूशन (तर्क), अतिरिक्त वैध बाधाओं को बनाने के लिए बाधाओं के जोड़े को संयोजित करने की विधि, बहुपद समय समाधान की ओर भी ले जाती है। 2-संतोषजनक समस्याएं संयोजक सामान्य रूप सूत्रों के दो प्रमुख उपवर्गों में से प्रदान करती हैं जिन्हें बहुपद समय में हल किया जा सकता है; दो उपवर्गों में से दूसरा हॉर्न-संतुष्टि है । | ||
2-संतुष्टि को ज्यामिति और विज़ुअलाइज़ेशन समस्याओं पर | 2-संतुष्टि को ज्यामिति और विज़ुअलाइज़ेशन समस्याओं पर प्रयुक्त किया जा सकता है जिसमें वस्तुओं के संग्रह में प्रत्येक के दो संभावित स्थान होते हैं और लक्ष्य प्रत्येक वस्तु के लिए प्लेसमेंट ढूंढना है जो अन्य वस्तुओं के साथ ओवरलैप होने से बचाता है। अन्य अनुप्रयोगों में क्लस्टर के व्यास के योग को कम करने के लिए क्लस्टरिंग डेटा, कक्षा और खेल शेड्यूलिंग और उनके क्रॉस-सेक्शन के बारे में जानकारी से आकृतियों को पुनर्प्राप्त करना सम्मिलित है। | ||
[[कम्प्यूटेशनल जटिलता सिद्धांत]] में, 2-संतुष्टि [[एनएल-पूर्ण]] समस्या का उदाहरण प्रदान करती है, जिसे भंडारण की लघुगणकीय मात्रा का उपयोग करके गैर-नियतात्मक रूप से हल किया जा सकता है और यह इस संसाधन में हल करने योग्य सबसे कठिन समस्याओं में से है। 2-संतुष्टि उदाहरण के सभी समाधानों के सेट को [[माध्यिका ग्राफ]] की संरचना दी जा सकती है, | [[कम्प्यूटेशनल जटिलता सिद्धांत|कम्प्यूटेशनल सम्मिश्रता सिद्धांत]] में, 2-संतुष्टि [[एनएल-पूर्ण]] समस्या का उदाहरण प्रदान करती है, जिसे भंडारण की लघुगणकीय मात्रा का उपयोग करके गैर-नियतात्मक रूप से हल किया जा सकता है और यह इस संसाधन में हल करने योग्य सबसे कठिन समस्याओं में से है। 2-संतुष्टि उदाहरण के सभी समाधानों के सेट को [[माध्यिका ग्राफ]] की संरचना दी जा सकती है, किन्तु इन समाधानों की गिनती शार्प-P-पूर्ण| या P-पूर्ण है और इसलिए बहुपद-समय समाधान की उम्मीद नहीं है। यादृच्छिक उदाहरणों को हल करने योग्य से अघुलनशील उदाहरणों में तेज चरण संक्रमण से गुजरना पड़ता है क्योंकि वेरिएबल के लिए बाधाओं का अनुपात 1 से अधिक बढ़ जाता है, घटना अनुमानित है किन्तु संतुष्टि समस्या के अधिक सम्मिश्र रूपों के लिए अप्रमाणित है। 2-संतोषजनकता की कम्प्यूटेशनल रूप से कठिन विविधता, सत्य असाइनमेंट ढूंढना जो संतुष्ट बाधाओं की संख्या को अधिकतम करता है, अनुमानित एल्गोरिदम है जिसकी अधिकतमता अद्वितीय गेम अनुमान पर निर्भर करती है, और और कठिन भिन्नता, वास्तविक वेरिएबल की संख्या को कम करने वाला संतोषजनक असाइनमेंट ढूंढना, [[पैरामीटरयुक्त जटिलता|पैरामीटरयुक्त सम्मिश्रता]] के लिए महत्वपूर्ण परीक्षण स्तिथि है। | ||
==समस्या प्रतिनिधित्व== | ==समस्या प्रतिनिधित्व == | ||
[[File:Implication graph.svg|thumb|upright=1.35|इस खंड में दिखाए गए उदाहरण 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 अक्षर हैं: | ||
<math display=block> | <math display=block> | ||
\begin{align} | \begin{align} | ||
Line 17: | Line 17: | ||
\end{align} | \end{align} | ||
</math> | </math> | ||
2-संतुष्टि की समस्या इन | 2-संतुष्टि की समस्या इन वेरिएबलों के लिए [[सत्य असाइनमेंट|ट्रूथ असाइनमेंट]] ढूंढना है जो पूरे सूत्र को सत्य बनाता है। ऐसा असाइनमेंट यह चुनता है कि प्रत्येक वेरिएबल को सही या गलत बनाया जाए, जिससे कि प्रत्येक खंड में कम से कम अक्षर सत्य हो जाए। ऊपर दिखाए गए अभिव्यक्ति के लिए, संभावित संतोषजनक असाइनमेंट वह है जो सभी सात वेरिएबलों को सत्य पर सेट करता है। प्रत्येक खंड में कम से कम गैर-ऋणात्मक वेरिएबल होता है, इसलिए यह असाइनमेंट प्रत्येक खंड को संतुष्ट करता है। सभी वेरिएबल्स को सेट करने की 15 अन्य विधियाँ भी हैं जिससे सूत्र सत्य हो जाए। इसलिए, इस अभिव्यक्ति द्वारा दर्शाया गया 2-संतोषजनक उदाहरण संतोषजनक है। | ||
इस रूप में सूत्रों को 2- | इस रूप में सूत्रों को 2-सीएनएफ सूत्र के रूप में जाना जाता है। इस नाम में 2 प्रति खंड शाब्दिकों की संख्या को दर्शाता है, और सीएनएफ संयोजक सामान्य रूप के लिए है, विच्छेदन के संयोजन के रूप में प्रकार की बूलियन अभिव्यक्ति है।<ref name="cnf"/> कैलिफ़ोर्निया विश्वविद्यालय, डेविस के गणितज्ञ मेल्वेन आर. क्रॉम के कार्य के पश्चात, उन्हें क्रॉम सूत्र भी कहा जाता है, जिनका 1967 का पेपर 2-संतुष्टि समस्या पर सबसे शुरुआती कार्यों में से था।<ref name="Krom1967">{{citation | ||
| last1 = Krom | first1 = Melven R. | | last1 = Krom | first1 = Melven R. | ||
| title = The Decision Problem for a Class of First-Order Formulas in Which all Disjunctions are Binary | | title = The Decision Problem for a Class of First-Order Formulas in Which all Disjunctions are Binary | ||
Line 29: | Line 29: | ||
| doi = 10.1002/malq.19670130104 | | doi = 10.1002/malq.19670130104 | ||
}}.</ref> | }}.</ref> | ||
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-सीएनएफ सूत्र में प्रत्येक खंड वेरिएबल या अस्वीकृत वेरिएबल से दूसरे में निहितार्थ के लिए [[तार्किक तुल्यता]] है। उदाहरण के लिए, उदाहरण में दूसरा खंड तीन समकक्ष विधियों में से किसी में लिखा जा सकता है: | ||
<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>{{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-संतुष्टि उदाहरण का वर्णन करने का तीसरा, अधिक ग्राफिकल | |||
2-संतुष्टि उदाहरण का वर्णन करने का तीसरा, अधिक ग्राफिकल विधि निहितार्थ ग्राफ के रूप में है। निहितार्थ ग्राफ निर्देशित ग्राफ है जिसमें प्रति वेरिएबल या ऋणात्मक वेरिएबल में शीर्ष (ग्राफ सिद्धांत) होता है, और शीर्ष को दूसरे से जोड़ने वाला किनारा होता है जब भी संबंधित वेरिएबल उदाहरण के निहितार्थ सामान्य रूप में निहितार्थ से संबंधित होते हैं। निहितार्थ ग्राफ [[तिरछा-सममित ग्राफ]] होना चाहिए, जिसका अर्थ है कि इसमें [[ग्राफ ऑटोमोर्फिज्म]] है जो प्रत्येक वेरिएबल को उसके निषेध में ले जाता है और सभी किनारों के झुकाव को उलट देता है।<ref name="APT79">{{citation | |||
| last1 = Aspvall | first1 = Bengt | | last1 = Aspvall | first1 = Bengt | ||
| last2 = Plass | first2 = Michael F. | | last2 = Plass | first2 = Michael F. | ||
Line 41: | Line 43: | ||
| volume = 8 | issue = 3 | pages = 121–123 | year = 1979 | | volume = 8 | issue = 3 | pages = 121–123 | year = 1979 | ||
| doi = 10.1016/0020-0190(79)90002-4}}.</ref> | | doi = 10.1016/0020-0190(79)90002-4}}.</ref> | ||
==एल्गोरिदम== | ==एल्गोरिदम== | ||
2-संतुष्टि समस्या को हल करने के लिए | 2-संतुष्टि समस्या को हल करने के लिए अनेक एल्गोरिदम ज्ञात हैं। उनमें से सबसे कुशल रैखिक समय लेते हैं।<ref name="Krom1967"/><ref name="APT79"/><ref name="EIS76"/> | ||
===संकल्प और सकर्मक समापन=== | ===संकल्प और सकर्मक समापन=== | ||
{{harvtxt| | {{harvtxt|क्रोम|1967}} 2-संतोषजनक उदाहरणों को हल करने के लिए निम्नलिखित बहुपद समय निर्णय प्रक्रिया का वर्णन किया गया है।<ref name="Krom1967"/> | ||
मान लीजिए कि 2-संतोषजनक उदाहरण में दो खंड हैं जो दोनों ही | मान लीजिए कि 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''<sup>3</sup>)}}, जहाँ {{math|''n''}} उदाहरण में वेरिएबलों की संख्या है। यह सूत्र वेरिएबलों की संख्या को गुणा करने से {{math|O(''n''<sup>2</sup>)}} प्राप्त होता है किसी दिए गए वेरिएबल को सम्मिलित करने वाले खंडों के जोड़े की संख्या, जिस पर अनुमान नियम प्रयुक्त किया जा सकता है। इस प्रकार, यह निर्धारित करना संभव है कि दिया गया 2-सीएनएफ उदाहरण समय में संतोषजनक या नहीं {{math|O(''n''<sup>3</sup>)}} है . क्योंकि क्रॉम की विधि का उपयोग करके संतोषजनक असाइनमेंट खोजने में अनुक्रम सम्मिलित होता है {{math|O(''n'')}} निरंतरता की जांच, इसमें समय लगेगा {{math|O(''n''<sup>4</sup>)}}. {{harvtxt|इवेन |इटाई|शमीर|1976}} तेज़ समय सीमा का उद्धरण दें {{math|O(''n''<sup>2</sup>)}} इस एल्गोरिथम के लिए, इसके संचालन के अधिक सावधानीपूर्वक क्रम पर आधारित है। फिर भी, पश्चात के रैखिक समय एल्गोरिदम द्वारा इस छोटी समय सीमा में भी अधिक सुधार किया गया था {{harvtxt|इवेन |इटाई|शमीर|1976}} और {{harvtxt|एस्पवॉल|प्लास|टारजन|1979}}. | ||
2-संतुष्टि उदाहरण के निहितार्थ ग्राफ के संदर्भ में, क्रॉम के अनुमान नियम की व्याख्या ग्राफ के संक्रमणीय समापन के निर्माण के रूप में की जा सकती है। जैसा {{harvtxt| | 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| | {{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-सीएनएफ फॉर्मूला असंतोषजनक है। | |||
*यदि कोई ऐसा खंड है जिसमें खंड के दो वेरिएबलों में से पहले ही सेट किया जा चुका है, और खंड अभी भी या तो सत्य या गलत हो सकता है, तो दूसरा वेरिएबल इस तरह से सेट किया जाता है जो खंड को सत्य बनने के लिए मजबूर करता है। | |||
*शेष मामले में, प्रत्येक खंड के या तो सत्य होने की गारंटी है, चाहे शेष वेरिएबल कैसे भी निर्दिष्ट किए गए हों, या इसके दो वेरिएबल में से किसी को भी अभी तक निर्दिष्ट नहीं किया गया है। इस मामले में एल्गोरिदम नया विकल्प बिंदु बनाता है और किसी भी अनअसाइन किए गए वेरिएबल को मनमाने ढंग से चुने गए मान पर सेट करता है। | |||
सहज रूप से, एल्गोरिथ्म अपने प्रत्येक विकल्प को चुनने के पश्चात अनुमान की सभी श्रृंखलाओं का पालन करता है। इससे या तो विरोधाभास पैदा होता है और कदम पीछे हट जाता है, या, यदि कोई विरोधाभास नहीं निकलता है, तो इसका मतलब यह है कि चुनाव सही था जो संतोषजनक असाइनमेंट की ओर ले जाता है। इसलिए, एल्गोरिदम या तो सही ढंग से संतोषजनक असाइनमेंट पाता है या यह सही ढंग से निर्धारित करता है कि इनपुट असंतोषजनक है।<ref name="EIS76" /> | |||
यहां तक कि एट अल. इस एल्गोरिथम को कुशलतापूर्वक कैसे कार्यान्वित किया जाए, इसका विस्तार से वर्णन नहीं किया गया। वे केवल यह बताते हैं कि किसी भी निर्णय के निहितार्थ खोजने के लिए उपयुक्त डेटा संरचनाओं का उपयोग करके, एल्गोरिदम के प्रत्येक चरण (बैकट्रैकिंग के अलावा) को जल्दी से निष्पादित किया जा सकता है। चूँकि , कुछ इनपुट के कारण एल्गोरिदम अनेक बार बैकट्रैक कर सकता है, हर बार बैकट्रैकिंग से पहले अनेक चरण निष्पादित करता है, इसलिए इसकी समग्र सम्मिश्र ता अरेखीय हो सकती है। इस समस्या से बचने के लिए, वे एल्गोरिदम को संशोधित करते हैं जिससे , प्रत्येक विकल्प बिंदु पर पहुंचने के पश्चात, यह विकल्प बिंदु पर वेरिएबल सेट के लिए दो असाइनमेंट का साथ परीक्षण करना शुरू कर दे, दोनों असाइनमेंट में से प्रत्येक पर समान संख्या में चरण खर्च करें। जैसे ही इन दो असाइनमेंट में से का परीक्षण और विकल्प बिंदु बनाता है, दूसरा परीक्षण रोक दिया जाता है, जिससे एल्गोरिदम के किसी भी चरण में बैकट्रैकिंग ट्री की केवल दो शाखाएं हों जिनका अभी भी परीक्षण किया जा रहा हो। इस प्रकार, किसी भी वेरिएबल के लिए दो परीक्षण करने में बिताया गया कुल समय इनपुट सूत्र के उन वेरिएबलों और खंडों की संख्या के समानुपाती होता है जिनके मान स्थायी रूप से निर्दिष्ट होते हैं। परिणामस्वरूप, एल्गोरिथ्म कुल मिलाकर रैखिक समय लेता है।<ref name="EIS76" /> | |||
===मजबूती से जुड़े घटक=== | ===मजबूती से जुड़े घटक=== | ||
{{harvtxt| | {{harvtxt|एस्पवॉल|प्लास|टारजन|1979}} ग्राफ़ सिद्धांत से दृढ़ता से जुड़े अवयवों की धारणा के आधार पर, 2-संतोषजनक उदाहरणों को हल करने के लिए सरल रैखिक समय प्रक्रिया मिली।<ref name="APT79"/> | ||
एक निर्देशित ग्राफ़ में दो शीर्षों को एक-दूसरे से मजबूती से जुड़ा हुआ माना जाता है यदि से दूसरे तक कोई निर्देशित पथ हो और इसके विपरीत। यह तुल्यता संबंध है, और ग्राफ़ के शीर्षों को दृढ़ता से जुड़े | एक निर्देशित ग्राफ़ में दो शीर्षों को एक-दूसरे से मजबूती से जुड़ा हुआ माना जाता है यदि से दूसरे तक कोई निर्देशित पथ हो और इसके विपरीत। यह तुल्यता संबंध है, और ग्राफ़ के शीर्षों को दृढ़ता से जुड़े अवयवों , उपसमुच्चयों में विभाजित किया जा सकता है जिनके भीतर प्रत्येक दो शीर्ष दृढ़ता से जुड़े हुए हैं। [[गहराई-पहली खोज]] के आधार पर ग्राफ़ के दृढ़ता से जुड़े अवयवों को खोजने के लिए अनेक कुशल रैखिक समय एल्गोरिदम हैं: टार्जन के दृढ़ता से जुड़े घटक एल्गोरिदम<ref>{{citation|first=Robert E.|last=Tarjan|author-link=Robert Tarjan|title=Depth-first search and linear graph algorithms|journal=[[SIAM Journal on Computing]]|volume=1|year=1972|issue=2|pages=146–160|doi=10.1137/0201010|s2cid=16467262 }}.</ref> और [[पथ-आधारित मजबूत घटक एल्गोरिदम]]<ref>First published by {{citation | ||
| last1 = Cheriyan | first1 = J. | | last1 = Cheriyan | first1 = J. | ||
| last2 = Mehlhorn | first2 = K. | author2-link = Kurt Mehlhorn | | last2 = Mehlhorn | first2 = K. | author2-link = Kurt Mehlhorn | ||
Line 95: | Line 100: | ||
| title = Discrete Math. and its Applications: Handbook of Graph Theory | | title = Discrete Math. and its Applications: Handbook of Graph Theory | ||
| volume = 25 | | volume = 25 | ||
| year = 2003}}.</ref> प्रत्येक एकल गहराई-पहली खोज करता है। कोसाराजू का एल्गोरिदम दो गहराई-पहली खोज करता है, | | year = 2003}}.</ref> प्रत्येक एकल गहराई-पहली खोज करता है। कोसाराजू का एल्गोरिदम दो गहराई-पहली खोज करता है, किन्तु यह बहुत सरल है। | ||
निहितार्थ ग्राफ के संदर्भ में, जब भी शाब्दिक से दूसरे और इसके विपरीत निहितार्थ की श्रृंखला मौजूद होती है, तो दो शाब्दिक ही दृढ़ता से जुड़े घटक से संबंधित होते हैं। इसलिए, दिए गए 2-संतुष्टि उदाहरण के लिए किसी भी संतोषजनक असाइनमेंट में दो शाब्दिकों का समान | निहितार्थ ग्राफ के संदर्भ में, जब भी शाब्दिक से दूसरे और इसके विपरीत निहितार्थ की श्रृंखला मौजूद होती है, तो दो शाब्दिक ही दृढ़ता से जुड़े घटक से संबंधित होते हैं। इसलिए, दिए गए 2-संतुष्टि उदाहरण के लिए किसी भी संतोषजनक असाइनमेंट में दो शाब्दिकों का समान मान होना चाहिए। विशेष रूप से, यदि वेरिएबल और उसका निषेध दोनों ही मजबूती से जुड़े घटक से संबंधित हैं, तो उदाहरण को संतुष्ट नहीं किया जा सकता है, क्योंकि इन दोनों शाब्दिकों को समान मान निर्दिष्ट करना असंभव है। एस्पवॉल एट अल के रूप में। दिखाया गया है, यह आवश्यक और पर्याप्त शर्त है: 2-सीएनएफ फॉर्मूला तभी संतोषजनक है जब कोई ऐसा वेरिएबल न हो जो इसके निषेध के समान मजबूती से जुड़े घटक से संबंधित हो।<ref name="APT79"/> | ||
यह तुरंत 2-सीएनएफ सूत्रों की संतुष्टि के परीक्षण के लिए रैखिक समय एल्गोरिदम की ओर ले जाता है: बस निहितार्थ ग्राफ पर मजबूत कनेक्टिविटी विश्लेषण करें और जांचें कि प्रत्येक | यह तुरंत 2-सीएनएफ सूत्रों की संतुष्टि के परीक्षण के लिए रैखिक समय एल्गोरिदम की ओर ले जाता है: बस निहितार्थ ग्राफ पर मजबूत कनेक्टिविटी विश्लेषण करें और जांचें कि प्रत्येक वेरिएबल और उसका निषेध अलग-अलग अवयवों से संबंधित है। चूँकि , एस्पवॉल एट अल के रूप में। यह भी दिखाया गया है, यह संतोषजनक असाइनमेंट खोजने के लिए रैखिक समय एल्गोरिदम की ओर भी ले जाता है, जब कोई मौजूद होता है। उनका एल्गोरिदम निम्नलिखित चरण निष्पादित करता है: | ||
*उदाहरण के निहितार्थ ग्राफ का निर्माण करें, और मजबूत कनेक्टिविटी विश्लेषण के लिए किसी भी ज्ञात रैखिक-समय एल्गोरिदम का उपयोग करके इसके दृढ़ता से जुड़े | *उदाहरण के निहितार्थ ग्राफ का निर्माण करें, और मजबूत कनेक्टिविटी विश्लेषण के लिए किसी भी ज्ञात रैखिक-समय एल्गोरिदम का उपयोग करके इसके दृढ़ता से जुड़े अवयवों को ढूंढें। | ||
*जांचें कि क्या किसी दृढ़ता से जुड़े घटक में | *जांचें कि क्या किसी दृढ़ता से जुड़े घटक में वेरिएबल और उसका निषेध दोनों सम्मिलित हैं। यदि हां, तो रिपोर्ट करें कि स्तिथि संतोषजनक नहीं है और रुकें। | ||
*निहितार्थ ग्राफ के मजबूती से जुड़े घटक का निर्माण करें, छोटा ग्राफ जिसमें प्रत्येक मजबूती से जुड़े घटक के लिए शीर्ष और घटक से किनारा हो {{math|''i''}} घटक के लिए {{math|''j''}} जब भी निहितार्थ ग्राफ़ में कोई किनारा होता है {{math|''uv''}} ऐसा है कि {{math|''u''}} घटक से संबंधित है {{math|''i''}} और {{math|''v''}} घटक से संबंधित है {{math|''j''}}. संक्षेपण स्वचालित रूप से निर्देशित चक्रीय ग्राफ है और, निहितार्थ ग्राफ की तरह, जिससे इसे बनाया गया था, यह तिरछा-सममित ग्राफ है|तिरछा-सममित। | *निहितार्थ ग्राफ के मजबूती से जुड़े घटक का निर्माण करें, छोटा ग्राफ जिसमें प्रत्येक मजबूती से जुड़े घटक के लिए शीर्ष और घटक से किनारा हो {{math|''i''}} घटक के लिए {{math|''j''}} जब भी निहितार्थ ग्राफ़ में कोई किनारा होता है {{math|''uv''}} ऐसा है कि {{math|''u''}} घटक से संबंधित है {{math|''i''}} और {{math|''v''}} घटक से संबंधित है {{math|''j''}}. संक्षेपण स्वचालित रूप से निर्देशित चक्रीय ग्राफ है और, निहितार्थ ग्राफ की तरह, जिससे इसे बनाया गया था, यह तिरछा-सममित ग्राफ है|तिरछा-सममित। | ||
*संक्षेपण के शीर्षों को [[टोपोलॉजिकल छँटाई]] करना। व्यवहार में इसे पिछले चरण के साइड इफेक्ट के रूप में कुशलतापूर्वक प्राप्त किया जा सकता है, क्योंकि घटक कोसाराजू के एल्गोरिदम द्वारा टोपोलॉजिकल क्रम में और टारजन के एल्गोरिदम द्वारा रिवर्स टोपोलॉजिकल क्रम में उत्पन्न होते हैं।<ref>{{citation|last=Harrison|first=Paul|title=Robust topological sorting and Tarjan's algorithm in Python|url=http://www.logarithmic.net/pfh/blog/01208083168|access-date=9 February 2011}}</ref> | *संक्षेपण के शीर्षों को [[टोपोलॉजिकल छँटाई]] करना। व्यवहार में इसे पिछले चरण के साइड इफेक्ट के रूप में कुशलतापूर्वक प्राप्त किया जा सकता है, क्योंकि घटक कोसाराजू के एल्गोरिदम द्वारा टोपोलॉजिकल क्रम में और टारजन के एल्गोरिदम द्वारा रिवर्स टोपोलॉजिकल क्रम में उत्पन्न होते हैं।<ref>{{citation|last=Harrison|first=Paul|title=Robust topological sorting and Tarjan's algorithm in Python|url=http://www.logarithmic.net/pfh/blog/01208083168|access-date=9 February 2011}}</ref> | ||
*रिवर्स टोपोलॉजिकल ऑर्डर में प्रत्येक घटक के लिए, यदि इसके | *रिवर्स टोपोलॉजिकल ऑर्डर में प्रत्येक घटक के लिए, यदि इसके वेरिएबल में पहले से ही सत्य असाइनमेंट नहीं हैं, तो घटक में सभी शाब्दिक को सत्य पर सेट करें। इसके कारण पूरक घटक के सभी अक्षर गलत पर सेट हो जाते हैं। | ||
रिवर्स टोपोलॉजिकल ऑर्डरिंग और तिरछी-समरूपता के कारण, जब शाब्दिक को सत्य पर सेट किया जाता है, तो निहितार्थों की श्रृंखला के माध्यम से इससे प्राप्त होने वाले सभी शाब्दिक पहले से ही सत्य पर सेट हो चुके होंगे। सममित रूप से, जब शाब्दिक {{math|''x''}} को गलत पर सेट किया गया है, सभी शाब्दिक अर्थ जो निहितार्थों की श्रृंखला के माध्यम से इसकी ओर ले जाते हैं वे स्वयं पहले से ही गलत पर सेट हो चुके होंगे। इसलिए, इस प्रक्रिया द्वारा निर्मित सत्य असाइनमेंट दिए गए सूत्र को संतुष्ट करता है, जो एस्पवॉल एट अल द्वारा पहचानी गई आवश्यक और पर्याप्त स्थिति की शुद्धता का प्रमाण भी पूरा करता है।<ref name="APT79"/> | रिवर्स टोपोलॉजिकल ऑर्डरिंग और तिरछी-समरूपता के कारण, जब शाब्दिक को सत्य पर सेट किया जाता है, तो निहितार्थों की श्रृंखला के माध्यम से इससे प्राप्त होने वाले सभी शाब्दिक पहले से ही सत्य पर सेट हो चुके होंगे। सममित रूप से, जब शाब्दिक {{math|''x''}} को गलत पर सेट किया गया है, सभी शाब्दिक अर्थ जो निहितार्थों की श्रृंखला के माध्यम से इसकी ओर ले जाते हैं वे स्वयं पहले से ही गलत पर सेट हो चुके होंगे। इसलिए, इस प्रक्रिया द्वारा निर्मित सत्य असाइनमेंट दिए गए सूत्र को संतुष्ट करता है, जो एस्पवॉल एट अल द्वारा पहचानी गई आवश्यक और पर्याप्त स्थिति की शुद्धता का प्रमाण भी पूरा करता है।<ref name="APT79"/> | ||
एस्पवॉल एट अल के रूप में। दिखाएँ, निहितार्थ ग्राफ़ के दृढ़ता से जुड़े | एस्पवॉल एट अल के रूप में। दिखाएँ, निहितार्थ ग्राफ़ के दृढ़ता से जुड़े अवयवों को टोपोलॉजिकल रूप से क्रमबद्ध करने वाली समान प्रक्रिया का उपयोग सही मात्राबद्ध बूलियन सूत्र का मूल्यांकन करने के लिए भी किया जा सकता है जिसमें मात्रा निर्धारित किया जा रहा सूत्र 2-सीएनएफ सूत्र है।<ref name="APT79"/> | ||
Line 114: | Line 119: | ||
===ज्यामितीय वस्तुओं का संघर्ष-मुक्त स्थान === | ===ज्यामितीय वस्तुओं का संघर्ष-मुक्त स्थान === | ||
[[स्वचालित लेबल प्लेसमेंट]] समस्या के लिए | [[स्वचालित लेबल प्लेसमेंट]] समस्या के लिए अनेक सटीक और अनुमानित एल्गोरिदम 2-संतुष्टि पर आधारित हैं। यह समस्या किसी आरेख या मानचित्र की विशेषताओं पर पाठ्य लेबल लगाने से संबंधित है। सामान्यतः , प्रत्येक लेबल के लिए संभावित स्थानों का सेट अत्यधिक प्रतिबंधित होता है, न केवल मानचित्र द्वारा (प्रत्येक लेबल को उस सुविधा के पास होना चाहिए जिसे वह लेबल करता है, और अन्य सुविधाओं को अस्पष्ट नहीं करना चाहिए), किन्तु एक-दूसरे द्वारा: प्रत्येक दो लेबल को एक-दूसरे को ओवरलैप करने से बचना चाहिए, अन्यथा वे अस्पष्ट हो जाएंगे। सामान्य तौर पर, इन बाधाओं का पालन करने वाला लेबल प्लेसमेंट ढूंढना [[ एनपी कठिन |एनपी कठिन]] समस्या है। चूँकि , यदि प्रत्येक फीवेरिएबल में उसके लेबल के लिए केवल दो संभावित स्थान हैं (जैसे, फीवेरिएबल के बाईं और दाईं ओर विस्तार) तो लेबल प्लेसमेंट को बहुपद समय में हल किया जा सकता है। इस मामले में, कोई 2-संतोषजनक उदाहरण बना सकता है जिसमें प्रत्येक लेबल के लिए वेरिएबल होता है और जिसमें लेबल की प्रत्येक जोड़ी के लिए खंड होता है जो ओवरलैप हो सकता है, जिससे उन्हें ओवरलैपिंग स्थिति आवंटित करने से रोका जा सकता है। यदि लेबल सभी सर्वांगसम आयत हैं, तो संबंधित 2-संतुष्टि उदाहरण को केवल रैखिक रूप से अनेक बाधाओं के रूप में दिखाया जा सकता है, जिससे लेबलिंग खोजने के लिए निकट-रेखीय समय एल्गोरिदम हो सकता है।<ref name="fw91">{{citation|first1=M.|last1=Formann|first2=F.|last2=Wagner|contribution=A packing problem with applications to lettering of maps|title=Proc. 7th ACM Symposium on Computational Geometry|year=1991|pages=281–288|doi=10.1145/109648.109680|isbn=978-0-89791-426-0|title-link=Symposium on Computational Geometry|s2cid=15740667}}.</ref> {{harvtxt|पून|झू |चिन|1998}} मानचित्र लेबलिंग समस्या का वर्णन करें जिसमें प्रत्येक लेबल आयत है जिसे लेबल किए गए रेखा खंड के संबंध में तीन स्थितियों में से में रखा जा सकता है: इसमें खंड इसके किनारों में से के रूप में हो सकता है, या यह खंड पर केंद्रित हो सकता है। वे दो बाइनरी वेरिएबल का उपयोग करके इन तीन स्थितियों का प्रतिनिधित्व इस तरह से करते हैं कि, फिर से, वैध लेबलिंग के अस्तित्व का परीक्षण करना 2-संतुष्टि समस्या बन जाता है।<ref>{{citation|first1=Chung Keung|last1=Poon|first2=Binhai|last2=Zhu|first3=Francis|last3=Chin|author3-link=Y. L. Chin|title=A polynomial time solution for labeling a rectilinear map|journal=[[Information Processing Letters]]|volume=65|issue=4|year=1998|pages=201–207|doi=10.1016/S0020-0190(98)00002-7}}.</ref> | ||
{{harvtxt| | {{harvtxt|फॉर्मैन |वैगनर|1991}} किसी दिए गए बिंदुओं के सेट के लिए सबसे बड़े संभावित आकार के वर्ग लेबल खोजने की समस्या के लिए सन्निकटन एल्गोरिदम के भाग के रूप में 2-संतुष्टि का उपयोग करें, इस बाधा के साथ कि प्रत्येक लेबल का कोना उस बिंदु पर हो जिस बिंदु पर वह लेबल करता है। किसी दिए गए आकार के साथ लेबलिंग खोजने के लिए, वे उन वर्गों को हटा देते हैं, जिन्हें यदि दोगुना किया जाए, तो वे दूसरे बिंदु को ओवरलैप कर देंगे, और वे उन बिंदुओं को हटा देते हैं, जिन्हें इस तरह से लेबल किया जा सकता है कि संभवतः किसी अन्य बिंदु के लेबल के साथ ओवरलैप नहीं किया जा सकता है। वे दिखाते हैं कि इन उन्मूलन नियमों के कारण शेष बिंदुओं पर प्रति बिंदु केवल दो संभावित लेबल प्लेसमेंट होते हैं, जिससे 2-संतुष्टि उदाहरण के समाधान के रूप में वैध लेबल प्लेसमेंट (यदि कोई मौजूद है) पाया जा सकता है। सबसे बड़े लेबल आकार की खोज करके जो हल करने योग्य 2-संतोषजनक उदाहरण की ओर ले जाता है, उन्हें वैध लेबल प्लेसमेंट मिलता है जिसके लेबल इष्टतम समाधान से कम से कम आधे बड़े होते हैं। अर्थात्, उनके एल्गोरिथ्म का [[सन्निकटन अनुपात]] अधिकतम दो है।<ref name="fw91"/><ref>{{citation|first1=Frank|last1=Wagner|first2=Alexander|last2=Wolff|title=A practical map labeling algorithm|journal=[[Computational Geometry (journal)|Computational Geometry: Theory and Applications]]|volume=7|issue=5–6|year=1997|pages=387–404|doi=10.1016/S0925-7721(96)00007-7}}.</ref> इसी तरह, यदि प्रत्येक लेबल आयताकार है और उसे इस तरह से रखा जाना चाहिए कि जिस बिंदु पर वह लेबल करता है वह उसके निचले किनारे के साथ कहीं है, तो सबसे बड़े लेबल आकार को खोजने के लिए 2-संतुष्टि का उपयोग करें जिसके लिए समाधान है जिसमें प्रत्येक लेबल के निचले कोने पर बिंदु होता है जिससे अधिकतम दो का अनुमान अनुपात होता है।<ref>{{citation|first1=Srinivas|last1=Doddi|first2=Madhav V.|last2=Marathe|first3=Andy|last3=Mirzaian|first4=Bernard M. E.|last4=Moret|first5=Binhai|last5=Zhu|contribution=Map labeling and its generalizations|title=Proc. 8th ACM-SIAM Symp. Discrete Algorithms (SODA)|year=1997|pages=148–157|url=http://portal.acm.org/citation.cfm?id=314250|isbn=9780898713909|series=Soda '97}}.</ref> | ||
अन्य ज्यामितीय प्लेसमेंट समस्याओं के लिए 2-संतुष्टि के समान अनुप्रयोग किए गए हैं। [[ग्राफ ड्राइंग]] में, यदि शीर्ष स्थान तय किए गए हैं और प्रत्येक किनारे को दो संभावित स्थानों में से के साथ गोलाकार चाप के रूप में खींचा जाना चाहिए (उदाहरण के लिए आर्क आरेख के रूप में), तो क्रॉसिंग से बचने के लिए प्रत्येक किनारे के लिए कौन सा चाप का उपयोग करना है यह चुनने की समस्या प्रत्येक किनारे के लिए | |||
[[वीएलएसआई]] एकीकृत | अन्य ज्यामितीय प्लेसमेंट समस्याओं के लिए 2-संतुष्टि के समान अनुप्रयोग किए गए हैं। [[ग्राफ ड्राइंग]] में, यदि शीर्ष स्थान तय किए गए हैं और प्रत्येक किनारे को दो संभावित स्थानों में से के साथ गोलाकार चाप के रूप में खींचा जाना चाहिए (उदाहरण के लिए आर्क आरेख के रूप में), तो क्रॉसिंग से बचने के लिए प्रत्येक किनारे के लिए कौन सा चाप का उपयोग करना है यह चुनने की समस्या प्रत्येक किनारे के लिए वेरिएबल के साथ 2-संतुष्टि की समस्या है और प्लेसमेंट की प्रत्येक जोड़ी के लिए बाधा है जो क्रॉसिंग की ओर ले जाएगी। चूँकि , इस मामले में समाधान को गति देना संभव है, एल्गोरिदम की तुलना में जो ग्राफ़ के [[अंतर्निहित ग्राफ]]़ को खोजकर, निहितार्थ ग्राफ़ का स्पष्ट प्रतिनिधित्व बनाता है और फिर खोजता है।<ref>{{citation|first1=Alon|last1=Efrat|first2=Cesim|last2=Erten|first3=Stephen G.|last3=Kobourov|title=Fixed-location circular arc drawing of planar graphs|journal=[[Journal of Graph Algorithms and Applications]]|volume=11|issue=1|pages=145–164|year=2007|url=http://jgaa.info/accepted/2007/EfratErtenKobourov2007.11.1.pdf|doi=10.7155/jgaa.00140}}.</ref> [[वीएलएसआई]] एकीकृत परिपथ डिजाइन में, यदि मॉड्यूल का संग्रह तारों से जुड़ा होना चाहिए जो प्रत्येक अधिकतम बार झुक सकता है, तो तारों के लिए फिर से दो संभावित मार्ग हैं, और इन दो मार्गों में से कौन सा उपयोग करना है, यह चुनने की समस्या, इस तरह से कि सभी तारों को परिपथ की परत में रूट किया जा सकता है, को 2-संतुष्टि उदाहरण के रूप में हल किया जा सकता है।<ref>{{citation|first1=Raghunath|last1=Raghavan|first2= James|last2=Cohoon|first3=Sartaj|last3=Sahni|author3-link=Sartaj Sahni|title=Single bend wiring|journal=Journal of Algorithms|volume=7|issue=2|year=1986|pages=232–237|doi=10.1016/0196-6774(86)90006-4}}.</ref> | ||
{{harvtxt|बोरोस|हैमर |मिनौक्स|रडर |1999}} अन्य वीएलएसआई डिज़ाइन समस्या पर विचार करें: परिपथ डिज़ाइन में प्रत्येक मॉड्यूल को मिरर-रिवर्स करना है या नहीं, इसका प्रश्न। यह मिरर रिवर्सल मॉड्यूल के संचालन को अपरिवर्तित छोड़ देता है, किन्तु यह उन बिंदुओं के क्रम को बदल देता है जिन पर मॉड्यूल के इनपुट और आउटपुट सिग्नल इससे जुड़ते हैं, संभवतः यह बदल जाता है कि मॉड्यूल बाकी डिज़ाइन में कितनी अच्छी तरह फिट बैठता है। बोरोस एट अल. समस्या के सरलीकृत संस्करण पर विचार करें जिसमें मॉड्यूल पहले से ही ही रैखिक चैनल के साथ रखे गए हैं, जिसमें मॉड्यूल के बीच तारों को रूट किया जाना चाहिए, और चैनल के घनत्व पर निश्चित सीमा होती है (सिग्नलों की अधिकतम संख्या जो चैनल के किसी भी क्रॉस-सेक्शन से गुज़रनी चाहिए)। उनका मानना है कि समस्या के इस संस्करण को 2-संतुष्टि उदाहरण के रूप में हल किया जा सकता है, जिसमें बाधाएं मॉड्यूल के जोड़े के उन्मुखीकरण से संबंधित हैं जो सीधे दूसरे से चैनल के पार हैं। परिणामस्वरूप, बाइनरी खोज करके इष्टतम घनत्व की गणना भी कुशलतापूर्वक की जा सकती है, जिसमें प्रत्येक चरण में 2-संतुष्टि उदाहरण का समाधान सम्मिलित होता है।<ref>{{citation|first1=Endre|last1=Boros|first2=Peter Ladislaw|last2=Hammer|author2-link=Peter Ladislaw Hammer|first3=Michel|last3=Minoux|first4=David J., Jr.|last4=Rader|title=Optimal cell flipping to minimize channel density in VLSI design and pseudo-Boolean optimization|journal=[[Discrete Applied Mathematics]]|volume=90|issue=1–3|year=1999|pages=69–88|doi=10.1016/S0166-218X(98)00114-0}}.</ref> | |||
===[[डेटा क्लस्टरिंग]]=== | ===[[डेटा क्लस्टरिंग]]=== | ||
एक [[मीट्रिक स्थान]] में डेटा को दो समूहों में क्लस्टर करने का | एक [[मीट्रिक स्थान]] में डेटा को दो समूहों में क्लस्टर करने का विधि क्लस्टर को इस तरह से चुनना है जिससे क्लस्टर के [[व्यास]] के योग को कम किया जा सके, जहां किसी एकल क्लस्टर का व्यास उसके किन्हीं दो बिंदुओं के बीच की सबसे बड़ी दूरी है। यह अधिकतम क्लस्टर आकार को कम करने के लिए बेहतर है, जिससे विभिन्न समूहों को बहुत समान अंक आवंटित किए जा सकते हैं। यदि दो समूहों के लक्ष्य व्यास ज्ञात हैं, तो 2-संतुष्टि उदाहरण को हल करके उन लक्ष्यों को प्राप्त करने वाली क्लस्टरिंग पाई जा सकती है। उदाहरण में प्रति बिंदु वेरिएबल है, जो दर्शाता है कि वह बिंदु पहले क्लस्टर से संबंधित है या दूसरे क्लस्टर से। जब भी कोई दो बिंदु दूसरे से इतने दूर होते हैं कि दोनों ही क्लस्टर से संबंधित नहीं होते हैं, तो उदाहरण में खंड जोड़ा जाता है जो इस असाइनमेंट को रोकता है। | ||
जब व्यक्तिगत क्लस्टर व्यास अज्ञात हों तो उसी विधि का उपयोग सबरूटीन के रूप में भी किया जा सकता है। यह जांचने के लिए कि क्या व्यास का दिया गया योग अलग-अलग क्लस्टर व्यास को जाने बिना प्राप्त किया जा सकता है, कोई लक्ष्य व्यास के सभी अधिकतम जोड़े का प्रयास कर सकता है जो अधिकतम दिए गए योग को जोड़ता है, व्यास की प्रत्येक जोड़ी को 2-संतुष्टिशीलता उदाहरण के रूप में दर्शाता है और यह निर्धारित करने के लिए 2-संतोषजनक एल्गोरिदम का उपयोग करता है कि क्या उस जोड़ी को क्लस्टरिंग द्वारा महसूस किया जा सकता है। व्यासों का इष्टतम योग ज्ञात करने के लिए कोई बाइनरी खोज कर सकता है जिसमें प्रत्येक चरण इस प्रकार का व्यवहार्यता परीक्षण होता है। यही दृष्टिकोण क्लस्टरिंग को खोजने के लिए भी | जब व्यक्तिगत क्लस्टर व्यास अज्ञात हों तो उसी विधि का उपयोग सबरूटीन के रूप में भी किया जा सकता है। यह जांचने के लिए कि क्या व्यास का दिया गया योग अलग-अलग क्लस्टर व्यास को जाने बिना प्राप्त किया जा सकता है, कोई लक्ष्य व्यास के सभी अधिकतम जोड़े का प्रयास कर सकता है जो अधिकतम दिए गए योग को जोड़ता है, व्यास की प्रत्येक जोड़ी को 2-संतुष्टिशीलता उदाहरण के रूप में दर्शाता है और यह निर्धारित करने के लिए 2-संतोषजनक एल्गोरिदम का उपयोग करता है कि क्या उस जोड़ी को क्लस्टरिंग द्वारा महसूस किया जा सकता है। व्यासों का इष्टतम योग ज्ञात करने के लिए कोई बाइनरी खोज कर सकता है जिसमें प्रत्येक चरण इस प्रकार का व्यवहार्यता परीक्षण होता है। यही दृष्टिकोण क्लस्टरिंग को खोजने के लिए भी कार्य करता है जो क्लस्टर व्यास के योग के अलावा अन्य संयोजनों को अनुकूलित करता है, और जो क्लस्टर के आकार को मापने के लिए मनमाने ढंग से असमानता संख्याओं (मीट्रिक स्थान में दूरी के अतिरिक्त ) का उपयोग करता है।<ref>{{citation|first1=P.|last1=Hansen|first2=B.|last2=Jaumard|author2-link= Brigitte Jaumard |title=Minimum sum of diameters clustering|journal=Journal of Classification|volume=4|issue=2|year=1987|pages=215–226|doi=10.1007/BF01896987|s2cid=120583429}}.</ref> इस एल्गोरिथम के लिए समय सीमा 2-संतोषजनक उदाहरणों के अनुक्रम को हल करने के समय पर हावी है जो एक-दूसरे से निकटता से संबंधित हैं, और {{harvtxt|रामनाथ|2004}} दिखाता है कि इन संबंधित उदाहरणों को एक-दूसरे से स्वतंत्र रूप से हल करने की तुलना में अधिक तेज़ी से कैसे हल किया जाए, जिससे कुल समय सीमा तय हो सके {{math|''O''(''n''<sup>3</sup>)}}व्यास के योग की क्लस्टरिंग समस्या के लिए।<ref>{{citation|first1=Sarnath|last1=Ramnath|title=Dynamic digraph connectivity hastens minimum sum-of-diameters clustering|journal=[[SIAM Journal on Discrete Mathematics]]|volume=18|issue=2|pages=272–286|year=2004|doi=10.1137/S0895480102396099}}.</ref> | ||
===शेड्यूलिंग=== | ===शेड्यूलिंग=== | ||
{{harvtxt| | {{harvtxt|इवेन |इटाई|शमीर|1976}} कक्षा समय-निर्धारण के मॉडल पर विचार करें जिसमें छात्रों के प्रत्येक समूह को पढ़ाने के लिए n शिक्षकों का समूह निर्धारित किया जाना चाहिए। उस शिक्षक के प्रति सप्ताह घंटों की संख्या <math>i</math> समूह के साथ बिताता है <math>j</math> प्रविष्टि द्वारा वर्णित है <math>R_{ij}</math> मैट्रिक्स का <math>R</math> समस्या के इनपुट के रूप में दिया गया है, और प्रत्येक शिक्षक के पास घंटों का सेट भी है जिसके दौरान वह शेड्यूल के लिए उपलब्ध रहता है। जैसा कि वे दिखाते हैं, समस्या एनपी-पूर्ण है, भले ही प्रत्येक शिक्षक के पास अधिकतम तीन उपलब्ध घंटे हों, किन्तु इसे 2-संतुष्टि के उदाहरण के रूप में हल किया जा सकता है जब प्रत्येक शिक्षक के पास केवल दो उपलब्ध घंटे हों। (केवल उपलब्ध घंटे वाले शिक्षकों को समस्या से आसानी से छुटकारा दिलाया जा सकता है।) इस समस्या में, प्रत्येक वेरिएबल <math>v_{ij}</math> उस शिक्षक के घंटे से मेल खाता है <math>i</math> समूह के साथ बिताना चाहिए <math>j</math>, वेरिएबल के लिए असाइनमेंट निर्दिष्ट करता है कि क्या वह घंटा शिक्षक के उपलब्ध घंटों में से पहला या दूसरा है, और 2-संतुष्टि खंड है जो दो प्रकार के किसी भी टकराव को रोकता है: शिक्षक को ही समय में एक-दूसरे को सौंपे गए दो समूह, या ही समय में दो शिक्षकों को सौंपा गया समूह।<ref name="EIS76"/> | ||
{{harvtxt| | {{harvtxt|मियाशिरो |मत्सुई |2005}} खेल शेड्यूलिंग की समस्या के लिए 2-संतुष्टि प्रयुक्त करें, जिसमें [[राउंड-रॉबिन टूर्नामेंट]] की जोड़ियों को पहले ही चुना जा चुका है और खेलों को टीमों के स्टेडियमों को सौंपा जाना चाहिए। इस समस्या में, जहां तक संभव हो घर और बाहर के खेलों को वैकल्पिक करना वांछनीय है, ब्रेक से बचना चाहिए जिसमें टीम पंक्ति में दो घरेलू खेल खेलती है या पंक्ति में दो दूर खेल खेलती है। अधिक से अधिक दो टीमें घर और बाहर के खेलों के बीच बारी-बारी से ब्रेक से पूरी तरह बच सकती हैं; किसी अन्य टीम का होम-अवे शेड्यूल इन दोनों के समान नहीं हो सकता, क्योंकि तब वह उस टीम के साथ खेलने में असमर्थ होगी जिसके साथ उसका शेड्यूल समान था। इसलिए, इष्टतम शेड्यूल में दो ब्रेकलेस टीमें होती हैं और हर दूसरी टीम के लिए ब्रेक होता है। बार जब ब्रेकलेस टीमों में से को चुना जाता है, तो कोई 2-संतुष्टि की समस्या खड़ी कर सकता है, जिसमें प्रत्येक वेरिएबल ही गेम में ही टीम के लिए होम-अवे असाइनमेंट का प्रतिनिधित्व करता है, और बाधाएं उन गुणों को प्रयुक्त करती हैं कि किन्हीं दो टीमों के पास अपने गेम के लिए सुसंगत असाइनमेंट होता है, प्रत्येक टीम के पास ब्रेकलेस टीम के साथ खेल से पहले अधिकतम ब्रेक और गेम के पश्चात अधिकतम ब्रेक होता है, और किसी भी टीम के पास दो ब्रेक नहीं होते हैं। इसलिए, यह परीक्षण करना कि क्या कोई शेड्यूल इष्टतम संख्या में ब्रेक के साथ समाधान स्वीकार करता है, ब्रेकलेस टीम की प्रत्येक पसंद के लिए 2-संतुष्टि समस्याओं की रैखिक संख्या को हल करके किया जा सकता है। समान तकनीक ऐसे शेड्यूल खोजने की भी अनुमति देती है जिसमें प्रत्येक टीम के पास ही ब्रेक होता है, और ब्रेक की संख्या को कम करने के अतिरिक्त अधिकतम करने की अनुमति देता है (टीमों द्वारा यात्रा की गई कुल माइलेज को कम करने के लिए)।<ref>{{citation|first1=Ryuhei|last1=Miyashiro|first2=Tomomi|last2=Matsui|title=A polynomial-time algorithm to find an equitable home–away assignment|journal=Operations Research Letters|volume=33|issue=3|year=2005|pages=235–241|doi=10.1016/j.orl.2004.06.004|citeseerx=10.1.1.64.240}}.</ref> | ||
===असतत टोमोग्राफी=== | ===असतत टोमोग्राफी=== | ||
[[File:Nonogram_wiki.svg|thumb|नॉनोग्राम पहेली का उदाहरण.]][[टोमोग्राफी]] उनके क्रॉस-सेक्शन से आकृतियों को पुनर्प्राप्त करने की प्रक्रिया है। [[असतत टोमोग्राफी]] में, समस्या का सरलीकृत संस्करण जिसका अक्सर अध्ययन किया गया है, पुनर्प्राप्त किया जाने वाला आकार [[पॉलीओमिनो]] (द्वि-आयामी वर्ग जाली में वर्गों का उपसमूह) है, और क्रॉस-सेक्शन जाली की व्यक्तिगत पंक्तियों और स्तंभों में वर्गों के सेट के बारे में समग्र जानकारी प्रदान करते हैं। उदाहरण के लिए, लोकप्रिय [[पहेलियाँ खेलना]] पहेलियों में, जिन्हें संख्याओं या ग्रिडलर द्वारा पेंट के रूप में भी जाना जाता है, निर्धारित किए जाने वाले वर्गों का सेट बाइनरी छवि में डार्क [[ पिक्सेल |पिक्सेल]] का प्रतिनिधित्व करता है, और पहेली सॉल्वर को दिया गया इनपुट उसे बताता है कि छवि की प्रत्येक पंक्ति या कॉलम में डार्क पिक्सल के कितने लगातार ब्लॉक | [[File:Nonogram_wiki.svg|thumb|नॉनोग्राम पहेली का उदाहरण.]][[टोमोग्राफी]] उनके क्रॉस-सेक्शन से आकृतियों को पुनर्प्राप्त करने की प्रक्रिया है। [[असतत टोमोग्राफी]] में, समस्या का सरलीकृत संस्करण जिसका अक्सर अध्ययन किया गया है, पुनर्प्राप्त किया जाने वाला आकार [[पॉलीओमिनो]] (द्वि-आयामी वर्ग जाली में वर्गों का उपसमूह) है, और क्रॉस-सेक्शन जाली की व्यक्तिगत पंक्तियों और स्तंभों में वर्गों के सेट के बारे में समग्र जानकारी प्रदान करते हैं। उदाहरण के लिए, लोकप्रिय [[पहेलियाँ खेलना]] पहेलियों में, जिन्हें संख्याओं या ग्रिडलर द्वारा पेंट के रूप में भी जाना जाता है, निर्धारित किए जाने वाले वर्गों का सेट बाइनरी छवि में डार्क [[ पिक्सेल |पिक्सेल]] का प्रतिनिधित्व करता है, और पहेली सॉल्वर को दिया गया इनपुट उसे बताता है कि छवि की प्रत्येक पंक्ति या कॉलम में डार्क पिक्सल के कितने लगातार ब्लॉक सम्मिलित करने हैं, और उनमें से प्रत्येक ब्लॉक कितना लंबा होना चाहिए। डिजिटल टोमोग्राफी के अन्य रूपों में, प्रत्येक पंक्ति या स्तंभ के बारे में और भी कम जानकारी दी जाती है: वर्गों के ब्लॉक की संख्या और लंबाई के अतिरिक्त केवल वर्गों की कुल संख्या। समस्या का समतुल्य संस्करण यह है कि हमें मैट्रिक्स की प्रत्येक पंक्ति और प्रत्येक कॉलम में केवल मानों के योग को देखते हुए दिए गए [[0-1 मैट्रिक्स]] को पुनर्प्राप्त करना होगा। | ||
यद्यपि पंक्ति और स्तंभ के योग वाले मैट्रिक्स को खोजने के लिए बहुपद समय एल्गोरिदम मौजूद हैं,<ref>{{citation|first=R. A.|last=Brualdi|author-link=Richard A. Brualdi|title=Matrices of zeros and ones with fixed row and column sum vectors|journal=Linear Algebra Appl.|volume=33|year=1980|pages=159–231|doi=10.1016/0024-3795(80)90105-6|doi-access=free}}.</ref> समाधान अद्वितीय से बहुत दूर हो सकता है: 2 × 2 पहचान मैट्रिक्स के रूप में किसी भी सबमैट्रिक्स को समाधान की शुद्धता को प्रभावित किए बिना पूरक किया जा सकता है। इसलिए, शोधकर्ताओं ने पुनर्निर्माण किए जाने वाले आकार पर बाधाओं की खोज की है जिसका उपयोग समाधानों के स्थान को प्रतिबंधित करने के लिए किया जा सकता है। उदाहरण के लिए, कोई यह मान सकता है कि आकृति जुड़ी हुई है; | यद्यपि पंक्ति और स्तंभ के योग वाले मैट्रिक्स को खोजने के लिए बहुपद समय एल्गोरिदम मौजूद हैं,<ref>{{citation|first=R. A.|last=Brualdi|author-link=Richard A. Brualdi|title=Matrices of zeros and ones with fixed row and column sum vectors|journal=Linear Algebra Appl.|volume=33|year=1980|pages=159–231|doi=10.1016/0024-3795(80)90105-6|doi-access=free}}.</ref> समाधान अद्वितीय से बहुत दूर हो सकता है: 2 × 2 पहचान मैट्रिक्स के रूप में किसी भी सबमैट्रिक्स को समाधान की शुद्धता को प्रभावित किए बिना पूरक किया जा सकता है। इसलिए, शोधकर्ताओं ने पुनर्निर्माण किए जाने वाले आकार पर बाधाओं की खोज की है जिसका उपयोग समाधानों के स्थान को प्रतिबंधित करने के लिए किया जा सकता है। उदाहरण के लिए, कोई यह मान सकता है कि आकृति जुड़ी हुई है; चूँकि , यह परीक्षण करना कि क्या कोई कनेक्टेड समाधान मौजूद है, एनपी-पूर्ण है।<ref>{{citation|first=G. J.|last=Woeginger|author-link= Gerhard J. Woeginger |title=The reconstruction of polyominoes from their orthogonal projections|series=Technical Report SFB-65|publisher=TU Graz|location=Graz, Austria|year=1996}}.</ref> और अधिक सीमित संस्करण जिसे हल करना आसान है वह यह है कि आकार [[ऑर्थोगोनल उत्तलता]] है: प्रत्येक पंक्ति और स्तंभ में वर्गों का एकल सन्निहित ब्लॉक होता है। | ||
पिछले | पिछले अनेक समाधानों में सुधार, {{harvtxt|क्रोबक|Dürr|1999}} ने दिखाया कि 2-एसएटी का उपयोग करके कनेक्टेड ऑर्थोगोनली उत्तल आकृतियों को कुशलतापूर्वक कैसे पुनर्निर्माण किया जाए।<ref>{{citation|first1=Marek|last1=Chrobak|first2=Christoph|last2=Dürr|title=Reconstructing hv-convex polyominoes from orthogonal projections|journal=[[Information Processing Letters]]|volume=69|issue=6|year=1999|pages=283–289|doi=10.1016/S0020-0190(99)00025-3|arxiv=cs/9906021|bibcode=1999cs........6021D|s2cid=6799509}}.</ref> उनके समाधान का विचार पुनर्निर्माण की जाने वाली आकृति की सबसे बाईं और दाईं ओर की कोशिकाओं वाली पंक्तियों के सूचकांक का अनुमान लगाना है, और फिर 2-संतुष्टि समस्या स्थापित करना है जो परीक्षण करता है कि क्या इन अनुमानों और दी गई पंक्ति और स्तंभ योगों के अनुरूप कोई आकृति मौजूद है। वे प्रत्येक वर्ग के लिए चार 2-संतुष्टि वेरिएबल का उपयोग करते हैं जो दिए गए आकार का हिस्सा हो सकते हैं, यह इंगित करने के लिए कि क्या यह आकृति के चार संभावित कोने क्षेत्रों में से प्रत्येक से संबंधित है, और वे उन बाधाओं का उपयोग करते हैं जो इन क्षेत्रों को असंयुक्त होने के लिए मजबूर करते हैं, वांछित आकार प्राप्त करने के लिए, सन्निहित पंक्तियों और स्तंभों के साथ समग्र आकार बनाने के लिए, और वांछित पंक्ति और स्तंभ योग प्राप्त करने के लिए। उनके एल्गोरिदम में समय लगता है {{math|O(''m''<sup>3</sup>''n'')}} जहाँ {{math|''m''}} इनपुट आकार के दो आयामों में से छोटा है और {{math|''n''}} दो आयामों में से बड़ा है। उसी पद्धति को पश्चात में ऑर्थोगोनल रूप से उत्तल आकृतियों तक विस्तारित किया गया, जिन्हें ऑर्थोगोनल कनेक्टिविटी की आवश्यकता के अतिरिक्त केवल तिरछे रूप से जोड़ा जा सकता है।<ref>{{citation|first1=Attila|last1=Kuba|first2=Emese|last2=Balogh|title=Reconstruction of convex 2D discrete sets in polynomial time|journal=[[Theoretical Computer Science (journal)|Theoretical Computer Science]]|volume=283|issue=1|year=2002|pages=223–242|doi=10.1016/S0304-3975(01)00080-9}}; {{citation|first1=Sara|last1=Brunetti|first2=Alain|last2=Daurat|title=An algorithm reconstructing convex lattice sets|journal=[[Theoretical Computer Science (journal)|Theoretical Computer Science]]|volume=304|issue=1–3|pages=35–57|year=2003|doi=10.1016/S0304-3975(03)00050-1|s2cid=2803842 |url=http://hal.archives-ouvertes.fr/docs/00/06/61/77/PDF/tomoqconv_els.pdf}}.</ref> | ||
पूर्ण नॉनोग्राम पहेलियों के लिए सॉल्वर का भाग, {{harvs|last1= | पूर्ण नॉनोग्राम पहेलियों के लिए सॉल्वर का भाग, {{harvs|last1=बटेनबर्ग|last2=कोस्टर्स|year=2008|year2=2009|टीएक्सटी}} अनेक अन्य अनुमानों से प्राप्त जानकारी को संयोजित करने के लिए 2-संतोषजनकता का उपयोग किया गया। पहेली के आंशिक समाधान को देखते हुए, वे यह निर्धारित करने के लिए प्रत्येक पंक्ति या स्तंभ के भीतर [[गतिशील प्रोग्रामिंग]] का उपयोग करते हैं कि क्या उस पंक्ति या स्तंभ की बाधाएं उसके किसी भी वर्ग को सफेद या काला होने के लिए मजबूर करती हैं, और क्या ही पंक्ति या स्तंभ में किसी भी दो वर्गों को निहितार्थ संबंध द्वारा जोड़ा जा सकता है। वे प्रत्येक पंक्ति और स्तंभ में ब्लॉक लंबाई के अनुक्रम को उसके योग से प्रतिस्थापित करके नॉनोग्राम को डिजिटल टोमोग्राफी समस्या में बदल देते हैं, और यह निर्धारित करने के लिए [[अधिकतम प्रवाह]] फॉर्मूलेशन का उपयोग करते हैं कि क्या सभी पंक्तियों और स्तंभों को संयोजित करने वाली इस डिजिटल टोमोग्राफी समस्या में कोई वर्ग है जिसकी स्थिति निर्धारित की जा सकती है या वर्गों के जोड़े हैं जिन्हें निहितार्थ संबंध द्वारा जोड़ा जा सकता है। यदि इन दोनों अनुमानों में से कोई वर्ग का मान निर्धारित करता है, तो इसे आंशिक समाधान में सम्मिलित किया जाता है और वही गणना दोहराई जाती है। चूँकि , यदि दोनों अनुमान किसी भी वर्ग को निर्धारित करने में विफल रहते हैं, तो उन दोनों द्वारा पाए गए निहितार्थों को 2-संतुष्टिशीलता समस्या में जोड़ दिया जाता है और उन वर्गों को खोजने के लिए 2-संतुष्टिकारक सॉल्वर का उपयोग किया जाता है जिनका मान समस्या द्वारा तय किया जाता है, जिसके पश्चात प्रक्रिया फिर से दोहराई जाती है। यह प्रक्रिया समाधान ढूंढने में सफल हो भी सकती है और नहीं भी, किन्तु इसके बहुपद समय में चलने की गारंटी है। बटेनबर्ग और कोस्टर्स की रिपोर्ट है कि, हालांकि अधिकांश अखबार पहेलियों को इसकी पूरी शक्ति की आवश्यकता नहीं है, यह प्रक्रिया और अधिक शक्तिशाली किन्तु धीमी प्रक्रिया है जो इस 2-संतुष्टि दृष्टिकोण को सीमित बैकट्रैकिंग के साथ जोड़ती है। {{harvtxt|इवेन|इटाई|शमीर|1976}}<ref name="EIS76"/> अधिक कठिन बेतरतीब ढंग से उत्पन्न नॉनोग्राम पर प्रयुक्त होने पर 2-संतुष्टि के बिना गतिशील प्रोग्रामिंग और प्रवाह अनुमान की तुलना में अधिक अधिक प्रभावी होते हैं।<ref>{{citation|first1=K. Joost|last1=Batenburg|first2=Walter A.|last2=Kosters|contribution=A reasoning framework for solving Nonograms|title=Combinatorial Image Analysis, 12th International Workshop, IWCIA 2008, Buffalo, NY, USA, April 7–9, 2008, Proceedings|series=Lecture Notes in Computer Science|volume=4958|year=2008|publisher=Springer-Verlag|pages=372–383|doi=10.1007/978-3-540-78275-9_33|isbn=978-3-540-78274-2}}; {{citation|first1=K. Joost|last1=Batenburg|first2=Walter A.|last2=Kosters|title=Solving Nonograms by combining relaxations|journal=Pattern Recognition|volume=42|issue=8|year=2009|pages=1672–1683|doi=10.1016/j.patcog.2008.12.003|bibcode=2009PatRe..42.1672B |citeseerx=10.1.1.177.76}}.</ref> | ||
===नाम बदलने योग्य हॉर्न संतुष्टि=== | ===नाम बदलने योग्य हॉर्न संतुष्टि=== | ||
2-संतुष्टि के | 2-संतुष्टि के पश्चात, संतुष्टि समस्याओं का दूसरा प्रमुख उपवर्ग जिसे बहुपद समय में हल किया जा सकता है, हॉर्न-संतुष्टि है। संतुष्टि समस्याओं के इस वर्ग में, इनपुट फिर से संयोजक सामान्य रूप में सूत्र है। इसमें प्रत्येक खंड में मनमाने ढंग से अनेक अक्षर हो सकते हैं किन्तु अधिकतम सकारात्मक अक्षर हो सकता है। {{harvtxt|लेविस |1978}} इस वर्ग का सामान्यीकरण पाया गया, नाम बदलने योग्य हॉर्न संतुष्टि, जिसे अभी भी सहायक 2-संतोषजनक उदाहरण के माध्यम से बहुपद समय में हल किया जा सकता है। सूत्र को हॉर्न नाम दिया जा सकता है जब कुछ वेरिएबलों को उनके निषेधों द्वारा प्रतिस्थापित करके इसे हॉर्न रूप में रखना संभव हो। ऐसा करने के लिए, लुईस नाम बदलने योग्य हॉर्न उदाहरण के प्रत्येक वेरिएबल के लिए वेरिएबल के साथ 2-संतोषजनक उदाहरण स्थापित करता है, जहां 2-संतोषजनक वेरिएबल इंगित करते हैं कि संबंधित नाम बदलने योग्य हॉर्न वेरिएबल को नकारना है या नहीं। | ||
हॉर्न उदाहरण तैयार करने के लिए, नाम बदलने योग्य हॉर्न उदाहरण के ही खंड में दिखाई देने वाले कोई भी दो | हॉर्न उदाहरण तैयार करने के लिए, नाम बदलने योग्य हॉर्न उदाहरण के ही खंड में दिखाई देने वाले कोई भी दो वेरिएबल उस खंड में सकारात्मक रूप से प्रकट नहीं होने चाहिए; वेरिएबलों की जोड़ी पर यह बाधा 2-संतोषजनक बाधा है। परिणामी 2-संतोषजनक उदाहरण के लिए संतोषजनक असाइनमेंट ढूंढकर, लुईस दिखाता है कि बहुपद समय में किसी भी नाम बदलने योग्य हॉर्न उदाहरण को हॉर्न उदाहरण में कैसे बदला जाए।<ref>{{citation | ||
| last = Lewis | first = Harry R. | author-link = Harry R. Lewis | | last = Lewis | first = Harry R. | author-link = Harry R. Lewis | ||
| doi = 10.1145/322047.322059 | | doi = 10.1145/322047.322059 | ||
Line 154: | Line 160: | ||
| title = Renaming a set of clauses as a Horn set | | title = Renaming a set of clauses as a Horn set | ||
| volume = 25 | | volume = 25 | ||
| year = 1978| s2cid = 3071958 }}.</ref> लंबे खंडों को | | year = 1978| s2cid = 3071958 }}.</ref> लंबे खंडों को अनेक छोटे खंडों में तोड़कर, और रैखिक-समय 2-संतुष्टि एल्गोरिथ्म को प्रयुक्त करके, इसे रैखिक समय तक कम करना संभव है।<ref>{{citation | ||
| last = Aspvall | first = Bengt | | last = Aspvall | first = Bengt | ||
| doi = 10.1016/0196-6774(80)90007-3 | | doi = 10.1016/0196-6774(80)90007-3 | ||
Line 167: | Line 173: | ||
===अन्य अनुप्रयोग=== | ===अन्य अनुप्रयोग=== | ||
2-संतुष्टि को [[अप्रत्यक्ष ग्राफ]]़ को पहचानने की समस्याओं पर भी | 2-संतुष्टि को [[अप्रत्यक्ष ग्राफ]]़ को पहचानने की समस्याओं पर भी प्रयुक्त किया गया है जिन्हें [[स्वतंत्र सेट (ग्राफ़ सिद्धांत)]] और [[पूर्ण द्विदलीय ग्राफ]]़ की छोटी संख्या में विभाजित किया जा सकता है,<ref>{{citation|first1=Andreas|last1=Brandstädt|author1-link=Andreas Brandstädt|first2=Peter Ladislaw|last2=Hammer|author2-link=Peter Ladislaw Hammer|first3=Van Bang|last3=Le|first4=Vadim V.|last4=Lozin|title=Bisplit graphs|journal=[[Discrete Mathematics (journal)|Discrete Mathematics]]|volume=299|issue=1–3|year=2005|pages=11–32|doi=10.1016/j.disc.2004.08.046}}.</ref> इंटरनेट के स्वायत्त उपप्रणालियों के बीच व्यावसायिक संबंधों का अनुमान लगाना,<ref>{{citation|first1=Hao|last1=Wang|first2=Haiyong|last2=Xie|first3=Yang Richard|last3=Yang|first4=Avi|last4=Silberschatz|first5=Li Erran|last5=Li|first6=Yanbin|last6=Liu|title=13TH IEEE International Conference on Network Protocols (ICNP'05) |contribution=Stable egress route selection for interdomain traffic engineering: model and analysis|year=2005|pages=16–29|doi=10.1109/ICNP.2005.39|isbn=978-0-7695-2437-5|citeseerx=10.1.1.106.7345|s2cid=4332805}}.</ref> और विकासवादी पेड़ों का पुनर्निर्माण।<ref>{{citation|first1=Eleazar|last1=Eskin|first2=Eran|last2=Halperin|first3=Richard M.|last3=Karp|author-link3=Richard Karp|title=Efficient reconstruction of haplotype structure via perfect phylogeny|journal=Journal of Bioinformatics and Computational Biology|year=2003|volume=1|issue=1|pages=1–20|doi=10.1142/S0219720003000174|pmid=15290779}}.</ref> | ||
== | ==सम्मिश्र ता और विस्तार== | ||
===एनएल-पूर्णता=== | ===एनएल-पूर्णता=== | ||
Line 182: | Line 188: | ||
| publisher = Addison-Wesley | | publisher = Addison-Wesley | ||
| year = 1994 | | year = 1994 | ||
| isbn = 978-0-201-53082-7}}., Thm. 16.3.</ref> इसका अर्थ यह है कि यह लघुगणकीय स्थान में गैर-नियतात्मक रूप से हल करने योग्य समस्याओं की [[जटिलता वर्ग]] [[एनएल (जटिलता)]] में सबसे कठिन या सबसे अभिव्यंजक समस्याओं में से है। यहां पूर्णता का मतलब है कि केवल लॉगरिदमिक स्थान का उपयोग करने वाली नियतात्मक ट्यूरिंग मशीन एनएल में किसी भी अन्य समस्या को समकक्ष 2-संतुष्टि समस्या में बदल सकती है। अधिक सुप्रसिद्ध | | isbn = 978-0-201-53082-7}}., Thm. 16.3.</ref> इसका अर्थ यह है कि यह लघुगणकीय स्थान में गैर-नियतात्मक रूप से हल करने योग्य समस्याओं की [[जटिलता वर्ग|सम्मिश्र ता वर्ग]] [[एनएल (जटिलता)|एनएल (सम्मिश्र ता)]] में सबसे कठिन या सबसे अभिव्यंजक समस्याओं में से है। यहां पूर्णता का मतलब है कि केवल लॉगरिदमिक स्थान का उपयोग करने वाली नियतात्मक ट्यूरिंग मशीन एनएल में किसी भी अन्य समस्या को समकक्ष 2-संतुष्टि समस्या में बदल सकती है। अधिक सुप्रसिद्ध सम्मिश्र ता वर्ग ''[[एनपी (जटिलता)|एनपी (सम्मिश्र ता)]]'' के लिए समान परिणामों के अनुरूप, यह परिवर्तन इमरमैन-स्ज़ेलेपीसीसेनी प्रमेय के साथ मिलकर एनएल में किसी भी समस्या को दूसरे क्रम के तर्क सूत्र के रूप में प्रस्तुत करने की अनुमति देता है, जिसमें लंबाई 2 तक सीमित खंडों के साथ एकल अस्तित्वगत रूप से परिमाणित विधेय होता है। ऐसे सूत्रों को एसओ-क्रोम के रूप में जाना जाता है।<ref name="ck04">{{citation | ||
| last1 = Cook | first1 = Stephen | author1-link = Stephen Cook | | last1 = Cook | first1 = Stephen | author1-link = Stephen Cook | ||
| last2 = Kolokolova | first2 = Antonina | | last2 = Kolokolova | first2 = Antonina | ||
Line 193: | Line 199: | ||
===सभी समाधानों का समुच्चय=== | ===सभी समाधानों का समुच्चय=== | ||
[[File:2SAT median graph.svg|thumb|upright=1.35|उदाहरण 2-संतुष्टि उदाहरण के सभी समाधानों का प्रतिनिधित्व करने वाला माध्य ग्राफ जिसका निहितार्थ ग्राफ ऊपर दिखाया गया है।]]2-संतुष्टि उदाहरण के सभी समाधानों के सेट में माध्यिका ग्राफ की संरचना होती है, जिसमें किनारा | [[File:2SAT median graph.svg|thumb|upright=1.35|उदाहरण 2-संतुष्टि उदाहरण के सभी समाधानों का प्रतिनिधित्व करने वाला माध्य ग्राफ जिसका निहितार्थ ग्राफ ऊपर दिखाया गया है।]]2-संतुष्टि उदाहरण के सभी समाधानों के सेट में माध्यिका ग्राफ की संरचना होती है, जिसमें किनारा वेरिएबल के सेट के मूल्यों को फ़्लिप करने के संचालन से मेल खाता है जो सभी दूसरे के समान या असमान होने के लिए बाध्य हैं। विशेष रूप से, इस तरह से किनारों का अनुसरण करके कोई भी किसी भी समाधान से किसी अन्य समाधान तक पहुंच सकता है। इसके विपरीत, किसी भी माध्य ग्राफ को इस तरह से 2-संतुष्टि उदाहरण के समाधान के सेट के रूप में दर्शाया जा सकता है। किन्हीं तीन समाधानों का माध्य प्रत्येक वेरिएबल को तीन समाधानों के बहुमत फलन में रखे गए मान पर सेट करके बनाया जाता है। यह माध्यिका हमेशा उदाहरण के लिए और समाधान बनाती है।<ref>{{citation | ||
| last1 = Bandelt | first1 = Hans-Jürgen | | last1 = Bandelt | first1 = Hans-Jürgen | ||
| last2 = Chepoi | first2 = Victor | | last2 = Chepoi | first2 = Victor | ||
Line 219: | Line 225: | ||
| volume = 555 | year = 1995}}.</ref> | | volume = 555 | year = 1995}}.</ref> | ||
{{harvtxt| | {{harvtxt|फेडर|1994}} किसी दिए गए 2-संतुष्टि उदाहरण के सभी समाधानों को कुशलतापूर्वक सूचीबद्ध करने और अनेक संबंधित समस्याओं को हल करने के लिए एल्गोरिदम का वर्णन करता है।<ref>{{citation|first=Tomás|last=Feder|title=Network flow and 2-satisfiability|journal=[[Algorithmica]]|volume=11|issue=3|year=1994|pages=291–319|doi=10.1007/BF01240738|s2cid=34194118}}.</ref> | ||
दो संतोषजनक असाइनमेंट खोजने के लिए एल्गोरिदम भी मौजूद हैं जिनकी दूसरे से अधिकतम [[हैमिंग दूरी]] है।<ref>{{citation|first1=Ola|last1=Angelsmark|first2=Johan|last2=Thapper|contribution=Algorithms for the maximum Hamming distance problem|title=Recent Advances in Constraints|publisher=Springer-Verlag|series=Lecture Notes in Computer Science|volume=3419|year=2005|pages=[https://archive.org/details/recentadvancesin0000join/page/128 128–141]|doi=10.1007/11402763_10|isbn=978-3-540-25176-7|url=https://archive.org/details/recentadvancesin0000join/page/128}}.</ref> | दो संतोषजनक असाइनमेंट खोजने के लिए एल्गोरिदम भी मौजूद हैं जिनकी दूसरे से अधिकतम [[हैमिंग दूरी]] है।<ref>{{citation|first1=Ola|last1=Angelsmark|first2=Johan|last2=Thapper|contribution=Algorithms for the maximum Hamming distance problem|title=Recent Advances in Constraints|publisher=Springer-Verlag|series=Lecture Notes in Computer Science|volume=3419|year=2005|pages=[https://archive.org/details/recentadvancesin0000join/page/128 128–141]|doi=10.1007/11402763_10|isbn=978-3-540-25176-7|url=https://archive.org/details/recentadvancesin0000join/page/128}}.</ref> | ||
===संतोषजनक असाइनमेंट की संख्या की गिनती=== | ===संतोषजनक असाइनमेंट की संख्या की गिनती=== | ||
# | #2एसएटी किसी दिए गए 2-सीएनएफ सूत्र में संतोषजनक असाइनमेंट की संख्या की गणना करने की समस्या है। यह गिनती समस्या (सम्मिश्र ता) तीव्र-पी-पूर्ण|#पी-पूर्ण है,<ref>{{citation | ||
| last1 = Valiant | first1 = Leslie G. | author-link = Leslie Valiant | | last1 = Valiant | first1 = Leslie G. | author-link = Leslie Valiant | ||
| year = 1979 | | year = 1979 | ||
Line 232: | Line 240: | ||
| pages= 410–421 | | pages= 410–421 | ||
| doi = 10.1137/0208032 | | doi = 10.1137/0208032 | ||
| issue = 3}}</ref> जिसका तात्पर्य यह है कि यह बहुपद समय में हल करने योग्य नहीं है जब तक कि P बनाम NP समस्या न हो|P = NP। इसके अलावा, # | | issue = 3}}</ref> जिसका तात्पर्य यह है कि यह बहुपद समय में हल करने योग्य नहीं है जब तक कि P बनाम NP समस्या न हो|P = NP। इसके अलावा, #2एसएटी के लिए कोई [[बहुपद-समय सन्निकटन योजना]] नहीं है जब तक कि एनपी (सम्मिश्र ता) = [[आरपी (जटिलता)|आरपी (सम्मिश्र ता)]] न हो और यह तब भी प्रयुक्त होता है जब इनपुट मोनोटोन 2-सीएनएफ सूत्रों तक सीमित होता है, यानी, 2-सीएनएफ सूत्र जिसमें प्रत्येक शाब्दिक (गणितीय तर्क) वेरिएबल की सकारात्मक घटना होती है।<ref>{{citation | ||
| last1 = Welsh | first1 = Dominic | author1-link = Dominic Welsh | | last1 = Welsh | first1 = Dominic | author1-link = Dominic Welsh | ||
| last2 = Gale | first2 = Amy | | last2 = Gale | first2 = Amy | ||
Line 239: | Line 247: | ||
| title = Aspects of complexity: minicourses in algorithmics, complexity and computational algebra: mathematics workshop, Kaikoura, January 7–15, 2000 | | title = Aspects of complexity: minicourses in algorithmics, complexity and computational algebra: mathematics workshop, Kaikoura, January 7–15, 2000 | ||
| pages = 115ff}}, Theorem 57.</ref> | | pages = 115ff}}, Theorem 57.</ref> | ||
2एसएटी फ़ॉर्मूले के लिए संतोषजनक असाइनमेंट की सटीक संख्या की गणना करने के लिए सबसे तेज़ ज्ञात एल्गोरिदम समय में चलता है <math>O(1.2377^n)</math>.<ref>{{citation|first1=Vilhelm|last1=Dahllöf|first2=Peter|last2=Jonsson|first3=Magnus|last3=Wahlström|title=Counting models for 2SAT and 3SAT formulae|journal=[[Theoretical Computer Science (journal)|Theoretical Computer Science]]|volume=332|issue=1–3|year=2005|pages=265–291|doi=10.1016/j.tcs.2004.10.037}}</ref> | |||
<ref>{{citation|first1=Martin|last1=Fürer|first2=Shiva Prasad|last2=Kasiviswanathan|contribution=Algorithms for counting 2-SAT solutions and colorings with applications|title=Algorithmic Aspects in Information and Management|publisher=Springer-Verlag|series=Lecture Notes in Computer Science|volume=4508|year=2007|pages=47–57|doi=10.1007/978-3-540-72870-2_5|isbn=978-3-540-72868-9|citeseerx=10.1.1.634.4498}}.</ref> | <ref>{{citation|first1=Martin|last1=Fürer|first2=Shiva Prasad|last2=Kasiviswanathan|contribution=Algorithms for counting 2-SAT solutions and colorings with applications|title=Algorithmic Aspects in Information and Management|publisher=Springer-Verlag|series=Lecture Notes in Computer Science|volume=4508|year=2007|pages=47–57|doi=10.1007/978-3-540-72870-2_5|isbn=978-3-540-72868-9|citeseerx=10.1.1.634.4498}}.</ref> | ||
<ref>{{citation|first1=Magnus|last1=Wahlström|contribution=A tighter bound for counting max-weight solutions to 2sat instances|title=International Workshop on Parameterized and Exact Computation|volume=5018|year=2008|pages=202–213|doi=10.1007/978-3-540-79723-4_19|series=Lecture Notes in Computer Science|isbn=978-3-540-79722-7|citeseerx=10.1.1.129.9232}}</ref> | <ref>{{citation|first1=Magnus|last1=Wahlström|contribution=A tighter bound for counting max-weight solutions to 2sat instances|title=International Workshop on Parameterized and Exact Computation|volume=5018|year=2008|pages=202–213|doi=10.1007/978-3-540-79723-4_19|series=Lecture Notes in Computer Science|isbn=978-3-540-79722-7|citeseerx=10.1.1.129.9232}}</ref> | ||
Line 246: | Line 254: | ||
===यादृच्छिक 2-संतोषजनक उदाहरण=== | ===यादृच्छिक 2-संतोषजनक उदाहरण=== | ||
सभी संभावित दो- | सभी संभावित दो-वेरिएबल खंडों के सेट से यादृच्छिक रूप से प्रत्येक खंड को समान रूप से चुनकर, किसी दिए गए वेरिएबल की संख्या n और खंडों के m के लिए, यादृच्छिक रूप से 2-संतोषजनक उदाहरण बनाया जा सकता है। जब m, n के सापेक्ष छोटा होता है, तो ऐसा उदाहरण संभवतः संतोषजनक होगा, किन्तु m के बड़े मानों के संतोषजनक होने की संभावनाएँ कम होती हैं। अधिक सटीक रूप से, यदि m/n को स्थिर α ≠ 1 के रूप में तय किया गया है, तो संतुष्टि की संभावना अनुक्रम की सीमा की ओर बढ़ जाती है क्योंकि n अनंत तक जाता है: यदि α < 1, सीमा है, जबकि यदि α > 1, सीमा शून्य है। इस प्रकार, समस्या α = 1 पर [[चरण संक्रमण]] प्रदर्शित करती है।<ref>{{citation|first1=Béla|last1=Bollobás|author1-link=Béla Bollobás|first2=Christian|last2=Borgs|first3=Jennifer T.|last3=Chayes|author3-link=Jennifer Tour Chayes|first4=Jeong Han|last4=Kim|first5=David B.|last5=Wilson|title=The scaling window of the 2-SAT transition|journal=Random Structures and Algorithms|volume=18|issue=3|pages=201–256|year=2001|doi=10.1002/rsa.1006|arxiv=math/9909031|s2cid=9954684}}; {{citation|first1=V.|last1=Chvátal|author-link1=Václav Chvátal|first2=B.|last2=Reed|title=Proceedings., 33rd Annual Symposium on Foundations of Computer Science |author2-link=Bruce Reed (mathematician)|contribution=Mick gets some (the odds are on his side)|year=1992|pages=620–627|doi=10.1109/SFCS.1992.267789|isbn=978-0-8186-2900-6|s2cid=5575389}}; {{citation|first=A.|last=Goerdt|title=A threshold for unsatisfiability|journal=[[Journal of Computer and System Sciences]]|volume=53|year=1996|pages=469–486|doi=10.1006/jcss.1996.0081|issue=3}}.</ref> | ||
===अधिकतम-2-संतुष्टि === | ===अधिकतम-2-संतुष्टि === | ||
अधिकतम-2-संतुष्टि समस्या (MAX-2- | अधिकतम-2-संतुष्टि समस्या (MAX-2-एसएटी) में, इनपुट प्रति खंड दो शाब्दिक (गणितीय तर्क) के साथ संयोजक सामान्य रूप में सूत्र है, और कार्य उन खंडों की अधिकतम संख्या निर्धारित करना है जिन्हें असाइनमेंट द्वारा साथ संतुष्ट किया जा सकता है। अधिक सामान्य अधिकतम संतुष्टि समस्या की तरह, MAX-2-एसएटी NP-हार्ड है। इसका प्रमाण बूलियन संतुष्टि समस्या से कमी है।<ref>{{citation|year=1976|author1=M. R. Garey|author2=D. S. Johnson|author3=L. J. Stockmeyer|title=Some simplified NP-complete graph problems|journal=Theoretical Computer Science|language=en|volume=1|issue=3|pages=237–267|doi=10.1016/0304-3975(76)90059-1|issn=0304-3975}}; see pp. 4–6</ref> | ||
एक [[ कट (ग्राफ सिद्धांत) |कट (ग्राफ सिद्धांत)]] खोजने की समस्या के रूप में मैक्स -2-सैट को तैयार करके (यानी, दो सबसेट में वर्टिस का विभाजन) उन किनारों की संख्या को अधिकतम करता है जो पहले सबसेट में एंडपॉइंट और दूसरे में एंडपॉइंट में एंडपॉइंट, निहितार्थ ग्राफ से संबंधित ग्राफ में ग्राफ को पूरा करने के लिए, जो कि कम से कम है। ।<ref>{{citation|first1=Michael|last1=Lewin|first2=Dror|last2=Livnar|first3=Uri|last3=Zwick|author3-link=Uri Zwick|contribution=Improved Rounding Techniques for the MAX 2-SAT and MAX DI-CUT Problems|title=Proceedings of the 9th International IPCO Conference on Integer Programming and Combinatorial Optimization|year=2002|pages=67–82|isbn=978-3-540-43676-8|publisher=Springer-Verlag}}</ref> संतुलित MAX 2- | एक [[ कट (ग्राफ सिद्धांत) |कट (ग्राफ सिद्धांत)]] खोजने की समस्या के रूप में मैक्स -2-सैट को तैयार करके (यानी, दो सबसेट में वर्टिस का विभाजन) उन किनारों की संख्या को अधिकतम करता है जो पहले सबसेट में एंडपॉइंट और दूसरे में एंडपॉइंट में एंडपॉइंट, निहितार्थ ग्राफ से संबंधित ग्राफ में ग्राफ को पूरा करने के लिए, जो कि कम से कम है। ।<ref>{{citation|first1=Michael|last1=Lewin|first2=Dror|last2=Livnar|first3=Uri|last3=Zwick|author3-link=Uri Zwick|contribution=Improved Rounding Techniques for the MAX 2-SAT and MAX DI-CUT Problems|title=Proceedings of the 9th International IPCO Conference on Integer Programming and Combinatorial Optimization|year=2002|pages=67–82|isbn=978-3-540-43676-8|publisher=Springer-Verlag}}</ref> संतुलित MAX 2-एसएटी उदाहरण MAX 2-एसएटी का उदाहरण है जहां प्रत्येक वेरिएबल समान भार के साथ सकारात्मक और ऋणात्मक रूप से प्रकट होता है। इस समस्या के लिए, ऑस्ट्रिन ने सन्निकटन अनुपात में सुधार किया है <math>\min \left\{(3 - \cos \theta)^{-1} (2 + (2/\pi)\theta) \,:\, \pi/2 \leq \theta \leq \pi \right\} = 0.943...</math>.<ref>{{citation | ||
| last = Austrin | first = Per | | last = Austrin | first = Per | ||
| contribution = Balanced Max 2-sat Might Not Be the Hardest | | contribution = Balanced Max 2-sat Might Not Be the Hardest | ||
Line 262: | Line 270: | ||
| year = 2007| s2cid = 2353625 | | year = 2007| s2cid = 2353625 | ||
}}.</ref> | }}.</ref> | ||
यदि अद्वितीय गेम का अनुमान सत्य है, तो बहुपद समय में 0.943... से बेहतर अनुमानित अनुपात के साथ, MAX 2- | यदि अद्वितीय गेम का अनुमान सत्य है, तो बहुपद समय में 0.943... से बेहतर अनुमानित अनुपात के साथ, MAX 2-एसएटी का अनुमान लगाना असंभव है, चाहे वह संतुलित हो या नहीं।<ref>{{citation|first1=Subhash|last1=Khot|author1-link=Subhash Khot|first2=Guy|last2=Kindler|first3=Elchanan|last3=Mossel|first4=Ryan|last4=O'Donnell|contribution=Optimal Inapproximability Results for MAX-CUT and Other 2-Variable CSPs?|title=FOCS '04: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science|year=2004|pages=146–154|doi=10.1109/FOCS.2004.49|isbn=978-0-7695-2228-9|publisher=IEEE|citeseerx=10.1.1.126.2295|s2cid=2090495}}</ref> कमजोर धारणा के तहत कि पी बनाम एनपी समस्या | पी ≠ एनपी, समस्या को केवल 21/22 = 0.95454 से बेहतर स्थिरांक के भीतर अनुपयुक्त माना जाता है...<ref>{{citation|first=Johan|last=Håstad|author-link=Johan Håstad|title=Some optimal inapproximability results|journal=[[Journal of the ACM]]|volume=48|issue=4|year=2001|pages=798–859|doi=10.1145/502090.502098|citeseerx=10.1.1.638.2808|s2cid=5120748}}.</ref> | ||
विभिन्न लेखकों ने MAX-2- | विभिन्न लेखकों ने MAX-2-एसएटी उदाहरणों के सटीक समाधान के लिए घातीय सबसे खराब समय सीमा का भी पता लगाया है।<ref>{{citation|first1=N.|last1=Bansal|first2=V.|last2=Raman|contribution=Upper bounds for MaxSat: further improved|editor1-first=A.|editor1-last=Aggarwal|editor2-first=C.|editor2-last=Pandu Rangan|title=Proc. 10th Conf. Algorithms and Computation, ISAAC'99|series=Lecture Notes in Computer Science|volume=1741|publisher=Springer-Verlag|year=1999|pages=247–258}}; {{citation|first1=Jens|last1=Gramm|first2=Edward A.|last2=Hirsch|first3=Rolf|last3=Niedermeier|first4=Peter|last4=Rossmanith|author3-link=Rolf Niedermeier|title=Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT|journal=[[Discrete Applied Mathematics]]|volume=130|issue=2|year=2003|pages=139–155|doi=10.1016/S0166-218X(02)00402-X}}; {{citation|first1=Arist|last1=Kojevnikov|first2=Alexander S.|last2=Kulikov|contribution=A new approach to proving upper bounds for MAX-2-SAT|title=Proc. 17th ACM-SIAM Symp. Discrete Algorithms|year=2006|pages=11–17|doi=10.1145/1109557.1109559|isbn=978-0-89871-605-4|s2cid=10194873}}</ref> | ||
===भारित-2-संतुष्टि=== | ===भारित-2-संतुष्टि=== | ||
भारित 2-संतुष्टि समस्या ( | भारित 2-संतुष्टि समस्या (W2एसएटी) में, इनपुट है <math>n</math>-परिवर्तनीय 2एसएटी उदाहरण और पूर्णांक {{math|''k''}}, और समस्या यह तय करना है कि वास्तव में कोई संतोषजनक असाइनमेंट मौजूद है या नहीं {{math|''k''}} वेरिएबल सत्य हैं।<ref name=fg06/> | ||
W2एसएटी समस्या में विशेष मामले के रूप में सेट खोजने की [[वर्टेक्स कवर समस्या]] सम्मिलित है {{mvar|k}}<nowiki> शीर्ष जो किसी दिए गए अप्रत्यक्ष ग्राफ़ के सभी किनारों को साथ छूते हैं। शीर्ष कवर समस्या के किसी भी उदाहरण के लिए, कोई ग्राफ़ के प्रत्येक शीर्ष के लिए वेरिएबल के साथ समतुल्य W2एसएटी समस्या का निर्माण कर सकता है। प्रत्येक किनारा {{math|</nowiki>''uv''}ग्राफ़ के } को 2एसएटी खंड द्वारा दर्शाया जा सकता है {{math|''u'' ∨ ''v''}} जिसे दोनों में से किसी को सम्मिलित करके ही संतुष्ट किया जा सकता है {{mvar|u}} या {{mvar|v}} समाधान के वास्तविक वेरिएबलों के बीच। फिर परिणामी 2एसएटी सूत्र के संतोषजनक उदाहरण वर्टेक्स कवर समस्या के समाधान को एन्कोड करते हैं, और इसके साथ संतोषजनक असाइनमेंट होता है {{math|''k''}} सत्य वेरिएबल यदि और केवल यदि कोई शीर्ष आवरण है {{math|''k''}} शिखर. इसलिए, वर्टेक्स कवर की तरह, W2एसएटी NP-पूर्ण है। | |||
इसके अलावा, पैरामीटरयुक्त | इसके अलावा, पैरामीटरयुक्त सम्मिश्र ता में W2एसएटी प्राकृतिक W(1)|W[1]-पूर्ण समस्या प्रदान करता है,<ref name=fg06>{{Citation | ||
| last1 = Flum | first1 = Jörg | | last1 = Flum | first1 = Jörg | ||
| last2 = Grohe | first2 = Martin | author2-link = Martin Grohe | | last2 = Grohe | first2 = Martin | author2-link = Martin Grohe | ||
Line 277: | Line 285: | ||
| pages = 69–70 | | pages = 69–70 | ||
| title = Parameterized Complexity Theory | year = 2006 | publisher = Springer | | title = Parameterized Complexity Theory | year = 2006 | publisher = Springer | ||
| isbn = 978-3-540-29952-3 }}</ref> जिसका तात्पर्य यह है कि | | isbn = 978-3-540-29952-3 }}</ref> जिसका तात्पर्य यह है कि W2एसएटी [[निश्चित-पैरामीटर ट्रैक्टेबल]] नहीं है जब तक कि यह W(1)|W[1] में सभी समस्याओं के लिए मान्य न हो। अर्थात्, यह संभावना नहीं है कि W2एसएटी के लिए कोई एल्गोरिदम मौजूद है जिसका रनिंग टाइम रूप लेता है {{math|''f''(''k'')·''n''<sup>''O''(1)</sup>}}. इससे भी अधिक दृढ़ता से, W2एसएटी को समय पर हल नहीं किया जा सकता है {{math|''n''<sup>''o''(''k'')</sup>}} जब तक कि घातीय समय परिकल्पना विफल न हो जाए।<ref>{{citation | ||
|first1=Jianer | last1=Chen | |first1=Jianer | last1=Chen | ||
|first2=Xiuzhen | last2=Huang | |first2=Xiuzhen | last2=Huang | ||
Line 292: | Line 300: | ||
===मात्राबद्ध बूलियन सूत्र=== | ===मात्राबद्ध बूलियन सूत्र=== | ||
2-संतुष्टि के लिए पहला बहुपद-समय एल्गोरिदम खोजने के साथ-साथ, {{harvtxt| | 2-संतुष्टि के लिए पहला बहुपद-समय एल्गोरिदम खोजने के साथ-साथ, {{harvtxt|क्रोम |1967}} ने ट्रू क्वांटिफाइड बूलियन फॉर्मूला के मूल्यांकन की समस्या भी तैयार की जिसमें क्वांटिफाई किया जा रहा फॉर्मूला 2-सीएनएफ फॉर्मूला है। 2-संतुष्टि समस्या इस परिमाणित 2-सीएनएफ समस्या का विशेष स्तिथि है, जिसमें सभी परिमाणक [[अस्तित्वगत परिमाणक]] हैं। क्रॉम ने इन सूत्रों के लिए प्रभावी निर्णय प्रक्रिया भी विकसित की। {{harvtxt|एस्पवॉल|प्लास |टारजन|1979}} ने दिखाया कि इसे दृढ़ता से जुड़े अवयवों और टोपोलॉजिकल ऑर्डरिंग की उनकी तकनीक के विस्तार द्वारा, रैखिक समय में हल किया जा सकता है।<ref name="Krom1967"/><ref name="APT79"/> | ||
===अनेक-मूल्यवान तर्क=== | ===अनेक-मूल्यवान तर्क=== | ||
2-संतुष्टि समस्या को प्रस्तावित [[बहु-मूल्यवान तर्क]] | 2-संतुष्टि समस्या को प्रस्तावित [[बहु-मूल्यवान तर्क]] के लिए भी पूछा जा सकता है। एल्गोरिदम आमतौर पर रैखिक नहीं होते हैं, और कुछ तर्कों के लिए समस्या एनपी-पूर्ण भी होती है। देखना {{harvs|last=हनले|year=2001|year2=2003|txt}} सर्वेक्षणों के लिए.<ref>{{citation|editor1-first=Dov M.|editor1-last=Gabbay|editor2-first=Franz|editor2-last=Günthner|title=Handbook of Philosophical Logic|year=2001|publisher=Springer|isbn=978-94-017-0452-6|pages=297–395|chapter=Advanced many-valued logics|first=Reiner|last=Hähnle|volume=2|doi=10.1007/978-94-017-0452-6_5}} (see in particular [https://books.google.com/books?id=_ol81ow-1s4C&pg=PA373 p. 373]); {{citation|editor1-first=Melvin|editor1-last=Fitting|editor2-first=Ewa|editor2-last=Orlowska|editor2-link= Ewa Orłowska |title=Beyond two: theory and applications of multiple-valued logic|year=2003|publisher=Springer|isbn=978-3-7908-1541-2|first=Reiner|last=Hähnle|chapter=Complexity of Many-valued Logics|doi=10.1007/978-3-7908-1769-0_9|series=Studies in Fuzziness and Soft Computing|volume=114|pages=211–233}}</ref> | ||
Revision as of 13:39, 4 August 2023
कंप्यूटर विज्ञान में, 2-संतुष्टि, 2-एसएटी या सिर्फ 2एसएटी वेरिएबल के जोड़े पर बाधा (गणित) की प्रणाली को संतुष्ट करने के लिए, वेरिएबल को मान निर्दिष्ट करने की कम्प्यूटेशनल समस्या है, जिनमें से प्रत्येक में दो संभावित मान होते हैं। यह सामान्य बूलियन संतुष्टि समस्या का विशेष स्तिथि है, जिसमें दो से अधिक वेरिएबल पर बाधाएं और बाधा संतुष्टि समस्याएं सम्मिलित हो सकती हैं, जो प्रत्येक वेरिएबल के मान के लिए दो से अधिक विकल्पों की अनुमति दे सकती हैं। किन्तु उन अधिक सामान्य समस्याओं के विपरीत, जो एनपी-पूर्ण हैं, जिसको कि 2-संतुष्टि को बहुपद समय में हल किया जा सकता है।
2-संतुष्टि समस्या के उदाहरणों को सामान्यतः विशेष प्रकार के बूलियन तर्क के रूप में व्यक्त किया जाता है, जिसे संयोजक सामान्य रूप (2-सीएनएफ) या क्रॉम सूत्र कहा जाता है। वैकल्पिक रूप से, उन्हें विशेष प्रकार के निर्देशित ग्राफ, निहितार्थ ग्राफ के रूप में व्यक्त किया जा सकता है, जो उदाहरण के वेरिएबल और उनके निषेधों को ग्राफ में शीर्ष के रूप में व्यक्त करता है, और वेरिएबल के जोड़े पर बाधाओं को निर्देशित किनारों के रूप में व्यक्त करता है। इन दोनों प्रकार के इनपुट को रैखिक समय में हल किया जा सकता है, या तो बैक ट्रैकिंग पर आधारित विधि द्वारा या निहितार्थ ग्राफ के दृढ़ता से जुड़े अवयवों का उपयोग करके। रिज़ॉल्यूशन (तर्क), अतिरिक्त वैध बाधाओं को बनाने के लिए बाधाओं के जोड़े को संयोजित करने की विधि, बहुपद समय समाधान की ओर भी ले जाती है। 2-संतोषजनक समस्याएं संयोजक सामान्य रूप सूत्रों के दो प्रमुख उपवर्गों में से प्रदान करती हैं जिन्हें बहुपद समय में हल किया जा सकता है; दो उपवर्गों में से दूसरा हॉर्न-संतुष्टि है ।
2-संतुष्टि को ज्यामिति और विज़ुअलाइज़ेशन समस्याओं पर प्रयुक्त किया जा सकता है जिसमें वस्तुओं के संग्रह में प्रत्येक के दो संभावित स्थान होते हैं और लक्ष्य प्रत्येक वस्तु के लिए प्लेसमेंट ढूंढना है जो अन्य वस्तुओं के साथ ओवरलैप होने से बचाता है। अन्य अनुप्रयोगों में क्लस्टर के व्यास के योग को कम करने के लिए क्लस्टरिंग डेटा, कक्षा और खेल शेड्यूलिंग और उनके क्रॉस-सेक्शन के बारे में जानकारी से आकृतियों को पुनर्प्राप्त करना सम्मिलित है।
कम्प्यूटेशनल सम्मिश्रता सिद्धांत में, 2-संतुष्टि एनएल-पूर्ण समस्या का उदाहरण प्रदान करती है, जिसे भंडारण की लघुगणकीय मात्रा का उपयोग करके गैर-नियतात्मक रूप से हल किया जा सकता है और यह इस संसाधन में हल करने योग्य सबसे कठिन समस्याओं में से है। 2-संतुष्टि उदाहरण के सभी समाधानों के सेट को माध्यिका ग्राफ की संरचना दी जा सकती है, किन्तु इन समाधानों की गिनती शार्प-P-पूर्ण| या P-पूर्ण है और इसलिए बहुपद-समय समाधान की उम्मीद नहीं है। यादृच्छिक उदाहरणों को हल करने योग्य से अघुलनशील उदाहरणों में तेज चरण संक्रमण से गुजरना पड़ता है क्योंकि वेरिएबल के लिए बाधाओं का अनुपात 1 से अधिक बढ़ जाता है, घटना अनुमानित है किन्तु संतुष्टि समस्या के अधिक सम्मिश्र रूपों के लिए अप्रमाणित है। 2-संतोषजनकता की कम्प्यूटेशनल रूप से कठिन विविधता, सत्य असाइनमेंट ढूंढना जो संतुष्ट बाधाओं की संख्या को अधिकतम करता है, अनुमानित एल्गोरिदम है जिसकी अधिकतमता अद्वितीय गेम अनुमान पर निर्भर करती है, और और कठिन भिन्नता, वास्तविक वेरिएबल की संख्या को कम करने वाला संतोषजनक असाइनमेंट ढूंढना, पैरामीटरयुक्त सम्मिश्रता के लिए महत्वपूर्ण परीक्षण स्तिथि है।
समस्या प्रतिनिधित्व
इस प्रकार के विशेष प्रतिबंधित रूप के साथ बूलियन अभिव्यक्ति का उपयोग करके 2-संतुष्टि समस्या का वर्णन किया जा सकता है। यह क्लॉज (तर्क) का तार्किक संयोजन (एक बूलियन और ऑपरेशन) है, जहां प्रत्येक क्लॉज दो वेरिएबल या ऋणात्मक वेरिएबल का वियोजन (एक बूलियन या ऑपरेशन) है। इस सूत्र में आने वाले वेरिएबल या उनके निषेधन को शाब्दिक (गणितीय तर्क) कहा जाता है।[1] उदाहरण के लिए, निम्नलिखित सूत्र संयोजक सामान्य रूप में है, जिसमें सात वेरिएबल , ग्यारह उपवाक्य और 22 अक्षर हैं:
इस रूप में सूत्रों को 2-सीएनएफ सूत्र के रूप में जाना जाता है। इस नाम में 2 प्रति खंड शाब्दिकों की संख्या को दर्शाता है, और सीएनएफ संयोजक सामान्य रूप के लिए है, विच्छेदन के संयोजन के रूप में प्रकार की बूलियन अभिव्यक्ति है।[1] कैलिफ़ोर्निया विश्वविद्यालय, डेविस के गणितज्ञ मेल्वेन आर. क्रॉम के कार्य के पश्चात, उन्हें क्रॉम सूत्र भी कहा जाता है, जिनका 1967 का पेपर 2-संतुष्टि समस्या पर सबसे शुरुआती कार्यों में से था।[2]
2-सीएनएफ सूत्र में प्रत्येक खंड वेरिएबल या अस्वीकृत वेरिएबल से दूसरे में निहितार्थ के लिए तार्किक तुल्यता है। उदाहरण के लिए, उदाहरण में दूसरा खंड तीन समकक्ष विधियों में से किसी में लिखा जा सकता है:
2-संतुष्टि उदाहरण का वर्णन करने का तीसरा, अधिक ग्राफिकल विधि निहितार्थ ग्राफ के रूप में है। निहितार्थ ग्राफ निर्देशित ग्राफ है जिसमें प्रति वेरिएबल या ऋणात्मक वेरिएबल में शीर्ष (ग्राफ सिद्धांत) होता है, और शीर्ष को दूसरे से जोड़ने वाला किनारा होता है जब भी संबंधित वेरिएबल उदाहरण के निहितार्थ सामान्य रूप में निहितार्थ से संबंधित होते हैं। निहितार्थ ग्राफ तिरछा-सममित ग्राफ होना चाहिए, जिसका अर्थ है कि इसमें ग्राफ ऑटोमोर्फिज्म है जो प्रत्येक वेरिएबल को उसके निषेध में ले जाता है और सभी किनारों के झुकाव को उलट देता है।[4]
एल्गोरिदम
2-संतुष्टि समस्या को हल करने के लिए अनेक एल्गोरिदम ज्ञात हैं। उनमें से सबसे कुशल रैखिक समय लेते हैं।[2][4][5]
संकल्प और सकर्मक समापन
क्रोम (1967) 2-संतोषजनक उदाहरणों को हल करने के लिए निम्नलिखित बहुपद समय निर्णय प्रक्रिया का वर्णन किया गया है।[2]
मान लीजिए कि 2-संतोषजनक उदाहरण में दो खंड हैं जो दोनों ही वेरिएबल x का उपयोग करते हैं, किन्तु x को खंड में नकार दिया गया है और दूसरे में नहीं। फिर दोनों खंडों को मिलाकर तीसरा खंड तैयार किया जा सकता है, जिसमें दो खंडों में दो अन्य शाब्दिक अर्थ होंगे; जब पहले दो खंड संतुष्ट हों तो यह तीसरा खंड भी संतुष्ट होना चाहिए। उदाहरण के लिए, हम खंडों और को जोड़ सकते हैं इस प्रकार उपवाक्य का निर्माण करें . 2-सीएनएफ सूत्र के निहितार्थ रूप के संदर्भ में, यह नियम दो निहितार्थ खोजने और के समान है, और सकर्मक संबंध द्वारा तीसरे निहितार्थ का अनुमान लगाना होता है .[2]
क्रॉम लिखते हैं कि सूत्र सुसंगत है यदि इस अनुमान नियम को बार-बार प्रयुक्त करने से दोनों खंड उत्पन्न नहीं हो सकते हैं और , किसी भी वेरिएबल के लिए . जैसा कि उन्होंने साबित किया है, 2-सीएनएफ फॉर्मूला तभी संतोषजनक है जब यह सुसंगत हो। क्योंकि, यदि कोई सूत्र सुसंगत नहीं है, तो दोनों खंडों को संतुष्ट करना संभव नहीं है और इसके साथ ही। और, यदि यह सुसंगत है, तो रूप के खंड को बार-बार जोड़कर सूत्र को बढ़ाया जा सकता है या समय में, प्रत्येक चरण में एकरूपता बनाए रखना, जब तक कि इसमें प्रत्येक वेरिएबल के लिए ऐसा खंड सम्मिलित न हो जाए। इन विस्तार वेरिएबल णों में से प्रत्येक में, स्थिरता बनाए रखते हुए इन दो खंडों में से को हमेशा जोड़ा जा सकता है, यदि नहीं तो अनुमान नियम का उपयोग करके अन्य खंड उत्पन्न किया जा सकता है। बार जब सभी वेरिएबल्स के सूत्र में इस रूप का खंड होता है, तो वेरिएबल सेट करके सभी वेरिएबल्स का संतोषजनक असाइनमेंट उत्पन्न किया जा सकता है यदि सूत्र में खंड सम्मिलित है तो सत्य है और यदि सूत्र में खंड सम्मिलित है तो इसे गलत पर सेट करना .[2]
क्रॉम मुख्य रूप से एल्गोरिदम की दक्षता के अतिरिक्त अनुमान नियमों की प्रणालियों की पूर्णता (तर्क) से चिंतित था। चूँकि, उनकी पद्धति 2-संतुष्टि समस्याओं को हल करने के लिए बहुपद समयबद्धता की ओर ले जाती है। समान वेरिएबल का उपयोग करने वाले सभी खंडों को साथ समूहित करके, और खंडों की प्रत्येक जोड़ी पर अनुमान नियम प्रयुक्त करके, किसी दिए गए 2-सीएनएफ उदाहरण से संभव सभी अनुमान ढूंढना संभव है, और यह परीक्षण करना संभव है कि क्या यह सुसंगत है, कुल समय में O(n3), जहाँ n उदाहरण में वेरिएबलों की संख्या है। यह सूत्र वेरिएबलों की संख्या को गुणा करने से O(n2) प्राप्त होता है किसी दिए गए वेरिएबल को सम्मिलित करने वाले खंडों के जोड़े की संख्या, जिस पर अनुमान नियम प्रयुक्त किया जा सकता है। इस प्रकार, यह निर्धारित करना संभव है कि दिया गया 2-सीएनएफ उदाहरण समय में संतोषजनक या नहीं O(n3) है . क्योंकि क्रॉम की विधि का उपयोग करके संतोषजनक असाइनमेंट खोजने में अनुक्रम सम्मिलित होता है O(n) निरंतरता की जांच, इसमें समय लगेगा O(n4). इवेन, इटाई & शमीर (1976) तेज़ समय सीमा का उद्धरण दें O(n2) इस एल्गोरिथम के लिए, इसके संचालन के अधिक सावधानीपूर्वक क्रम पर आधारित है। फिर भी, पश्चात के रैखिक समय एल्गोरिदम द्वारा इस छोटी समय सीमा में भी अधिक सुधार किया गया था इवेन, इटाई & शमीर (1976) और एस्पवॉल, प्लास & टारजन (1979) .
2-संतुष्टि उदाहरण के निहितार्थ ग्राफ के संदर्भ में, क्रॉम के अनुमान नियम की व्याख्या ग्राफ के संक्रमणीय समापन के निर्माण के रूप में की जा सकती है। जैसा कुक (1971) देखता है, इसे रिज़ॉल्यूशन (तर्क) के सिद्धांत का उपयोग करके संतुष्टि समस्याओं को हल करने के लिए डेविस-पुटनम एल्गोरिदम के उदाहरण के रूप में भी देखा जा सकता है। इसकी शुद्धता डेविस-पुटनम एल्गोरिथ्म की अधिक सामान्य शुद्धता से अनुसरण करती है। इसकी बहुपद समय सीमा इस तथ्य से उत्पन्न होती है कि प्रत्येक रिज़ॉल्यूशन चरण उदाहरण में खंडों की संख्या बढ़ाता है, जो कि वेरिएबल की संख्या के द्विघात फलन द्वारा ऊपरी सीमा पर होता है।[6]
सीमित बैकट्रैकिंग
इवेन, इटाई & शमीर (1976) बाइनरी डेटा और जोड़ीदार बाधाओं के साथ बाधा संतुष्टि समस्याओं को हल करने के लिए सीमित बैकट्रैकिंग से जुड़ी तकनीक का वर्णन करता है जहाँ वह इस तकनीक को कक्षा समय-निर्धारण की समस्या पर प्रयुक्त करते हैं, किन्तु वे यह भी देखते हैं कि यह 2-एसएटी सहित अन्य समस्याओं पर भी प्रयुक्त होती है।[5]
उनके दृष्टिकोण का मूल विचार समय में वेरिएबल , आंशिक सत्य असाइनमेंट का निर्माण करना है। एल्गोरिदम के कुछ चरण चयन बिंदु हैं, ऐसे बिंदु जिन पर वेरिएबल को दो अलग-अलग सत्य मानों में से कोई दिया जा सकता है, और एल्गोरिदम के पश्चात के वेरिएबल णों के कारण यह इन विकल्प बिंदुओं में से किसी पर पीछे जा सकता है। चूँकि , केवल सबसे हालिया विकल्प को ही वापस लिया जा सकता है। नवीनतम से पहले किए गए सभी विकल्प स्थायी हैं।[5]
प्रारंभ में, कोई विकल्प बिंदु नहीं है, और सभी वेरिएबल अनअसाइन किए गए हैं। प्रत्येक चरण में, एल्गोरिदम उस वेरिएबल को चुनता है जिसका मान सेट करना है, इस प्रकार:
- यदि कोई ऐसा खंड है जिसके दोनों वेरिएबल पहले से ही सेट हैं, इस तरह से जो खंड को गलत साबित करता है, तो एल्गोरिदम अपने सबसे हालिया विकल्प बिंदु पर वापस आ जाता है, उस विकल्प के पश्चात से किए गए असाइनमेंट को पूर्ववत कर देता है, और उस विकल्प पर किए गए निर्णय को उलट देता है। यदि कोई विकल्प बिंदु नहीं है, या यदि एल्गोरिदम पहले से ही सबसे हालिया विकल्प बिंदु पर पीछे हट गया है, तो यह खोज को रोक देता है और रिपोर्ट करता है कि इनपुट 2-सीएनएफ फॉर्मूला असंतोषजनक है।
- यदि कोई ऐसा खंड है जिसमें खंड के दो वेरिएबलों में से पहले ही सेट किया जा चुका है, और खंड अभी भी या तो सत्य या गलत हो सकता है, तो दूसरा वेरिएबल इस तरह से सेट किया जाता है जो खंड को सत्य बनने के लिए मजबूर करता है।
- शेष मामले में, प्रत्येक खंड के या तो सत्य होने की गारंटी है, चाहे शेष वेरिएबल कैसे भी निर्दिष्ट किए गए हों, या इसके दो वेरिएबल में से किसी को भी अभी तक निर्दिष्ट नहीं किया गया है। इस मामले में एल्गोरिदम नया विकल्प बिंदु बनाता है और किसी भी अनअसाइन किए गए वेरिएबल को मनमाने ढंग से चुने गए मान पर सेट करता है।
सहज रूप से, एल्गोरिथ्म अपने प्रत्येक विकल्प को चुनने के पश्चात अनुमान की सभी श्रृंखलाओं का पालन करता है। इससे या तो विरोधाभास पैदा होता है और कदम पीछे हट जाता है, या, यदि कोई विरोधाभास नहीं निकलता है, तो इसका मतलब यह है कि चुनाव सही था जो संतोषजनक असाइनमेंट की ओर ले जाता है। इसलिए, एल्गोरिदम या तो सही ढंग से संतोषजनक असाइनमेंट पाता है या यह सही ढंग से निर्धारित करता है कि इनपुट असंतोषजनक है।[5]
यहां तक कि एट अल. इस एल्गोरिथम को कुशलतापूर्वक कैसे कार्यान्वित किया जाए, इसका विस्तार से वर्णन नहीं किया गया। वे केवल यह बताते हैं कि किसी भी निर्णय के निहितार्थ खोजने के लिए उपयुक्त डेटा संरचनाओं का उपयोग करके, एल्गोरिदम के प्रत्येक चरण (बैकट्रैकिंग के अलावा) को जल्दी से निष्पादित किया जा सकता है। चूँकि , कुछ इनपुट के कारण एल्गोरिदम अनेक बार बैकट्रैक कर सकता है, हर बार बैकट्रैकिंग से पहले अनेक चरण निष्पादित करता है, इसलिए इसकी समग्र सम्मिश्र ता अरेखीय हो सकती है। इस समस्या से बचने के लिए, वे एल्गोरिदम को संशोधित करते हैं जिससे , प्रत्येक विकल्प बिंदु पर पहुंचने के पश्चात, यह विकल्प बिंदु पर वेरिएबल सेट के लिए दो असाइनमेंट का साथ परीक्षण करना शुरू कर दे, दोनों असाइनमेंट में से प्रत्येक पर समान संख्या में चरण खर्च करें। जैसे ही इन दो असाइनमेंट में से का परीक्षण और विकल्प बिंदु बनाता है, दूसरा परीक्षण रोक दिया जाता है, जिससे एल्गोरिदम के किसी भी चरण में बैकट्रैकिंग ट्री की केवल दो शाखाएं हों जिनका अभी भी परीक्षण किया जा रहा हो। इस प्रकार, किसी भी वेरिएबल के लिए दो परीक्षण करने में बिताया गया कुल समय इनपुट सूत्र के उन वेरिएबलों और खंडों की संख्या के समानुपाती होता है जिनके मान स्थायी रूप से निर्दिष्ट होते हैं। परिणामस्वरूप, एल्गोरिथ्म कुल मिलाकर रैखिक समय लेता है।[5]
मजबूती से जुड़े घटक
एस्पवॉल, प्लास & टारजन (1979) ग्राफ़ सिद्धांत से दृढ़ता से जुड़े अवयवों की धारणा के आधार पर, 2-संतोषजनक उदाहरणों को हल करने के लिए सरल रैखिक समय प्रक्रिया मिली।[4]
एक निर्देशित ग्राफ़ में दो शीर्षों को एक-दूसरे से मजबूती से जुड़ा हुआ माना जाता है यदि से दूसरे तक कोई निर्देशित पथ हो और इसके विपरीत। यह तुल्यता संबंध है, और ग्राफ़ के शीर्षों को दृढ़ता से जुड़े अवयवों , उपसमुच्चयों में विभाजित किया जा सकता है जिनके भीतर प्रत्येक दो शीर्ष दृढ़ता से जुड़े हुए हैं। गहराई-पहली खोज के आधार पर ग्राफ़ के दृढ़ता से जुड़े अवयवों को खोजने के लिए अनेक कुशल रैखिक समय एल्गोरिदम हैं: टार्जन के दृढ़ता से जुड़े घटक एल्गोरिदम[7] और पथ-आधारित मजबूत घटक एल्गोरिदम[8] प्रत्येक एकल गहराई-पहली खोज करता है। कोसाराजू का एल्गोरिदम दो गहराई-पहली खोज करता है, किन्तु यह बहुत सरल है।
निहितार्थ ग्राफ के संदर्भ में, जब भी शाब्दिक से दूसरे और इसके विपरीत निहितार्थ की श्रृंखला मौजूद होती है, तो दो शाब्दिक ही दृढ़ता से जुड़े घटक से संबंधित होते हैं। इसलिए, दिए गए 2-संतुष्टि उदाहरण के लिए किसी भी संतोषजनक असाइनमेंट में दो शाब्दिकों का समान मान होना चाहिए। विशेष रूप से, यदि वेरिएबल और उसका निषेध दोनों ही मजबूती से जुड़े घटक से संबंधित हैं, तो उदाहरण को संतुष्ट नहीं किया जा सकता है, क्योंकि इन दोनों शाब्दिकों को समान मान निर्दिष्ट करना असंभव है। एस्पवॉल एट अल के रूप में। दिखाया गया है, यह आवश्यक और पर्याप्त शर्त है: 2-सीएनएफ फॉर्मूला तभी संतोषजनक है जब कोई ऐसा वेरिएबल न हो जो इसके निषेध के समान मजबूती से जुड़े घटक से संबंधित हो।[4]
यह तुरंत 2-सीएनएफ सूत्रों की संतुष्टि के परीक्षण के लिए रैखिक समय एल्गोरिदम की ओर ले जाता है: बस निहितार्थ ग्राफ पर मजबूत कनेक्टिविटी विश्लेषण करें और जांचें कि प्रत्येक वेरिएबल और उसका निषेध अलग-अलग अवयवों से संबंधित है। चूँकि , एस्पवॉल एट अल के रूप में। यह भी दिखाया गया है, यह संतोषजनक असाइनमेंट खोजने के लिए रैखिक समय एल्गोरिदम की ओर भी ले जाता है, जब कोई मौजूद होता है। उनका एल्गोरिदम निम्नलिखित चरण निष्पादित करता है:
- उदाहरण के निहितार्थ ग्राफ का निर्माण करें, और मजबूत कनेक्टिविटी विश्लेषण के लिए किसी भी ज्ञात रैखिक-समय एल्गोरिदम का उपयोग करके इसके दृढ़ता से जुड़े अवयवों को ढूंढें।
- जांचें कि क्या किसी दृढ़ता से जुड़े घटक में वेरिएबल और उसका निषेध दोनों सम्मिलित हैं। यदि हां, तो रिपोर्ट करें कि स्तिथि संतोषजनक नहीं है और रुकें।
- निहितार्थ ग्राफ के मजबूती से जुड़े घटक का निर्माण करें, छोटा ग्राफ जिसमें प्रत्येक मजबूती से जुड़े घटक के लिए शीर्ष और घटक से किनारा हो i घटक के लिए j जब भी निहितार्थ ग्राफ़ में कोई किनारा होता है uv ऐसा है कि u घटक से संबंधित है i और v घटक से संबंधित है j. संक्षेपण स्वचालित रूप से निर्देशित चक्रीय ग्राफ है और, निहितार्थ ग्राफ की तरह, जिससे इसे बनाया गया था, यह तिरछा-सममित ग्राफ है|तिरछा-सममित।
- संक्षेपण के शीर्षों को टोपोलॉजिकल छँटाई करना। व्यवहार में इसे पिछले चरण के साइड इफेक्ट के रूप में कुशलतापूर्वक प्राप्त किया जा सकता है, क्योंकि घटक कोसाराजू के एल्गोरिदम द्वारा टोपोलॉजिकल क्रम में और टारजन के एल्गोरिदम द्वारा रिवर्स टोपोलॉजिकल क्रम में उत्पन्न होते हैं।[9]
- रिवर्स टोपोलॉजिकल ऑर्डर में प्रत्येक घटक के लिए, यदि इसके वेरिएबल में पहले से ही सत्य असाइनमेंट नहीं हैं, तो घटक में सभी शाब्दिक को सत्य पर सेट करें। इसके कारण पूरक घटक के सभी अक्षर गलत पर सेट हो जाते हैं।
रिवर्स टोपोलॉजिकल ऑर्डरिंग और तिरछी-समरूपता के कारण, जब शाब्दिक को सत्य पर सेट किया जाता है, तो निहितार्थों की श्रृंखला के माध्यम से इससे प्राप्त होने वाले सभी शाब्दिक पहले से ही सत्य पर सेट हो चुके होंगे। सममित रूप से, जब शाब्दिक x को गलत पर सेट किया गया है, सभी शाब्दिक अर्थ जो निहितार्थों की श्रृंखला के माध्यम से इसकी ओर ले जाते हैं वे स्वयं पहले से ही गलत पर सेट हो चुके होंगे। इसलिए, इस प्रक्रिया द्वारा निर्मित सत्य असाइनमेंट दिए गए सूत्र को संतुष्ट करता है, जो एस्पवॉल एट अल द्वारा पहचानी गई आवश्यक और पर्याप्त स्थिति की शुद्धता का प्रमाण भी पूरा करता है।[4]
एस्पवॉल एट अल के रूप में। दिखाएँ, निहितार्थ ग्राफ़ के दृढ़ता से जुड़े अवयवों को टोपोलॉजिकल रूप से क्रमबद्ध करने वाली समान प्रक्रिया का उपयोग सही मात्राबद्ध बूलियन सूत्र का मूल्यांकन करने के लिए भी किया जा सकता है जिसमें मात्रा निर्धारित किया जा रहा सूत्र 2-सीएनएफ सूत्र है।[4]
अनुप्रयोग
ज्यामितीय वस्तुओं का संघर्ष-मुक्त स्थान
स्वचालित लेबल प्लेसमेंट समस्या के लिए अनेक सटीक और अनुमानित एल्गोरिदम 2-संतुष्टि पर आधारित हैं। यह समस्या किसी आरेख या मानचित्र की विशेषताओं पर पाठ्य लेबल लगाने से संबंधित है। सामान्यतः , प्रत्येक लेबल के लिए संभावित स्थानों का सेट अत्यधिक प्रतिबंधित होता है, न केवल मानचित्र द्वारा (प्रत्येक लेबल को उस सुविधा के पास होना चाहिए जिसे वह लेबल करता है, और अन्य सुविधाओं को अस्पष्ट नहीं करना चाहिए), किन्तु एक-दूसरे द्वारा: प्रत्येक दो लेबल को एक-दूसरे को ओवरलैप करने से बचना चाहिए, अन्यथा वे अस्पष्ट हो जाएंगे। सामान्य तौर पर, इन बाधाओं का पालन करने वाला लेबल प्लेसमेंट ढूंढना एनपी कठिन समस्या है। चूँकि , यदि प्रत्येक फीवेरिएबल में उसके लेबल के लिए केवल दो संभावित स्थान हैं (जैसे, फीवेरिएबल के बाईं और दाईं ओर विस्तार) तो लेबल प्लेसमेंट को बहुपद समय में हल किया जा सकता है। इस मामले में, कोई 2-संतोषजनक उदाहरण बना सकता है जिसमें प्रत्येक लेबल के लिए वेरिएबल होता है और जिसमें लेबल की प्रत्येक जोड़ी के लिए खंड होता है जो ओवरलैप हो सकता है, जिससे उन्हें ओवरलैपिंग स्थिति आवंटित करने से रोका जा सकता है। यदि लेबल सभी सर्वांगसम आयत हैं, तो संबंधित 2-संतुष्टि उदाहरण को केवल रैखिक रूप से अनेक बाधाओं के रूप में दिखाया जा सकता है, जिससे लेबलिंग खोजने के लिए निकट-रेखीय समय एल्गोरिदम हो सकता है।[10] पून, झू & चिन (1998) मानचित्र लेबलिंग समस्या का वर्णन करें जिसमें प्रत्येक लेबल आयत है जिसे लेबल किए गए रेखा खंड के संबंध में तीन स्थितियों में से में रखा जा सकता है: इसमें खंड इसके किनारों में से के रूप में हो सकता है, या यह खंड पर केंद्रित हो सकता है। वे दो बाइनरी वेरिएबल का उपयोग करके इन तीन स्थितियों का प्रतिनिधित्व इस तरह से करते हैं कि, फिर से, वैध लेबलिंग के अस्तित्व का परीक्षण करना 2-संतुष्टि समस्या बन जाता है।[11]
फॉर्मैन & वैगनर (1991) किसी दिए गए बिंदुओं के सेट के लिए सबसे बड़े संभावित आकार के वर्ग लेबल खोजने की समस्या के लिए सन्निकटन एल्गोरिदम के भाग के रूप में 2-संतुष्टि का उपयोग करें, इस बाधा के साथ कि प्रत्येक लेबल का कोना उस बिंदु पर हो जिस बिंदु पर वह लेबल करता है। किसी दिए गए आकार के साथ लेबलिंग खोजने के लिए, वे उन वर्गों को हटा देते हैं, जिन्हें यदि दोगुना किया जाए, तो वे दूसरे बिंदु को ओवरलैप कर देंगे, और वे उन बिंदुओं को हटा देते हैं, जिन्हें इस तरह से लेबल किया जा सकता है कि संभवतः किसी अन्य बिंदु के लेबल के साथ ओवरलैप नहीं किया जा सकता है। वे दिखाते हैं कि इन उन्मूलन नियमों के कारण शेष बिंदुओं पर प्रति बिंदु केवल दो संभावित लेबल प्लेसमेंट होते हैं, जिससे 2-संतुष्टि उदाहरण के समाधान के रूप में वैध लेबल प्लेसमेंट (यदि कोई मौजूद है) पाया जा सकता है। सबसे बड़े लेबल आकार की खोज करके जो हल करने योग्य 2-संतोषजनक उदाहरण की ओर ले जाता है, उन्हें वैध लेबल प्लेसमेंट मिलता है जिसके लेबल इष्टतम समाधान से कम से कम आधे बड़े होते हैं। अर्थात्, उनके एल्गोरिथ्म का सन्निकटन अनुपात अधिकतम दो है।[10][12] इसी तरह, यदि प्रत्येक लेबल आयताकार है और उसे इस तरह से रखा जाना चाहिए कि जिस बिंदु पर वह लेबल करता है वह उसके निचले किनारे के साथ कहीं है, तो सबसे बड़े लेबल आकार को खोजने के लिए 2-संतुष्टि का उपयोग करें जिसके लिए समाधान है जिसमें प्रत्येक लेबल के निचले कोने पर बिंदु होता है जिससे अधिकतम दो का अनुमान अनुपात होता है।[13]
अन्य ज्यामितीय प्लेसमेंट समस्याओं के लिए 2-संतुष्टि के समान अनुप्रयोग किए गए हैं। ग्राफ ड्राइंग में, यदि शीर्ष स्थान तय किए गए हैं और प्रत्येक किनारे को दो संभावित स्थानों में से के साथ गोलाकार चाप के रूप में खींचा जाना चाहिए (उदाहरण के लिए आर्क आरेख के रूप में), तो क्रॉसिंग से बचने के लिए प्रत्येक किनारे के लिए कौन सा चाप का उपयोग करना है यह चुनने की समस्या प्रत्येक किनारे के लिए वेरिएबल के साथ 2-संतुष्टि की समस्या है और प्लेसमेंट की प्रत्येक जोड़ी के लिए बाधा है जो क्रॉसिंग की ओर ले जाएगी। चूँकि , इस मामले में समाधान को गति देना संभव है, एल्गोरिदम की तुलना में जो ग्राफ़ के अंतर्निहित ग्राफ़ को खोजकर, निहितार्थ ग्राफ़ का स्पष्ट प्रतिनिधित्व बनाता है और फिर खोजता है।[14] वीएलएसआई एकीकृत परिपथ डिजाइन में, यदि मॉड्यूल का संग्रह तारों से जुड़ा होना चाहिए जो प्रत्येक अधिकतम बार झुक सकता है, तो तारों के लिए फिर से दो संभावित मार्ग हैं, और इन दो मार्गों में से कौन सा उपयोग करना है, यह चुनने की समस्या, इस तरह से कि सभी तारों को परिपथ की परत में रूट किया जा सकता है, को 2-संतुष्टि उदाहरण के रूप में हल किया जा सकता है।[15]
बोरोस et al. (1999) अन्य वीएलएसआई डिज़ाइन समस्या पर विचार करें: परिपथ डिज़ाइन में प्रत्येक मॉड्यूल को मिरर-रिवर्स करना है या नहीं, इसका प्रश्न। यह मिरर रिवर्सल मॉड्यूल के संचालन को अपरिवर्तित छोड़ देता है, किन्तु यह उन बिंदुओं के क्रम को बदल देता है जिन पर मॉड्यूल के इनपुट और आउटपुट सिग्नल इससे जुड़ते हैं, संभवतः यह बदल जाता है कि मॉड्यूल बाकी डिज़ाइन में कितनी अच्छी तरह फिट बैठता है। बोरोस एट अल. समस्या के सरलीकृत संस्करण पर विचार करें जिसमें मॉड्यूल पहले से ही ही रैखिक चैनल के साथ रखे गए हैं, जिसमें मॉड्यूल के बीच तारों को रूट किया जाना चाहिए, और चैनल के घनत्व पर निश्चित सीमा होती है (सिग्नलों की अधिकतम संख्या जो चैनल के किसी भी क्रॉस-सेक्शन से गुज़रनी चाहिए)। उनका मानना है कि समस्या के इस संस्करण को 2-संतुष्टि उदाहरण के रूप में हल किया जा सकता है, जिसमें बाधाएं मॉड्यूल के जोड़े के उन्मुखीकरण से संबंधित हैं जो सीधे दूसरे से चैनल के पार हैं। परिणामस्वरूप, बाइनरी खोज करके इष्टतम घनत्व की गणना भी कुशलतापूर्वक की जा सकती है, जिसमें प्रत्येक चरण में 2-संतुष्टि उदाहरण का समाधान सम्मिलित होता है।[16]
डेटा क्लस्टरिंग
एक मीट्रिक स्थान में डेटा को दो समूहों में क्लस्टर करने का विधि क्लस्टर को इस तरह से चुनना है जिससे क्लस्टर के व्यास के योग को कम किया जा सके, जहां किसी एकल क्लस्टर का व्यास उसके किन्हीं दो बिंदुओं के बीच की सबसे बड़ी दूरी है। यह अधिकतम क्लस्टर आकार को कम करने के लिए बेहतर है, जिससे विभिन्न समूहों को बहुत समान अंक आवंटित किए जा सकते हैं। यदि दो समूहों के लक्ष्य व्यास ज्ञात हैं, तो 2-संतुष्टि उदाहरण को हल करके उन लक्ष्यों को प्राप्त करने वाली क्लस्टरिंग पाई जा सकती है। उदाहरण में प्रति बिंदु वेरिएबल है, जो दर्शाता है कि वह बिंदु पहले क्लस्टर से संबंधित है या दूसरे क्लस्टर से। जब भी कोई दो बिंदु दूसरे से इतने दूर होते हैं कि दोनों ही क्लस्टर से संबंधित नहीं होते हैं, तो उदाहरण में खंड जोड़ा जाता है जो इस असाइनमेंट को रोकता है।
जब व्यक्तिगत क्लस्टर व्यास अज्ञात हों तो उसी विधि का उपयोग सबरूटीन के रूप में भी किया जा सकता है। यह जांचने के लिए कि क्या व्यास का दिया गया योग अलग-अलग क्लस्टर व्यास को जाने बिना प्राप्त किया जा सकता है, कोई लक्ष्य व्यास के सभी अधिकतम जोड़े का प्रयास कर सकता है जो अधिकतम दिए गए योग को जोड़ता है, व्यास की प्रत्येक जोड़ी को 2-संतुष्टिशीलता उदाहरण के रूप में दर्शाता है और यह निर्धारित करने के लिए 2-संतोषजनक एल्गोरिदम का उपयोग करता है कि क्या उस जोड़ी को क्लस्टरिंग द्वारा महसूस किया जा सकता है। व्यासों का इष्टतम योग ज्ञात करने के लिए कोई बाइनरी खोज कर सकता है जिसमें प्रत्येक चरण इस प्रकार का व्यवहार्यता परीक्षण होता है। यही दृष्टिकोण क्लस्टरिंग को खोजने के लिए भी कार्य करता है जो क्लस्टर व्यास के योग के अलावा अन्य संयोजनों को अनुकूलित करता है, और जो क्लस्टर के आकार को मापने के लिए मनमाने ढंग से असमानता संख्याओं (मीट्रिक स्थान में दूरी के अतिरिक्त ) का उपयोग करता है।[17] इस एल्गोरिथम के लिए समय सीमा 2-संतोषजनक उदाहरणों के अनुक्रम को हल करने के समय पर हावी है जो एक-दूसरे से निकटता से संबंधित हैं, और रामनाथ (2004) दिखाता है कि इन संबंधित उदाहरणों को एक-दूसरे से स्वतंत्र रूप से हल करने की तुलना में अधिक तेज़ी से कैसे हल किया जाए, जिससे कुल समय सीमा तय हो सके O(n3)व्यास के योग की क्लस्टरिंग समस्या के लिए।[18]
शेड्यूलिंग
इवेन, इटाई & शमीर (1976) कक्षा समय-निर्धारण के मॉडल पर विचार करें जिसमें छात्रों के प्रत्येक समूह को पढ़ाने के लिए n शिक्षकों का समूह निर्धारित किया जाना चाहिए। उस शिक्षक के प्रति सप्ताह घंटों की संख्या समूह के साथ बिताता है प्रविष्टि द्वारा वर्णित है मैट्रिक्स का समस्या के इनपुट के रूप में दिया गया है, और प्रत्येक शिक्षक के पास घंटों का सेट भी है जिसके दौरान वह शेड्यूल के लिए उपलब्ध रहता है। जैसा कि वे दिखाते हैं, समस्या एनपी-पूर्ण है, भले ही प्रत्येक शिक्षक के पास अधिकतम तीन उपलब्ध घंटे हों, किन्तु इसे 2-संतुष्टि के उदाहरण के रूप में हल किया जा सकता है जब प्रत्येक शिक्षक के पास केवल दो उपलब्ध घंटे हों। (केवल उपलब्ध घंटे वाले शिक्षकों को समस्या से आसानी से छुटकारा दिलाया जा सकता है।) इस समस्या में, प्रत्येक वेरिएबल उस शिक्षक के घंटे से मेल खाता है समूह के साथ बिताना चाहिए , वेरिएबल के लिए असाइनमेंट निर्दिष्ट करता है कि क्या वह घंटा शिक्षक के उपलब्ध घंटों में से पहला या दूसरा है, और 2-संतुष्टि खंड है जो दो प्रकार के किसी भी टकराव को रोकता है: शिक्षक को ही समय में एक-दूसरे को सौंपे गए दो समूह, या ही समय में दो शिक्षकों को सौंपा गया समूह।[5]
मियाशिरो & मत्सुई (2005) खेल शेड्यूलिंग की समस्या के लिए 2-संतुष्टि प्रयुक्त करें, जिसमें राउंड-रॉबिन टूर्नामेंट की जोड़ियों को पहले ही चुना जा चुका है और खेलों को टीमों के स्टेडियमों को सौंपा जाना चाहिए। इस समस्या में, जहां तक संभव हो घर और बाहर के खेलों को वैकल्पिक करना वांछनीय है, ब्रेक से बचना चाहिए जिसमें टीम पंक्ति में दो घरेलू खेल खेलती है या पंक्ति में दो दूर खेल खेलती है। अधिक से अधिक दो टीमें घर और बाहर के खेलों के बीच बारी-बारी से ब्रेक से पूरी तरह बच सकती हैं; किसी अन्य टीम का होम-अवे शेड्यूल इन दोनों के समान नहीं हो सकता, क्योंकि तब वह उस टीम के साथ खेलने में असमर्थ होगी जिसके साथ उसका शेड्यूल समान था। इसलिए, इष्टतम शेड्यूल में दो ब्रेकलेस टीमें होती हैं और हर दूसरी टीम के लिए ब्रेक होता है। बार जब ब्रेकलेस टीमों में से को चुना जाता है, तो कोई 2-संतुष्टि की समस्या खड़ी कर सकता है, जिसमें प्रत्येक वेरिएबल ही गेम में ही टीम के लिए होम-अवे असाइनमेंट का प्रतिनिधित्व करता है, और बाधाएं उन गुणों को प्रयुक्त करती हैं कि किन्हीं दो टीमों के पास अपने गेम के लिए सुसंगत असाइनमेंट होता है, प्रत्येक टीम के पास ब्रेकलेस टीम के साथ खेल से पहले अधिकतम ब्रेक और गेम के पश्चात अधिकतम ब्रेक होता है, और किसी भी टीम के पास दो ब्रेक नहीं होते हैं। इसलिए, यह परीक्षण करना कि क्या कोई शेड्यूल इष्टतम संख्या में ब्रेक के साथ समाधान स्वीकार करता है, ब्रेकलेस टीम की प्रत्येक पसंद के लिए 2-संतुष्टि समस्याओं की रैखिक संख्या को हल करके किया जा सकता है। समान तकनीक ऐसे शेड्यूल खोजने की भी अनुमति देती है जिसमें प्रत्येक टीम के पास ही ब्रेक होता है, और ब्रेक की संख्या को कम करने के अतिरिक्त अधिकतम करने की अनुमति देता है (टीमों द्वारा यात्रा की गई कुल माइलेज को कम करने के लिए)।[19]
असतत टोमोग्राफी
टोमोग्राफी उनके क्रॉस-सेक्शन से आकृतियों को पुनर्प्राप्त करने की प्रक्रिया है। असतत टोमोग्राफी में, समस्या का सरलीकृत संस्करण जिसका अक्सर अध्ययन किया गया है, पुनर्प्राप्त किया जाने वाला आकार पॉलीओमिनो (द्वि-आयामी वर्ग जाली में वर्गों का उपसमूह) है, और क्रॉस-सेक्शन जाली की व्यक्तिगत पंक्तियों और स्तंभों में वर्गों के सेट के बारे में समग्र जानकारी प्रदान करते हैं। उदाहरण के लिए, लोकप्रिय पहेलियाँ खेलना पहेलियों में, जिन्हें संख्याओं या ग्रिडलर द्वारा पेंट के रूप में भी जाना जाता है, निर्धारित किए जाने वाले वर्गों का सेट बाइनरी छवि में डार्क पिक्सेल का प्रतिनिधित्व करता है, और पहेली सॉल्वर को दिया गया इनपुट उसे बताता है कि छवि की प्रत्येक पंक्ति या कॉलम में डार्क पिक्सल के कितने लगातार ब्लॉक सम्मिलित करने हैं, और उनमें से प्रत्येक ब्लॉक कितना लंबा होना चाहिए। डिजिटल टोमोग्राफी के अन्य रूपों में, प्रत्येक पंक्ति या स्तंभ के बारे में और भी कम जानकारी दी जाती है: वर्गों के ब्लॉक की संख्या और लंबाई के अतिरिक्त केवल वर्गों की कुल संख्या। समस्या का समतुल्य संस्करण यह है कि हमें मैट्रिक्स की प्रत्येक पंक्ति और प्रत्येक कॉलम में केवल मानों के योग को देखते हुए दिए गए 0-1 मैट्रिक्स को पुनर्प्राप्त करना होगा।
यद्यपि पंक्ति और स्तंभ के योग वाले मैट्रिक्स को खोजने के लिए बहुपद समय एल्गोरिदम मौजूद हैं,[20] समाधान अद्वितीय से बहुत दूर हो सकता है: 2 × 2 पहचान मैट्रिक्स के रूप में किसी भी सबमैट्रिक्स को समाधान की शुद्धता को प्रभावित किए बिना पूरक किया जा सकता है। इसलिए, शोधकर्ताओं ने पुनर्निर्माण किए जाने वाले आकार पर बाधाओं की खोज की है जिसका उपयोग समाधानों के स्थान को प्रतिबंधित करने के लिए किया जा सकता है। उदाहरण के लिए, कोई यह मान सकता है कि आकृति जुड़ी हुई है; चूँकि , यह परीक्षण करना कि क्या कोई कनेक्टेड समाधान मौजूद है, एनपी-पूर्ण है।[21] और अधिक सीमित संस्करण जिसे हल करना आसान है वह यह है कि आकार ऑर्थोगोनल उत्तलता है: प्रत्येक पंक्ति और स्तंभ में वर्गों का एकल सन्निहित ब्लॉक होता है। पिछले अनेक समाधानों में सुधार, क्रोबक & Dürr (1999) ने दिखाया कि 2-एसएटी का उपयोग करके कनेक्टेड ऑर्थोगोनली उत्तल आकृतियों को कुशलतापूर्वक कैसे पुनर्निर्माण किया जाए।[22] उनके समाधान का विचार पुनर्निर्माण की जाने वाली आकृति की सबसे बाईं और दाईं ओर की कोशिकाओं वाली पंक्तियों के सूचकांक का अनुमान लगाना है, और फिर 2-संतुष्टि समस्या स्थापित करना है जो परीक्षण करता है कि क्या इन अनुमानों और दी गई पंक्ति और स्तंभ योगों के अनुरूप कोई आकृति मौजूद है। वे प्रत्येक वर्ग के लिए चार 2-संतुष्टि वेरिएबल का उपयोग करते हैं जो दिए गए आकार का हिस्सा हो सकते हैं, यह इंगित करने के लिए कि क्या यह आकृति के चार संभावित कोने क्षेत्रों में से प्रत्येक से संबंधित है, और वे उन बाधाओं का उपयोग करते हैं जो इन क्षेत्रों को असंयुक्त होने के लिए मजबूर करते हैं, वांछित आकार प्राप्त करने के लिए, सन्निहित पंक्तियों और स्तंभों के साथ समग्र आकार बनाने के लिए, और वांछित पंक्ति और स्तंभ योग प्राप्त करने के लिए। उनके एल्गोरिदम में समय लगता है O(m3n) जहाँ m इनपुट आकार के दो आयामों में से छोटा है और n दो आयामों में से बड़ा है। उसी पद्धति को पश्चात में ऑर्थोगोनल रूप से उत्तल आकृतियों तक विस्तारित किया गया, जिन्हें ऑर्थोगोनल कनेक्टिविटी की आवश्यकता के अतिरिक्त केवल तिरछे रूप से जोड़ा जा सकता है।[23] पूर्ण नॉनोग्राम पहेलियों के लिए सॉल्वर का भाग, (बटेनबर्ग & कोस्टर्स 2008, 2009) अनेक अन्य अनुमानों से प्राप्त जानकारी को संयोजित करने के लिए 2-संतोषजनकता का उपयोग किया गया। पहेली के आंशिक समाधान को देखते हुए, वे यह निर्धारित करने के लिए प्रत्येक पंक्ति या स्तंभ के भीतर गतिशील प्रोग्रामिंग का उपयोग करते हैं कि क्या उस पंक्ति या स्तंभ की बाधाएं उसके किसी भी वर्ग को सफेद या काला होने के लिए मजबूर करती हैं, और क्या ही पंक्ति या स्तंभ में किसी भी दो वर्गों को निहितार्थ संबंध द्वारा जोड़ा जा सकता है। वे प्रत्येक पंक्ति और स्तंभ में ब्लॉक लंबाई के अनुक्रम को उसके योग से प्रतिस्थापित करके नॉनोग्राम को डिजिटल टोमोग्राफी समस्या में बदल देते हैं, और यह निर्धारित करने के लिए अधिकतम प्रवाह फॉर्मूलेशन का उपयोग करते हैं कि क्या सभी पंक्तियों और स्तंभों को संयोजित करने वाली इस डिजिटल टोमोग्राफी समस्या में कोई वर्ग है जिसकी स्थिति निर्धारित की जा सकती है या वर्गों के जोड़े हैं जिन्हें निहितार्थ संबंध द्वारा जोड़ा जा सकता है। यदि इन दोनों अनुमानों में से कोई वर्ग का मान निर्धारित करता है, तो इसे आंशिक समाधान में सम्मिलित किया जाता है और वही गणना दोहराई जाती है। चूँकि , यदि दोनों अनुमान किसी भी वर्ग को निर्धारित करने में विफल रहते हैं, तो उन दोनों द्वारा पाए गए निहितार्थों को 2-संतुष्टिशीलता समस्या में जोड़ दिया जाता है और उन वर्गों को खोजने के लिए 2-संतुष्टिकारक सॉल्वर का उपयोग किया जाता है जिनका मान समस्या द्वारा तय किया जाता है, जिसके पश्चात प्रक्रिया फिर से दोहराई जाती है। यह प्रक्रिया समाधान ढूंढने में सफल हो भी सकती है और नहीं भी, किन्तु इसके बहुपद समय में चलने की गारंटी है। बटेनबर्ग और कोस्टर्स की रिपोर्ट है कि, हालांकि अधिकांश अखबार पहेलियों को इसकी पूरी शक्ति की आवश्यकता नहीं है, यह प्रक्रिया और अधिक शक्तिशाली किन्तु धीमी प्रक्रिया है जो इस 2-संतुष्टि दृष्टिकोण को सीमित बैकट्रैकिंग के साथ जोड़ती है। इवेन, इटाई & शमीर (1976)[5] अधिक कठिन बेतरतीब ढंग से उत्पन्न नॉनोग्राम पर प्रयुक्त होने पर 2-संतुष्टि के बिना गतिशील प्रोग्रामिंग और प्रवाह अनुमान की तुलना में अधिक अधिक प्रभावी होते हैं।[24]
नाम बदलने योग्य हॉर्न संतुष्टि
2-संतुष्टि के पश्चात, संतुष्टि समस्याओं का दूसरा प्रमुख उपवर्ग जिसे बहुपद समय में हल किया जा सकता है, हॉर्न-संतुष्टि है। संतुष्टि समस्याओं के इस वर्ग में, इनपुट फिर से संयोजक सामान्य रूप में सूत्र है। इसमें प्रत्येक खंड में मनमाने ढंग से अनेक अक्षर हो सकते हैं किन्तु अधिकतम सकारात्मक अक्षर हो सकता है। लेविस (1978) इस वर्ग का सामान्यीकरण पाया गया, नाम बदलने योग्य हॉर्न संतुष्टि, जिसे अभी भी सहायक 2-संतोषजनक उदाहरण के माध्यम से बहुपद समय में हल किया जा सकता है। सूत्र को हॉर्न नाम दिया जा सकता है जब कुछ वेरिएबलों को उनके निषेधों द्वारा प्रतिस्थापित करके इसे हॉर्न रूप में रखना संभव हो। ऐसा करने के लिए, लुईस नाम बदलने योग्य हॉर्न उदाहरण के प्रत्येक वेरिएबल के लिए वेरिएबल के साथ 2-संतोषजनक उदाहरण स्थापित करता है, जहां 2-संतोषजनक वेरिएबल इंगित करते हैं कि संबंधित नाम बदलने योग्य हॉर्न वेरिएबल को नकारना है या नहीं। हॉर्न उदाहरण तैयार करने के लिए, नाम बदलने योग्य हॉर्न उदाहरण के ही खंड में दिखाई देने वाले कोई भी दो वेरिएबल उस खंड में सकारात्मक रूप से प्रकट नहीं होने चाहिए; वेरिएबलों की जोड़ी पर यह बाधा 2-संतोषजनक बाधा है। परिणामी 2-संतोषजनक उदाहरण के लिए संतोषजनक असाइनमेंट ढूंढकर, लुईस दिखाता है कि बहुपद समय में किसी भी नाम बदलने योग्य हॉर्न उदाहरण को हॉर्न उदाहरण में कैसे बदला जाए।[25] लंबे खंडों को अनेक छोटे खंडों में तोड़कर, और रैखिक-समय 2-संतुष्टि एल्गोरिथ्म को प्रयुक्त करके, इसे रैखिक समय तक कम करना संभव है।[26]
अन्य अनुप्रयोग
2-संतुष्टि को अप्रत्यक्ष ग्राफ़ को पहचानने की समस्याओं पर भी प्रयुक्त किया गया है जिन्हें स्वतंत्र सेट (ग्राफ़ सिद्धांत) और पूर्ण द्विदलीय ग्राफ़ की छोटी संख्या में विभाजित किया जा सकता है,[27] इंटरनेट के स्वायत्त उपप्रणालियों के बीच व्यावसायिक संबंधों का अनुमान लगाना,[28] और विकासवादी पेड़ों का पुनर्निर्माण।[29]
सम्मिश्र ता और विस्तार
एनएल-पूर्णता
यह निर्धारित करने के लिए गैर-नियतात्मक एल्गोरिथ्म कि क्या 2-संतोषजनक उदाहरण संतोषजनक नहीं है, केवल लिखने योग्य मेमोरी की लघुगणकीय मात्रा का उपयोग करके वर्णन करना आसान है: बस (नॉन-नियतात्मक रूप से) वेरिएबल v चुनें और v से उसके निषेध तक और फिर वापस v तक जाने वाले निहितार्थों की श्रृंखला के लिए (नॉन-नियतात्मक रूप से) खोजें। यदि ऐसी कोई श्रृंखला पाई जाती है, तो उदाहरण संतोषजनक नहीं हो सकता है। इमरमैन-स्ज़ेलेपेसेनी प्रमेय के अनुसार, गैर-नियतात्मक लॉगस्पेस में यह सत्यापित करना भी संभव है कि संतोषजनक 2-संतोषजनक उदाहरण संतोषजनक है।
2-संतुष्टि एनएल-पूर्ण है,[30] इसका अर्थ यह है कि यह लघुगणकीय स्थान में गैर-नियतात्मक रूप से हल करने योग्य समस्याओं की सम्मिश्र ता वर्ग एनएल (सम्मिश्र ता) में सबसे कठिन या सबसे अभिव्यंजक समस्याओं में से है। यहां पूर्णता का मतलब है कि केवल लॉगरिदमिक स्थान का उपयोग करने वाली नियतात्मक ट्यूरिंग मशीन एनएल में किसी भी अन्य समस्या को समकक्ष 2-संतुष्टि समस्या में बदल सकती है। अधिक सुप्रसिद्ध सम्मिश्र ता वर्ग एनपी (सम्मिश्र ता) के लिए समान परिणामों के अनुरूप, यह परिवर्तन इमरमैन-स्ज़ेलेपीसीसेनी प्रमेय के साथ मिलकर एनएल में किसी भी समस्या को दूसरे क्रम के तर्क सूत्र के रूप में प्रस्तुत करने की अनुमति देता है, जिसमें लंबाई 2 तक सीमित खंडों के साथ एकल अस्तित्वगत रूप से परिमाणित विधेय होता है। ऐसे सूत्रों को एसओ-क्रोम के रूप में जाना जाता है।[31] इसी प्रकार, अंतर्निहित सामान्य रूप को ट्रांजिटिव क्लोजर के लिए ऑपरेटर के अतिरिक्त के साथ प्रथम क्रम तर्क में व्यक्त किया जा सकता है।[31]
सभी समाधानों का समुच्चय
2-संतुष्टि उदाहरण के सभी समाधानों के सेट में माध्यिका ग्राफ की संरचना होती है, जिसमें किनारा वेरिएबल के सेट के मूल्यों को फ़्लिप करने के संचालन से मेल खाता है जो सभी दूसरे के समान या असमान होने के लिए बाध्य हैं। विशेष रूप से, इस तरह से किनारों का अनुसरण करके कोई भी किसी भी समाधान से किसी अन्य समाधान तक पहुंच सकता है। इसके विपरीत, किसी भी माध्य ग्राफ को इस तरह से 2-संतुष्टि उदाहरण के समाधान के सेट के रूप में दर्शाया जा सकता है। किन्हीं तीन समाधानों का माध्य प्रत्येक वेरिएबल को तीन समाधानों के बहुमत फलन में रखे गए मान पर सेट करके बनाया जाता है। यह माध्यिका हमेशा उदाहरण के लिए और समाधान बनाती है।[32]
फेडर (1994) किसी दिए गए 2-संतुष्टि उदाहरण के सभी समाधानों को कुशलतापूर्वक सूचीबद्ध करने और अनेक संबंधित समस्याओं को हल करने के लिए एल्गोरिदम का वर्णन करता है।[33]
दो संतोषजनक असाइनमेंट खोजने के लिए एल्गोरिदम भी मौजूद हैं जिनकी दूसरे से अधिकतम हैमिंग दूरी है।[34]
संतोषजनक असाइनमेंट की संख्या की गिनती
- 2एसएटी किसी दिए गए 2-सीएनएफ सूत्र में संतोषजनक असाइनमेंट की संख्या की गणना करने की समस्या है। यह गिनती समस्या (सम्मिश्र ता) तीव्र-पी-पूर्ण|#पी-पूर्ण है,[35] जिसका तात्पर्य यह है कि यह बहुपद समय में हल करने योग्य नहीं है जब तक कि P बनाम NP समस्या न हो|P = NP। इसके अलावा, #2एसएटी के लिए कोई बहुपद-समय सन्निकटन योजना नहीं है जब तक कि एनपी (सम्मिश्र ता) = आरपी (सम्मिश्र ता) न हो और यह तब भी प्रयुक्त होता है जब इनपुट मोनोटोन 2-सीएनएफ सूत्रों तक सीमित होता है, यानी, 2-सीएनएफ सूत्र जिसमें प्रत्येक शाब्दिक (गणितीय तर्क) वेरिएबल की सकारात्मक घटना होती है।[36]
2एसएटी फ़ॉर्मूले के लिए संतोषजनक असाइनमेंट की सटीक संख्या की गणना करने के लिए सबसे तेज़ ज्ञात एल्गोरिदम समय में चलता है .[37] [38] [39]
यादृच्छिक 2-संतोषजनक उदाहरण
सभी संभावित दो-वेरिएबल खंडों के सेट से यादृच्छिक रूप से प्रत्येक खंड को समान रूप से चुनकर, किसी दिए गए वेरिएबल की संख्या n और खंडों के m के लिए, यादृच्छिक रूप से 2-संतोषजनक उदाहरण बनाया जा सकता है। जब m, n के सापेक्ष छोटा होता है, तो ऐसा उदाहरण संभवतः संतोषजनक होगा, किन्तु m के बड़े मानों के संतोषजनक होने की संभावनाएँ कम होती हैं। अधिक सटीक रूप से, यदि m/n को स्थिर α ≠ 1 के रूप में तय किया गया है, तो संतुष्टि की संभावना अनुक्रम की सीमा की ओर बढ़ जाती है क्योंकि n अनंत तक जाता है: यदि α < 1, सीमा है, जबकि यदि α > 1, सीमा शून्य है। इस प्रकार, समस्या α = 1 पर चरण संक्रमण प्रदर्शित करती है।[40]
अधिकतम-2-संतुष्टि
अधिकतम-2-संतुष्टि समस्या (MAX-2-एसएटी) में, इनपुट प्रति खंड दो शाब्दिक (गणितीय तर्क) के साथ संयोजक सामान्य रूप में सूत्र है, और कार्य उन खंडों की अधिकतम संख्या निर्धारित करना है जिन्हें असाइनमेंट द्वारा साथ संतुष्ट किया जा सकता है। अधिक सामान्य अधिकतम संतुष्टि समस्या की तरह, MAX-2-एसएटी NP-हार्ड है। इसका प्रमाण बूलियन संतुष्टि समस्या से कमी है।[41] एक कट (ग्राफ सिद्धांत) खोजने की समस्या के रूप में मैक्स -2-सैट को तैयार करके (यानी, दो सबसेट में वर्टिस का विभाजन) उन किनारों की संख्या को अधिकतम करता है जो पहले सबसेट में एंडपॉइंट और दूसरे में एंडपॉइंट में एंडपॉइंट, निहितार्थ ग्राफ से संबंधित ग्राफ में ग्राफ को पूरा करने के लिए, जो कि कम से कम है। ।[42] संतुलित MAX 2-एसएटी उदाहरण MAX 2-एसएटी का उदाहरण है जहां प्रत्येक वेरिएबल समान भार के साथ सकारात्मक और ऋणात्मक रूप से प्रकट होता है। इस समस्या के लिए, ऑस्ट्रिन ने सन्निकटन अनुपात में सुधार किया है .[43] यदि अद्वितीय गेम का अनुमान सत्य है, तो बहुपद समय में 0.943... से बेहतर अनुमानित अनुपात के साथ, MAX 2-एसएटी का अनुमान लगाना असंभव है, चाहे वह संतुलित हो या नहीं।[44] कमजोर धारणा के तहत कि पी बनाम एनपी समस्या | पी ≠ एनपी, समस्या को केवल 21/22 = 0.95454 से बेहतर स्थिरांक के भीतर अनुपयुक्त माना जाता है...[45] विभिन्न लेखकों ने MAX-2-एसएटी उदाहरणों के सटीक समाधान के लिए घातीय सबसे खराब समय सीमा का भी पता लगाया है।[46]
भारित-2-संतुष्टि
भारित 2-संतुष्टि समस्या (W2एसएटी) में, इनपुट है -परिवर्तनीय 2एसएटी उदाहरण और पूर्णांक k, और समस्या यह तय करना है कि वास्तव में कोई संतोषजनक असाइनमेंट मौजूद है या नहीं k वेरिएबल सत्य हैं।[47]
W2एसएटी समस्या में विशेष मामले के रूप में सेट खोजने की वर्टेक्स कवर समस्या सम्मिलित है k शीर्ष जो किसी दिए गए अप्रत्यक्ष ग्राफ़ के सभी किनारों को साथ छूते हैं। शीर्ष कवर समस्या के किसी भी उदाहरण के लिए, कोई ग्राफ़ के प्रत्येक शीर्ष के लिए वेरिएबल के साथ समतुल्य W2एसएटी समस्या का निर्माण कर सकता है। प्रत्येक किनारा {{math|uv}ग्राफ़ के } को 2एसएटी खंड द्वारा दर्शाया जा सकता है u ∨ v जिसे दोनों में से किसी को सम्मिलित करके ही संतुष्ट किया जा सकता है u या v समाधान के वास्तविक वेरिएबलों के बीच। फिर परिणामी 2एसएटी सूत्र के संतोषजनक उदाहरण वर्टेक्स कवर समस्या के समाधान को एन्कोड करते हैं, और इसके साथ संतोषजनक असाइनमेंट होता है k सत्य वेरिएबल यदि और केवल यदि कोई शीर्ष आवरण है k शिखर. इसलिए, वर्टेक्स कवर की तरह, W2एसएटी NP-पूर्ण है।
इसके अलावा, पैरामीटरयुक्त सम्मिश्र ता में W2एसएटी प्राकृतिक W(1)|W[1]-पूर्ण समस्या प्रदान करता है,[47] जिसका तात्पर्य यह है कि W2एसएटी निश्चित-पैरामीटर ट्रैक्टेबल नहीं है जब तक कि यह W(1)|W[1] में सभी समस्याओं के लिए मान्य न हो। अर्थात्, यह संभावना नहीं है कि W2एसएटी के लिए कोई एल्गोरिदम मौजूद है जिसका रनिंग टाइम रूप लेता है f(k)·nO(1). इससे भी अधिक दृढ़ता से, W2एसएटी को समय पर हल नहीं किया जा सकता है no(k) जब तक कि घातीय समय परिकल्पना विफल न हो जाए।[48]
मात्राबद्ध बूलियन सूत्र
2-संतुष्टि के लिए पहला बहुपद-समय एल्गोरिदम खोजने के साथ-साथ, क्रोम (1967) ने ट्रू क्वांटिफाइड बूलियन फॉर्मूला के मूल्यांकन की समस्या भी तैयार की जिसमें क्वांटिफाई किया जा रहा फॉर्मूला 2-सीएनएफ फॉर्मूला है। 2-संतुष्टि समस्या इस परिमाणित 2-सीएनएफ समस्या का विशेष स्तिथि है, जिसमें सभी परिमाणक अस्तित्वगत परिमाणक हैं। क्रॉम ने इन सूत्रों के लिए प्रभावी निर्णय प्रक्रिया भी विकसित की। एस्पवॉल, प्लास & टारजन (1979) ने दिखाया कि इसे दृढ़ता से जुड़े अवयवों और टोपोलॉजिकल ऑर्डरिंग की उनकी तकनीक के विस्तार द्वारा, रैखिक समय में हल किया जा सकता है।[2][4]
अनेक-मूल्यवान तर्क
2-संतुष्टि समस्या को प्रस्तावित बहु-मूल्यवान तर्क के लिए भी पूछा जा सकता है। एल्गोरिदम आमतौर पर रैखिक नहीं होते हैं, और कुछ तर्कों के लिए समस्या एनपी-पूर्ण भी होती है। देखना हनले (2001, 2003) सर्वेक्षणों के लिए.[49]
संदर्भ
- ↑ 1.0 1.1 Prestwich, Steven (2009), "2. CNF Encodings", in Biere, Armin; Heule, Marijn; van Maaren, Hans; Walsh, Toby (eds.), Handbook of Satisfiability, Frontiers in Artificial Intelligence and Applications, vol. 185, IOS Press, pp. 75–98, doi:10.3233/978-1-58603-929-5-75, ISBN 978-1-58603-929-5, S2CID 31666330.
- ↑ 2.0 2.1 2.2 2.3 2.4 2.5 Krom, Melven R. (1967), "The Decision Problem for a Class of First-Order Formulas in Which all Disjunctions are Binary", Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, 13 (1–2): 15–20, doi:10.1002/malq.19670130104.
- ↑ Russell, Stuart Jonathan; Norvig, Peter (2010), Artificial Intelligence: A Modern Approach, Prentice Hall series in artificial intelligence, Prentice Hall, p. 282, ISBN 978-0-13-604259-4.
- ↑ 4.0 4.1 4.2 4.3 4.4 4.5 4.6 Aspvall, Bengt; Plass, Michael F.; Tarjan, Robert E. (1979), "A linear-time algorithm for testing the truth of certain quantified boolean formulas" (PDF), Information Processing Letters, 8 (3): 121–123, doi:10.1016/0020-0190(79)90002-4.
- ↑ 5.0 5.1 5.2 5.3 5.4 5.5 5.6 Even, S.; Itai, A.; Shamir, A. (1976), "On the complexity of time table and multi-commodity flow problems", SIAM Journal on Computing, 5 (4): 691–703, doi:10.1137/0205048.
- ↑ Cook, Stephen A. (1971), "The complexity of theorem-proving procedures", Proc. 3rd ACM Symp. Theory of Computing (STOC), pp. 151–158, doi:10.1145/800157.805047, S2CID 7573663.
- ↑ Tarjan, Robert E. (1972), "Depth-first search and linear graph algorithms", SIAM Journal on Computing, 1 (2): 146–160, doi:10.1137/0201010, S2CID 16467262.
- ↑ First published by Cheriyan, J.; Mehlhorn, K. (1996), "Algorithms for dense graphs and networks on the random access computer", Algorithmica, 15 (6): 521–549, doi:10.1007/BF01940880, S2CID 8930091. Rediscovered in 1999 by Harold N. Gabow, and published in Gabow, Harold N. (2003), "Searching (Ch 10.1)", in Gross, J. L.; Yellen, J. (eds.), Discrete Math. and its Applications: Handbook of Graph Theory, vol. 25, CRC Press, pp. 953–984.
- ↑ Harrison, Paul, Robust topological sorting and Tarjan's algorithm in Python, retrieved 9 February 2011
- ↑ 10.0 10.1 Formann, M.; Wagner, F. (1991), "A packing problem with applications to lettering of maps", Proc. 7th ACM Symposium on Computational Geometry, pp. 281–288, doi:10.1145/109648.109680, ISBN 978-0-89791-426-0, S2CID 15740667.
- ↑ Poon, Chung Keung; Zhu, Binhai; Chin, Francis (1998), "A polynomial time solution for labeling a rectilinear map", Information Processing Letters, 65 (4): 201–207, doi:10.1016/S0020-0190(98)00002-7.
- ↑ Wagner, Frank; Wolff, Alexander (1997), "A practical map labeling algorithm", Computational Geometry: Theory and Applications, 7 (5–6): 387–404, doi:10.1016/S0925-7721(96)00007-7.
- ↑ Doddi, Srinivas; Marathe, Madhav V.; Mirzaian, Andy; Moret, Bernard M. E.; Zhu, Binhai (1997), "Map labeling and its generalizations", Proc. 8th ACM-SIAM Symp. Discrete Algorithms (SODA), Soda '97, pp. 148–157, ISBN 9780898713909.
- ↑ Efrat, Alon; Erten, Cesim; Kobourov, Stephen G. (2007), "Fixed-location circular arc drawing of planar graphs" (PDF), Journal of Graph Algorithms and Applications, 11 (1): 145–164, doi:10.7155/jgaa.00140.
- ↑ Raghavan, Raghunath; Cohoon, James; Sahni, Sartaj (1986), "Single bend wiring", Journal of Algorithms, 7 (2): 232–237, doi:10.1016/0196-6774(86)90006-4.
- ↑ Boros, Endre; Hammer, Peter Ladislaw; Minoux, Michel; Rader, David J., Jr. (1999), "Optimal cell flipping to minimize channel density in VLSI design and pseudo-Boolean optimization", Discrete Applied Mathematics, 90 (1–3): 69–88, doi:10.1016/S0166-218X(98)00114-0
{{citation}}
: CS1 maint: multiple names: authors list (link). - ↑ Hansen, P.; Jaumard, B. (1987), "Minimum sum of diameters clustering", Journal of Classification, 4 (2): 215–226, doi:10.1007/BF01896987, S2CID 120583429.
- ↑ Ramnath, Sarnath (2004), "Dynamic digraph connectivity hastens minimum sum-of-diameters clustering", SIAM Journal on Discrete Mathematics, 18 (2): 272–286, doi:10.1137/S0895480102396099.
- ↑ Miyashiro, Ryuhei; Matsui, Tomomi (2005), "A polynomial-time algorithm to find an equitable home–away assignment", Operations Research Letters, 33 (3): 235–241, CiteSeerX 10.1.1.64.240, doi:10.1016/j.orl.2004.06.004.
- ↑ Brualdi, R. A. (1980), "Matrices of zeros and ones with fixed row and column sum vectors", Linear Algebra Appl., 33: 159–231, doi:10.1016/0024-3795(80)90105-6.
- ↑ Woeginger, G. J. (1996), The reconstruction of polyominoes from their orthogonal projections, Technical Report SFB-65, Graz, Austria: TU Graz.
- ↑ Chrobak, Marek; Dürr, Christoph (1999), "Reconstructing hv-convex polyominoes from orthogonal projections", Information Processing Letters, 69 (6): 283–289, arXiv:cs/9906021, Bibcode:1999cs........6021D, doi:10.1016/S0020-0190(99)00025-3, S2CID 6799509.
- ↑ Kuba, Attila; Balogh, Emese (2002), "Reconstruction of convex 2D discrete sets in polynomial time", Theoretical Computer Science, 283 (1): 223–242, doi:10.1016/S0304-3975(01)00080-9; Brunetti, Sara; Daurat, Alain (2003), "An algorithm reconstructing convex lattice sets" (PDF), Theoretical Computer Science, 304 (1–3): 35–57, doi:10.1016/S0304-3975(03)00050-1, S2CID 2803842.
- ↑ Batenburg, K. Joost; Kosters, Walter A. (2008), "A reasoning framework for solving Nonograms", Combinatorial Image Analysis, 12th International Workshop, IWCIA 2008, Buffalo, NY, USA, April 7–9, 2008, Proceedings, Lecture Notes in Computer Science, vol. 4958, Springer-Verlag, pp. 372–383, doi:10.1007/978-3-540-78275-9_33, ISBN 978-3-540-78274-2; Batenburg, K. Joost; Kosters, Walter A. (2009), "Solving Nonograms by combining relaxations", Pattern Recognition, 42 (8): 1672–1683, Bibcode:2009PatRe..42.1672B, CiteSeerX 10.1.1.177.76, doi:10.1016/j.patcog.2008.12.003.
- ↑ Lewis, Harry R. (1978), "Renaming a set of clauses as a Horn set", Journal of the ACM, 25 (1): 134–135, doi:10.1145/322047.322059, MR 0468315, S2CID 3071958.
- ↑ Aspvall, Bengt (1980), "Recognizing disguised NR(1) instances of the satisfiability problem", Journal of Algorithms, 1 (1): 97–103, doi:10.1016/0196-6774(80)90007-3, MR 0578079.
- ↑ Brandstädt, Andreas; Hammer, Peter Ladislaw; Le, Van Bang; Lozin, Vadim V. (2005), "Bisplit graphs", Discrete Mathematics, 299 (1–3): 11–32, doi:10.1016/j.disc.2004.08.046.
- ↑ Wang, Hao; Xie, Haiyong; Yang, Yang Richard; Silberschatz, Avi; Li, Li Erran; Liu, Yanbin (2005), "Stable egress route selection for interdomain traffic engineering: model and analysis", 13TH IEEE International Conference on Network Protocols (ICNP'05), pp. 16–29, CiteSeerX 10.1.1.106.7345, doi:10.1109/ICNP.2005.39, ISBN 978-0-7695-2437-5, S2CID 4332805.
- ↑ Eskin, Eleazar; Halperin, Eran; Karp, Richard M. (2003), "Efficient reconstruction of haplotype structure via perfect phylogeny", Journal of Bioinformatics and Computational Biology, 1 (1): 1–20, doi:10.1142/S0219720003000174, PMID 15290779.
- ↑ Papadimitriou, Christos H. (1994), Computational Complexity, Addison-Wesley, pp. chapter 4.2, ISBN 978-0-201-53082-7., Thm. 16.3.
- ↑ 31.0 31.1 Cook, Stephen; Kolokolova, Antonina (2004), "A Second-Order Theory for NL", 19th Annual IEEE Symposium on Logic in Computer Science (LICS'04), pp. 398–407, doi:10.1109/LICS.2004.1319634, ISBN 978-0-7695-2192-3, S2CID 9936442.
- ↑ Bandelt, Hans-Jürgen; Chepoi, Victor (2008), "Metric graph theory and geometry: a survey", Surveys on discrete and computational geometry, Contemporary Mathematics, vol. 453, Providence, RI: American Mathematical Society, pp. 49–86, doi:10.1090/conm/453/08795, ISBN 9780821842393, MR 2405677. Chung, F. R. K.; Graham, R. L.; Saks, M. E. (1989), "A dynamic location problem for graphs" (PDF), Combinatorica, 9 (2): 111–132, doi:10.1007/BF02124674, S2CID 5419897. Feder, T. (1995), Stable Networks and Product Graphs, Memoirs of the American Mathematical Society, vol. 555.
- ↑ Feder, Tomás (1994), "Network flow and 2-satisfiability", Algorithmica, 11 (3): 291–319, doi:10.1007/BF01240738, S2CID 34194118.
- ↑ Angelsmark, Ola; Thapper, Johan (2005), "Algorithms for the maximum Hamming distance problem", Recent Advances in Constraints, Lecture Notes in Computer Science, vol. 3419, Springer-Verlag, pp. 128–141, doi:10.1007/11402763_10, ISBN 978-3-540-25176-7.
- ↑ Valiant, Leslie G. (1979), "The complexity of enumeration and reliability problems", SIAM Journal on Computing, 8 (3): 410–421, doi:10.1137/0208032
- ↑ Welsh, Dominic; Gale, Amy (2001), "The complexity of counting problems", Aspects of complexity: minicourses in algorithmics, complexity and computational algebra: mathematics workshop, Kaikoura, January 7–15, 2000, pp. 115ff, Theorem 57.
- ↑ Dahllöf, Vilhelm; Jonsson, Peter; Wahlström, Magnus (2005), "Counting models for 2SAT and 3SAT formulae", Theoretical Computer Science, 332 (1–3): 265–291, doi:10.1016/j.tcs.2004.10.037
- ↑ Fürer, Martin; Kasiviswanathan, Shiva Prasad (2007), "Algorithms for counting 2-SAT solutions and colorings with applications", Algorithmic Aspects in Information and Management, Lecture Notes in Computer Science, vol. 4508, Springer-Verlag, pp. 47–57, CiteSeerX 10.1.1.634.4498, doi:10.1007/978-3-540-72870-2_5, ISBN 978-3-540-72868-9.
- ↑ Wahlström, Magnus (2008), "A tighter bound for counting max-weight solutions to 2sat instances", International Workshop on Parameterized and Exact Computation, Lecture Notes in Computer Science, vol. 5018, pp. 202–213, CiteSeerX 10.1.1.129.9232, doi:10.1007/978-3-540-79723-4_19, ISBN 978-3-540-79722-7
- ↑ Bollobás, Béla; Borgs, Christian; Chayes, Jennifer T.; Kim, Jeong Han; Wilson, David B. (2001), "The scaling window of the 2-SAT transition", Random Structures and Algorithms, 18 (3): 201–256, arXiv:math/9909031, doi:10.1002/rsa.1006, S2CID 9954684; Chvátal, V.; Reed, B. (1992), "Mick gets some (the odds are on his side)", Proceedings., 33rd Annual Symposium on Foundations of Computer Science, pp. 620–627, doi:10.1109/SFCS.1992.267789, ISBN 978-0-8186-2900-6, S2CID 5575389; Goerdt, A. (1996), "A threshold for unsatisfiability", Journal of Computer and System Sciences, 53 (3): 469–486, doi:10.1006/jcss.1996.0081.
- ↑ M. R. Garey; D. S. Johnson; L. J. Stockmeyer (1976), "Some simplified NP-complete graph problems", Theoretical Computer Science (in English), 1 (3): 237–267, doi:10.1016/0304-3975(76)90059-1, ISSN 0304-3975; see pp. 4–6
- ↑ Lewin, Michael; Livnar, Dror; Zwick, Uri (2002), "Improved Rounding Techniques for the MAX 2-SAT and MAX DI-CUT Problems", Proceedings of the 9th International IPCO Conference on Integer Programming and Combinatorial Optimization, Springer-Verlag, pp. 67–82, ISBN 978-3-540-43676-8
- ↑ Austrin, Per (2007), "Balanced Max 2-sat Might Not Be the Hardest", Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing (STOC '07), New York, NY, USA: ACM, pp. 189–197, doi:10.1145/1250790.1250818, ISBN 978-1-59593-631-8, S2CID 2353625.
- ↑ Khot, Subhash; Kindler, Guy; Mossel, Elchanan; O'Donnell, Ryan (2004), "Optimal Inapproximability Results for MAX-CUT and Other 2-Variable CSPs?", FOCS '04: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, IEEE, pp. 146–154, CiteSeerX 10.1.1.126.2295, doi:10.1109/FOCS.2004.49, ISBN 978-0-7695-2228-9, S2CID 2090495
- ↑ Håstad, Johan (2001), "Some optimal inapproximability results", Journal of the ACM, 48 (4): 798–859, CiteSeerX 10.1.1.638.2808, doi:10.1145/502090.502098, S2CID 5120748.
- ↑ Bansal, N.; Raman, V. (1999), "Upper bounds for MaxSat: further improved", in Aggarwal, A.; Pandu Rangan, C. (eds.), Proc. 10th Conf. Algorithms and Computation, ISAAC'99, Lecture Notes in Computer Science, vol. 1741, Springer-Verlag, pp. 247–258; Gramm, Jens; Hirsch, Edward A.; Niedermeier, Rolf; Rossmanith, Peter (2003), "Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT", Discrete Applied Mathematics, 130 (2): 139–155, doi:10.1016/S0166-218X(02)00402-X; Kojevnikov, Arist; Kulikov, Alexander S. (2006), "A new approach to proving upper bounds for MAX-2-SAT", Proc. 17th ACM-SIAM Symp. Discrete Algorithms, pp. 11–17, doi:10.1145/1109557.1109559, ISBN 978-0-89871-605-4, S2CID 10194873
- ↑ 47.0 47.1 Flum, Jörg; Grohe, Martin (2006), Parameterized Complexity Theory, Springer, pp. 69–70, doi:10.1007/3-540-29953-X, ISBN 978-3-540-29952-3
- ↑ Chen, Jianer; Huang, Xiuzhen; Kanj, Iyad A.; Xia, Ge (2006), "Strong computational lower bounds via parameterized complexity", Journal of Computer and System Sciences, 72 (8): 1346–1367, doi:10.1016/j.jcss.2006.04.007
- ↑ Hähnle, Reiner (2001), "Advanced many-valued logics", in Gabbay, Dov M.; Günthner, Franz (eds.), Handbook of Philosophical Logic, vol. 2, Springer, pp. 297–395, doi:10.1007/978-94-017-0452-6_5, ISBN 978-94-017-0452-6 (see in particular p. 373); Hähnle, Reiner (2003), "Complexity of Many-valued Logics", in Fitting, Melvin; Orlowska, Ewa (eds.), Beyond two: theory and applications of multiple-valued logic, Studies in Fuzziness and Soft Computing, vol. 114, Springer, pp. 211–233, doi:10.1007/978-3-7908-1769-0_9, ISBN 978-3-7908-1541-2