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

Revision as of 10:06, 7 August 2023

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

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

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

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

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

इस खंड में दिखाए गए उदाहरण 2-संतोषजनकता उदाहरण के लिए निहितार्थ ग्राफ़।

इस प्रकार के विशेष प्रतिबंधित रूप के साथ बूलियन अभिव्यक्ति का उपयोग करके 2-संतोषजनकता समस्या का वर्णन किया जा सकता है। यह क्लॉज (तर्क) का तार्किक संयोजन ( बूलियन और ऑपरेशन) है, जहां प्रत्येक क्लॉज दो वेरिएबल या ऋणात्मक वेरिएबल का वियोजन ( बूलियन या ऑपरेशन) है। इस सूत्र में आने वाले वेरिएबल या उनके निषेधन को शाब्दिक (गणितीय तर्क) कहा जाता है।^[1] उदाहरण के लिए, निम्नलिखित सूत्र संयोजक सामान्य रूप में है, जिसमें सात वेरिएबल , ग्यारह उपवाक्य और 22 अक्षर हैं:

{\begin{aligned}&(x_{0}\lor x_{2})\land (x_{0}\lor \lnot x_{3})\land (x_{1}\lor \lnot x_{3})\land (x_{1}\lor \lnot x_{4})\land {}\\&(x_{2}\lor \lnot x_{4})\land {}(x_{0}\lor \lnot x_{5})\land (x_{1}\lor \lnot x_{5})\land (x_{2}\lor \lnot x_{5})\land {}\\&(x_{3}\lor x_{6})\land (x_{4}\lor x_{6})\land (x_{5}\lor x_{6}).\end{aligned}}

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

इस रूप में सूत्रों को 2-सीएनएफ सूत्र के रूप में जाना जाता है। इस नाम में 2 प्रति खंड शाब्दिकों की संख्या को दर्शाता है, और सीएनएफ संयोजक सामान्य रूप के लिए है, विच्छेदन के संयोजन के रूप में प्रकार की बूलियन अभिव्यक्ति है।^[1] कैलिफ़ोर्निया विश्वविद्यालय, डेविस के गणितज्ञ मेल्वेन आर. क्रॉम के कार्य के पश्चात, उन्हें क्रॉम सूत्र भी कहा जाता है, जिनका 1967 का पेपर 2-संतोषजनकता समस्या पर सबसे प्रारम्भिक कार्यों में से था।^[2]

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

(x_{0}\lor \lnot x_{3})\;\equiv \;(\lnot x_{0}\Rightarrow \lnot x_{3})\;\equiv \;(x_{3}\Rightarrow x_{0}).

इन विभिन्न प्रकार के ऑपरेशनों के मध्य इस तुल्यता के कारण, 2-संतोषजनकता उदाहरण को निहितार्थ सामान्य रूप में भी लिखा जा सकता है, जिसमें हम संयोजनात्मक सामान्य रूप में प्रत्येक या खंड को उन दो निहितार्थों से प्रतिस्थापित करते हैं जिनके लिए यह समतुल्य है।^[3]

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

एल्गोरिदम

2-संतोषजनकता समस्या को हल करने के लिए अनेक एल्गोरिदम ज्ञात हैं। उनमें से सबसे कुशल रैखिक समय लेते हैं।^[2]^[4]^[5]

संकल्प और सकर्मक समापन

क्रोम (1967) 2-संतोषजनक उदाहरणों को हल करने के लिए निम्नलिखित बहुपद समय निर्णय प्रक्रिया का वर्णन किया गया है।^[2]

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

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

क्रॉम मुख्य रूप से एल्गोरिदम की दक्षता के अतिरिक्त अनुमान नियमों की प्रणालियों की पूर्णता (तर्क) से चिंतित था। चूँकि, उनकी पद्धति 2-संतोषजनकता समस्याओं को हल करने के लिए बहुपद समयबद्धता की ओर ले जाती है। समान वेरिएबल का उपयोग करने वाले सभी खंडों को साथ समूहित करके, और खंडों की प्रत्येक जोड़ी पर अनुमान नियम प्रयुक्त करके, किसी दिए गए 2-सीएनएफ उदाहरण से संभव सभी अनुमान खोजता संभव है, और यह परीक्षण करना संभव है कि क्या यह सुसंगत है, कुल समय में $O(n 3)$ ,है जहाँ $n$ उदाहरण में वेरिएबलों की संख्या है। यह सूत्र वेरिएबलों की संख्या को गुणा करने से $O(n 2)$ प्राप्त होता है किसी दिए गए वेरिएबल को सम्मिलित करने वाले खंडों के जोड़े की संख्या, जिस पर अनुमान नियम प्रयुक्त किया जा सकता है। इस प्रकार, यह निर्धारित करना संभव है कि दिया गया 2-सीएनएफ उदाहरण समय में संतोषजनक या नहीं $O(n 3)$ है . क्योंकि क्रॉम की विधि का उपयोग करके संतोषजनक असाइनमेंट खोजने में अनुक्रम सम्मिलित होता है $O(n)$ निरंतरता की जांच, इसमें समय लगेगा $O(n 4)$ . इवेन, इटाई & शमीर (1976) तेज़ समय सीमा का उद्धरण दें $O(n 2)$ इस एल्गोरिथम के लिए, इसके संचालन के अधिक सावधानीपूर्वक क्रम पर आधारित है। फिर भी, पश्चात के रैखिक समय एल्गोरिदम द्वारा इस छोटी समय सीमा में भी अधिक सुधार इवेन, इटाई & शमीर (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-संतोषजनकता पर आधारित हैं। यह समस्या किसी आरेख या मानचित्र की विशेषताओं पर पाठ्य लेबल लगाने से संबंधित है। सामान्यतः, प्रत्येक लेबल के लिए संभावित स्थानों का सेट अत्यधिक प्रतिबंधित होता है, जो न केवल मानचित्र द्वारा (प्रत्येक लेबल को उस सुविधा के पास होना चाहिए जिसे वह लेबल करता है, और अन्य सुविधाओं को अस्पष्ट नहीं करना चाहिए), किन्तु एक-दूसरे द्वारा: प्रत्येक दो लेबल को एक-दूसरे को ओवरलैप करने से बचना चाहिए, अन्यथा वह अस्पष्ट हो जाएंगे। सामान्यतः इन बाधाओं का पालन करने वाला लेबल प्लेसमेंट खोजता NP हार्ड समस्या है। चूँकि , यदि प्रत्येक फीवेरिएबल में उसके लेबल के लिए केवल दो संभावित स्थान हैं (जैसे, फीवेरिएबल के बाईं और दाईं ओर विस्तार) तो लेबल प्लेसमेंट को बहुपद समय में हल किया जा सकता है। इस स्तिथि में, कोई 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 (n 3)$ व्यास के योग की क्लस्टरिंग समस्या के लिए जिससे कुल समय सीमा तय हो सकता है।^[18]

शेड्यूलिंग

इवेन, इटाई & शमीर (1976) कक्षा समय-निर्धारण के मॉडल पर विचार करें जिसमें छात्रों के प्रत्येक समूह को पढ़ाने के लिए n शिक्षकों का समूह निर्धारित किया जाना चाहिए। उस शिक्षक के प्रति सप्ताह घंटों की संख्या $i$ समूह के साथ बिताता है जहाँ $j$ प्रविष्टि द्वारा वर्णित है और $R_{ij}$ आव्युह का $R$ समस्या के इनपुट के रूप में दिया गया है, और प्रत्येक शिक्षक के पास घंटों का सेट भी है जिसके समय वह शेड्यूल के लिए उपलब्ध रहता है। जैसा कि वह दिखाते हैं, समस्या NP-पूर्ण है, तथापि प्रत्येक शिक्षक के पास अधिकतम तीन उपलब्ध घंटे हों, किन्तु इसे 2-संतोषजनकता के उदाहरण के रूप में हल किया जा सकता है जब प्रत्येक शिक्षक के पास केवल दो उपलब्ध घंटे हों। (केवल उपलब्ध घंटे वाले शिक्षकों को समस्या से आसानी से छुटकारा दिलाया जा सकता है।) इस समस्या में, प्रत्येक वेरिएबल $v_{ij}$ उस शिक्षक के घंटे से मेल खाता है $i$ समूह के साथ बिताना चाहिए जो की $j$ , वेरिएबल के लिए असाइनमेंट निर्दिष्ट करता है कि क्या वह घंटा शिक्षक के उपलब्ध घंटों में से पहला या दूसरा है, और 2-संतोषजनकता खंड है जो दो प्रकार के किसी भी टकराव को रोकता है: शिक्षक को ही समय में एक-दूसरे को सौंपे गए दो समूह, या ही समय में दो शिक्षकों को निरुपित किय गए समूह होते है ।^[5]

मियाशिरो & मत्सुई (2005) खेल शेड्यूलिंग की समस्या के लिए 2-संतोषजनकता प्रयुक्त करें, जिसमें राउंड-रॉबिन टूर्नामेंट की जोड़ियों को पहले ही चुना जा चुका है और खेलों को टीमों के स्टेडियमों को सौंपा जाना चाहिए। इस समस्या में, जहां तक संभव हो घर और बाहर के खेलों को वैकल्पिक करना वांछनीय है, ब्रेक से बचना चाहिए जिसमें टीम पंक्ति में दो घरेलू खेल खेलती है या पंक्ति में दो दूर खेल खेलती है। जहाँ अधिक से अधिक दो टीमें घर और बाहर के खेलों के मध्य निरंतरता से ब्रेक से पूरी तरह बच सकती हैं; किसी अन्य टीम का होम-अवे शेड्यूल इन दोनों के समान नहीं हो सकता, क्योंकि तब वह उस टीम के साथ खेलने में असमर्थ होगी जिसके साथ उसका शेड्यूल समान था। इसलिए, अधिकतम शेड्यूल में दो ब्रेकलेस टीमें होती हैं और हर दूसरी टीम के लिए ब्रेक होता है। जब ब्रेकलेस टीमों में से को चुना जाता है, तो कोई 2-संतोषजनकता की समस्या खड़ी कर सकता है, जिसमें प्रत्येक वेरिएबल ही गेम में ही टीम के लिए होम-अवे असाइनमेंट का प्रतिनिधित्व करता है, और बाधाएं उन गुणों को प्रयुक्त करती हैं कि किन्हीं दो टीमों के पास अपने गेम के लिए सुसंगत असाइनमेंट होता है, प्रत्येक टीम के पास ब्रेकलेस टीम के साथ खेल से पहले अधिकतम ब्रेक और गेम के पश्चात अधिकतम ब्रेक होता है, और किसी भी टीम के पास दो ब्रेक नहीं होते हैं। इसलिए, यह परीक्षण करना कि क्या कोई शेड्यूल अधिकतम संख्या में ब्रेक के साथ समाधान स्वीकार करता है, ब्रेकलेस टीम की प्रत्येक पसंद के लिए 2-संतोषजनकता समस्याओं की रैखिक संख्या को हल करके किया जा सकता है। समान तकनीक ऐसे शेड्यूल खोजने की भी अनुमति देती है जिसमें प्रत्येक टीम के पास ही ब्रेक होता है, और ब्रेक की संख्या को कम करने के अतिरिक्त अधिकतम करने की अनुमति देता है (टीमों द्वारा यात्रा की गई कुल माइलेज को कम करने के लिए)।^[19]

असतत टोमोग्राफी

नॉनोग्राम पहेली का उदाहरण.

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

यद्यपि पंक्ति और स्तंभ के योग वाले आव्युह को खोजने के लिए बहुपद समय एल्गोरिदम उपस्तिथ हैं,^[20] समाधान अद्वितीय से बहुत दूर हो सकता है: 2 × 2 पहचान आव्युह के रूप में किसी भी उपआव्युह को समाधान की शुद्धता को प्रभावित किए बिना पूरक किया जा सकता है। इसलिए, शोधकर्ताओं ने पुनर्निर्माण किए जाने वाले आकार पर बाधाओं की खोज की है जिसका उपयोग समाधानों के स्थान को प्रतिबंधित करने के लिए किया जा सकता है। उदाहरण के लिए, कोई यह मान सकता है कि आकृति जुड़ी हुई है; चूँकि, यह परीक्षण करना कि क्या कोई कनेक्टेड समाधान उपस्तिथ है, NP-पूर्ण है।^[21] और अधिक सीमित संस्करण जिसे हल करना आसान है वह यह है कि आकार ऑर्थोगोनल उत्तलता है: प्रत्येक पंक्ति और स्तंभ में वर्गों का एकल सन्निहित ब्लॉक होता है। पिछले अनेक समाधानों में सुधार, क्रोबक & ड्यूर (1999) ने दिखाया कि 2-एसएटी का उपयोग करके कनेक्टेड ऑर्थोगोनली उत्तल आकृतियों को कुशलतापूर्वक कैसे पुनर्निर्माण किया जाए।^[22] उनके समाधान का विचार पुनर्निर्माण की जाने वाली आकृति की सबसे बाईं और दाईं ओर की कोशिकाओं वाली पंक्तियों के सूचकांक का अनुमान लगाना है, और फिर 2-संतोषजनकता समस्या स्थापित करना है जो परीक्षण करता है कि क्या इन अनुमानों और दी गई पंक्ति और स्तंभ योगों के अनुरूप कोई आकृति उपस्तिथ है। वह प्रत्येक वर्ग के लिए चार 2-संतोषजनकता वेरिएबल का उपयोग करते हैं जो दिए गए आकार का भाग हो सकते हैं, यह संकेत करने के लिए कि क्या यह आकृति के चार संभावित कोने क्षेत्रों में से प्रत्येक से संबंधित है, और वह उन बाधाओं का उपयोग करते हैं जो इन क्षेत्रों को असंयुक्त होने के लिए विवश करते हैं, वांछित आकार प्राप्त करने के लिए, सन्निहित पंक्तियों और स्तंभों के साथ समग्र आकार बनाने के लिए, और वांछित पंक्ति और स्तंभ योग प्राप्त करने के लिए। उनके एल्गोरिदम में $O(m 3 n)$ समय लगता है जहाँ $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-संतोषजनकता समस्या में बदल सकती है। अधिक सुप्रसिद्ध सम्मिश्र ता वर्ग NP (सम्मिश्रता) के लिए समान परिणामों के अनुरूप, यह परिवर्तन इमरमैन-स्ज़ेलेपीसीसेनी प्रमेय के साथ मिलकर एनएल में किसी भी समस्या को दूसरे क्रम के तर्क सूत्र के रूप में प्रस्तुत करने की अनुमति देता है, जिसमें लंबाई 2 तक सीमित खंडों के साथ एकल अस्तित्वगत रूप से परिमाणित विधेय होता है। ऐसे सूत्रों को एसओ-क्रोम के रूप में जाना जाता है।^[31] इसी प्रकार, अंतर्निहित सामान्य रूप को ट्रांजिटिव क्लोजर के लिए ऑपरेटर के अतिरिक्त के साथ प्रथम क्रम तर्क में व्यक्त किया जा सकता है।^[31]

सभी समाधानों का समुच्चय

उदाहरण 2-संतोषजनकता उदाहरण के सभी समाधानों का प्रतिनिधित्व करने वाला माध्य ग्राफ जिसका निहितार्थ ग्राफ ऊपर दिखाया गया है।

2-संतोषजनकता उदाहरण के सभी समाधानों के सेट में माध्यिका ग्राफ की संरचना होती है, जिसमें किनारा वेरिएबल के सेट के मूल्यों को फ़्लिप करने के संचालन से मेल खाता है जो सभी दूसरे के समान या असमान होने के लिए बाध्य हैं। विशेष रूप से, इस तरह से किनारों का अनुसरण करके कोई भी किसी भी समाधान से किसी अन्य समाधान तक पहुंच सकता है। इसके विपरीत, किसी भी माध्य ग्राफ को इस तरह से 2-संतोषजनकता उदाहरण के समाधान के सेट के रूप में दर्शाया जा सकता है। किन्हीं तीन समाधानों का माध्य प्रत्येक वेरिएबल को तीन समाधानों के बहुमत फलन में रखे गए मान पर सेट करके बनाया जाता है। यह माध्यिका सदैव उदाहरण के लिए और समाधान बनाती है।^[32]

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

दो संतोषजनक असाइनमेंट खोजने के लिए एल्गोरिदम भी उपस्तिथ हैं जिनकी दूसरे से अधिकतम हैमिंग दूरी है।^[34]

संतोषजनक असाइनमेंट की संख्या की गिनती

1. 2एसएटी किसी दिए गए 2-सीएनएफ सूत्र में संतोषजनक असाइनमेंट की संख्या की गणना करने की समस्या है। यह गिनती समस्या #पी-पूर्ण है,^[35] जिसका अर्थ है कि यह बहुपद समय में हल करने योग्य नहीं है जब तक कि P = NP न हो। इसके अतिरिक्त , #2एसएटी के लिए कोई पूरी तरह से बहुपद यादृच्छिक सन्निकटन योजना नहीं है जब तक कि NP = RP न हो और यह तब भी प्रयुक्त होता है जब इनपुट मोनोटोन 2-CNF फ़ार्मुलों तक सीमित होता है, यानी, 2-सीएनएफ सूत्र जिसमें प्रत्येक शाब्दिक एक चर की सकारात्मक घटना होती है^[36]

2एसएटी सूत्रों के लिए संतोषजनक असाइनमेंट की स्पष्ट संख्या की गणना करने के लिए सबसे तेज़ $O(1.2377^{n})$ ज्ञात एल्गोरिदम समय में चलता है .^[37]^[38]^[39]

यादृच्छिक 2-संतोषजनक उदाहरण

सभी संभावित दो-वेरिएबल खंडों के सेट से यादृच्छिक रूप से प्रत्येक खंड को समान रूप से चुनकर, किसी दिए गए वेरिएबल की संख्या n और खंडों के m के लिए, यादृच्छिक रूप से 2-संतोषजनक उदाहरण बनाया जा सकता है। जब m, n के सापेक्ष छोटा होता है, तो ऐसा उदाहरण संभवतः संतोषजनक होगा, किन्तु m के बड़े मानों के संतोषजनक होने की संभावनाएँ कम होती हैं। अधिक स्पष्ट रूप से, यदि m/n को स्थिर α ≠ 1 के रूप में तय किया गया है, तो संतुष्टि की संभावना अनुक्रम की सीमा की ओर बढ़ जाती है क्योंकि n अनंत तक जाता है: यदि α < 1, सीमा है, जबकि यदि α > 1, सीमा शून्य है। इस प्रकार, समस्या α = 1 पर चरण संक्रमण प्रदर्शित करती है।^[40]

अधिकतम-2-संतोषजनकता

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

कट (ग्राफ सिद्धांत) खोजने की समस्या के रूप में मैक्स -2-सैट को तैयार करके (अर्थात, दो सबसेट में वर्टिस का विभाजन) उन किनारों की संख्या को अधिकतम करता है जो पहले सबसेट में एंडपॉइंट और दूसरे में एंडपॉइंट में एंडपॉइंट, निहितार्थ ग्राफ से संबंधित ग्राफ में ग्राफ को पूरा करने के लिए, जो कि कम से कम है। ।^[42] संतुलित मैक्स 2-एसएटी उदाहरण मैक्स 2-एसएटी का उदाहरण है जहां प्रत्येक वेरिएबल समान भार के साथ धनात्मक और ऋणात्मक रूप से प्रकट होता है। इस समस्या के लिए, ऑस्ट्रिन ने सन्निकटन $\min \left\{(3-\cos \theta )^{-1}(2+(2/\pi )\theta )\,:\,\pi /2\leq \theta \leq \pi \right\}=0.943...$ अनुपात में सुधार किया है .^[43]

यदि अद्वितीय गेम का अनुमान सत्य है, तो बहुपद समय में 0.943... से उत्तम अनुमानित अनुपात के साथ, मैक्स 2-एसएटी का अनुमान लगाना असंभव है, चाहे वह संतुलित हो या नहीं।^[44] अशक्त धारणा के अनुसार कि P बनाम NP समस्या या P ≠ NP, समस्या को केवल 21/22 = 0.95454 से उत्तम स्थिरांक के अंदर अनुपयुक्त माना जाता है...^[45]

विभिन्न लेखकों ने मैक्स-2-एसएटी उदाहरणों के स्पष्ट समाधान के लिए घातीय सबसे व्यर्थ समय सीमा का भी पता लगाया है।^[46]

भारित-2-संतोषजनकता

भारित 2-संतोषजनकता समस्या (W2सैट ) में, इनपुट है जो $n$ -परिवर्तनीय 2एसएटी उदाहरण और पूर्णांक $k$ , और समस्या यह तय करना है कि वास्तव में कोई संतोषजनक असाइनमेंट उपस्तिथ है या नहीं जिससे कि यह पता चलता कि $k$ वेरिएबल सत्य हैं।^[47]

W2सैट समस्या में विशेष स्तिथि के रूप में सेट खोजने की वर्टेक्स कवर समस्या सम्मिलित है जो की $k$ शीर्ष जो किसी दिए गए अप्रत्यक्ष ग्राफ़ के सभी किनारों को साथ छूते हैं। शीर्ष कवर समस्या के किसी भी उदाहरण के लिए, कोई ग्राफ़ के प्रत्येक शीर्ष के लिए वेरिएबल के साथ समतुल्य W2सैट समस्या का निर्माण कर सकता है। प्रत्येक किनारा u ∨ v को 2एसएटी खंड द्वारा दर्शाया जा सकता है $u \lor v$ जिसे दोनों में से किसी को सम्मिलित करके ही संतुष्ट किया जा सकता है जिसमे यह $u$ या $v$ समाधान के वास्तविक वेरिएबलों के मध्य फिर परिणामी 2एसएटी सूत्र के संतोषजनक उदाहरण वर्टेक्स कवर समस्या के समाधान को एन्कोड करते हैं, और इसके साथ संतोषजनक असाइनमेंट होता है $k$ सत्य वेरिएबल यदि और केवल यदि कोई शीर्ष आवरण है $k$ शिखर. इसलिए, वर्टेक्स कवर की तरह, W2सैट NP-पूर्ण है।

इसके अतिरिक्त , पैरामीटरयुक्त सम्मिश्र ता में W2सैट प्राकृतिक W(1)|W[1]-पूर्ण समस्या प्रदान करता है,^[47] जिसका तात्पर्य यह है कि W2सैट निश्चित-पैरामीटर ट्रैक्टेबल नहीं है जब तक कि यह W(1)| W[1] में सभी समस्याओं के लिए मान्य न हो। अर्थात्, यह संभावना नहीं है कि W2सैट के लिए कोई एल्गोरिदम उपस्तिथ है जिसका रनिंग टाइम रूप लेता है $f (k)\cdot n O (1)$ . इससे भी $n o (k)$ अधिक दृढ़ता से, W2सैट को समय पर हल नहीं किया जा सकता है जब तक कि घातीय समय परिकल्पना विफल न हो जाए।^[48]

मात्राबद्ध बूलियन सूत्र

2-संतोषजनकता के लिए पहला बहुपद-समय एल्गोरिदम खोजने के साथ-साथ, क्रोम (1967) ने ट्रू क्वांटिफाइड बूलियन सूत्र के मूल्यांकन की समस्या भी तैयार की जिसमें क्वांटिफाई किया जा रहा सूत्र 2-सीएनएफ सूत्र है। 2-संतोषजनकता समस्या इस परिमाणित 2-सीएनएफ समस्या का विशेष स्तिथि है, जिसमें सभी परिमाणक अस्तित्वगत परिमाणक हैं। क्रॉम ने इन सूत्रों के लिए प्रभावी निर्णय प्रक्रिया भी विकसित की एस्पवॉल, प्लास & टारजन (1979) ने दिखाया कि इसे दृढ़ता से जुड़े अवयवों और टोपोलॉजिकल ऑर्डरिंग की उनकी तकनीक के विस्तार द्वारा, रैखिक समय में हल किया जा सकता है।^[2]^[4]

अनेक-मूल्यवान तर्क

2-संतोषजनकता समस्या को प्रस्तावित बहु-मूल्यवान तर्क के लिए भी पूछा जा सकता है। एल्गोरिदम सामान्यतः रैखिक नहीं होते हैं, और कुछ तर्कों के लिए समस्या NP-पूर्ण भी होती है। सर्वेक्षणों के लिए हनले (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

[cnf-1] 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.

[Krom1967-2] 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.

[3] 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.

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

[EIS76-5] 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.

[6] 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.

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

[8] 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.

[9] Harrison, Paul, Robust topological sorting and Tarjan's algorithm in Python, retrieved 9 February 2011

[fw91-10] 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.

[11] 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.

[12] 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.

[13] 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.

[14] 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.

[15] 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.

[16] 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).

[17] Hansen, P.; Jaumard, B. (1987), "Minimum sum of diameters clustering", Journal of Classification, 4 (2): 215–226, doi:10.1007/BF01896987, S2CID 120583429.

[18] 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.

[19] 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.

[20] 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.

[21] Woeginger, G. J. (1996), The reconstruction of polyominoes from their orthogonal projections, Technical Report SFB-65, Graz, Austria: TU Graz.

[22] 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.

[23] 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.

[24] 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.

[25] 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.

[26] 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.

[27] 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.

[28] 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.

[29] 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.

[30] Papadimitriou, Christos H. (1994), Computational Complexity, Addison-Wesley, pp. chapter 4.2, ISBN 978-0-201-53082-7., Thm. 16.3.

[ck04-31] 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.

[32] 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.

[33] Feder, Tomás (1994), "Network flow and 2-satisfiability", Algorithmica, 11 (3): 291–319, doi:10.1007/BF01240738, S2CID 34194118.

[34] 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.

[35] Valiant, Leslie G. (1979), "The complexity of enumeration and reliability problems", SIAM Journal on Computing, 8 (3): 410–421, doi:10.1137/0208032

[36] 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.

[37] 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

[38] 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.

[39] 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

[40] 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.

[41] 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

[42] 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

[43] 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.

[44] 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

[45] 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.

[46] 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

[fg06-47] 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

[48] 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

[49] 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

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

[32]

[33]

[34]

[35]

[36]

[37]

[38]

[39]

[40]

[41]

[42]

[43]

[44]

[45]

[46]

[47]

[48]

[49]

@@ Line 6: / Line 6: @@
 -संतोषजनकता को ज्यामिति और विज़ुअलाइज़ेशन समस्याओं पर प्रयुक्त किया जा सकता है जिसमें वस्तुओं के संग्रह में प्रत्येक के दो संभावित स्थान होते हैं और लक्ष्य प्रत्येक वस्तु के लिए प्लेसमेंट खोजता है जो अन्य वस्तुओं के साथ ओवरलैप होने से बचाता है। अन्य अनुप्रयोगों में क्लस्टर के व्यास के योग को कम करने के लिए क्लस्टरिंग डेटा, कक्षा और खेल शेड्यूलिंग और उनके क्रॉस-सेक्शन के बारे में जानकारी से आकृतियों को पुनर्प्राप्त करना सम्मिलित है।
-[[कम्प्यूटेशनल जटिलता सिद्धांत|कम्प्यूटेशनल सम्मिश्रता सिद्धांत]] में, 2-संतोषजनकता [[एनएल-पूर्ण]] समस्या का उदाहरण प्रदान करती है, जिसे संचयन  की लघुगणकीय मात्रा का उपयोग करके गैर-नियतात्मक रूप से हल किया जा सकता है और यह इस संसाधन में हल करने योग्य सबसे कठिन समस्याओं में से है। 2-संतोषजनकता उदाहरण के सभी समाधानों के सेट को [[माध्यिका ग्राफ]] की संरचना दी जा सकती है, किन्तु इन समाधानों की गिनती शार्प-P-पूर्ण| या P-पूर्ण है और इसलिए बहुपद-समय समाधान की उम्मीद नहीं है। यादृच्छिक उदाहरणों को हल करने योग्य से अघुलनशील उदाहरणों में तेज चरण संक्रमण से गुजरना पड़ता है क्योंकि वेरिएबल के लिए बाधाओं का अनुपात 1 से अधिक बढ़ जाता है, घटना अनुमानित है किन्तु संतुष्टि समस्या के अधिक सम्मिश्र रूपों के लिए अप्रमाणित है। 2-संतोषजनकता की कम्प्यूटेशनल रूप से कठिन विविधता, सत्य असाइनमेंट खोजता जो संतुष्ट बाधाओं की संख्या को अधिकतम करता है, अनुमानित एल्गोरिदम है जिसकी अधिकतमता अद्वितीय गेम अनुमान पर निर्भर करती है, और और कठिन भिन्नता, वास्तविक वेरिएबल की संख्या को कम करने वाला संतोषजनक असाइनमेंट खोजता , [[पैरामीटरयुक्त जटिलता|पैरामीटर युक्त सम्मिश्रता]] के लिए महत्वपूर्ण परीक्षण स्तिथि है।
+[[कम्प्यूटेशनल जटिलता सिद्धांत|कम्प्यूटेशनल सम्मिश्रता सिद्धांत]] में, 2-संतोषजनकता [[एनएल-पूर्ण]] समस्या का उदाहरण प्रदान करती है, जिसे संचयन की लघुगणकीय मात्रा का उपयोग करके गैर-नियतात्मक रूप से हल किया जा सकता है और यह इस संसाधन में हल करने योग्य सबसे कठिन समस्याओं में से है। 2-संतोषजनकता उदाहरण के सभी समाधानों के सेट को [[माध्यिका ग्राफ]] की संरचना दी जा सकती है, किन्तु इन समाधानों की गिनती शार्प-P-पूर्ण| या P-पूर्ण है और इसलिए बहुपद-समय समाधान की उम्मीद नहीं है। यादृच्छिक उदाहरणों को हल करने योग्य से अघुलनशील उदाहरणों में तेज चरण संक्रमण से गुजरना पड़ता है क्योंकि वेरिएबल के लिए बाधाओं का अनुपात 1 से अधिक बढ़ जाता है, घटना अनुमानित है किन्तु संतुष्टि समस्या के अधिक सम्मिश्र रूपों के लिए अप्रमाणित है। 2-संतोषजनकता की कम्प्यूटेशनल रूप से कठिन विविधता, सत्य असाइनमेंट खोजता जो संतुष्ट बाधाओं की संख्या को अधिकतम करता है, अनुमानित एल्गोरिदम है जिसकी अधिकतमता अद्वितीय गेम अनुमान पर निर्भर करती है, और और कठिन भिन्नता, वास्तविक वेरिएबल की संख्या को कम करने वाला संतोषजनक असाइनमेंट खोजता , [[पैरामीटरयुक्त जटिलता|पैरामीटर युक्त सम्मिश्रता]] के लिए महत्वपूर्ण परीक्षण स्तिथि है।
 ==समस्या प्रतिनिधित्व                                            ==
@@ Line 32: / Line 32: @@
 -सीएनएफ सूत्र में प्रत्येक खंड वेरिएबल या अस्वीकृत वेरिएबल से दूसरे में निहितार्थ के लिए [[तार्किक तुल्यता]] है। उदाहरण के लिए, उदाहरण में दूसरा खंड तीन समकक्ष विधियों में से किसी में लिखा जा सकता है:
 <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>
 -संतोषजनकता उदाहरण का वर्णन करने का तीसरा, अधिक ग्राफिकल विधि निहितार्थ ग्राफ के रूप में है। निहितार्थ ग्राफ निर्देशित ग्राफ है जिसमें प्रति वेरिएबल या ऋणात्मक वेरिएबल में शीर्ष (ग्राफ सिद्धांत) होता है, और शीर्ष को दूसरे से जोड़ने वाला किनारा होता है जब भी संबंधित वेरिएबल उदाहरण के निहितार्थ सामान्य रूप में निहितार्थ से संबंधित होते हैं। निहितार्थ ग्राफ [[तिरछा-सममित ग्राफ|विषम -सममित ग्राफ]] होना चाहिए, जिसका अर्थ है कि इसमें [[ग्राफ ऑटोमोर्फिज्म]] है जो प्रत्येक वेरिएबल को उसके निषेध में ले जाता है और सभी किनारों के झुकाव को विपरीत कर देता है।<ref name="APT79">{{citation
@@ Line 58: / Line 58: @@
 क्रॉम लिखते हैं कि सूत्र <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-संतोषजनकता समस्याओं को हल करने के लिए बहुपद समयबद्धता की ओर ले जाती है। समान वेरिएबल का उपयोग करने वाले सभी खंडों को साथ समूहित करके, और खंडों की प्रत्येक जोड़ी पर अनुमान नियम प्रयुक्त करके, किसी दिए गए 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}} के द्वारा किया गया था |
 -संतोषजनकता उदाहरण के निहितार्थ ग्राफ के संदर्भ में, क्रॉम के अनुमान नियम की व्याख्या ग्राफ के संक्रमणीय समापन के निर्माण के रूप में की जा सकती है। जैसा {{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>
@@ Line 69: / Line 69: @@
 प्रारंभ में, कोई विकल्प बिंदु नहीं है, और सभी वेरिएबल अनअसाइन किए गए हैं। प्रत्येक चरण में, एल्गोरिदम उस वेरिएबल को चुनता है जिसका मान सेट करना है, इस प्रकार:
-*यदि कोई ऐसा खंड है जिसके दोनों वेरिएबल पहले से ही सेट हैं, इस तरह से जो खंड को गलत सिद्ध करता है, तो एल्गोरिदम अपने सबसे हालिया विकल्प बिंदु पर वापस आ जाता है, उस विकल्प के पश्चात से किए गए असाइनमेंट को पूर्ववत कर देता है, और उस विकल्प पर किए गए निर्णय को विपरीत  देता है। यदि कोई विकल्प बिंदु नहीं है, या यदि एल्गोरिदम पहले से ही सबसे हालिया विकल्प बिंदु पर पीछे हट गया है, तो यह खोज को रोक देता है और रिपोर्ट करता है कि इनपुट 2-सीएनएफ सूत्र असंतोषजनक है।
+*यदि कोई ऐसा खंड है जिसके दोनों वेरिएबल पहले से ही सेट हैं, इस तरह से जो खंड को गलत सिद्ध करता है, तो एल्गोरिदम अपने सबसे हालिया विकल्प बिंदु पर वापस आ जाता है, उस विकल्प के पश्चात से किए गए असाइनमेंट को पूर्ववत कर देता है, और उस विकल्प पर किए गए निर्णय को विपरीत देता है। यदि कोई विकल्प बिंदु नहीं है, या यदि एल्गोरिदम पहले से ही सबसे हालिया विकल्प बिंदु पर पीछे हट गया है, तो यह खोज को रोक देता है और रिपोर्ट करता है कि इनपुट 2-सीएनएफ सूत्र असंतोषजनक है।
 *यदि कोई ऐसा खंड है जिसमें खंड के दो वेरिएबलों में से पहले ही सेट किया जा चुका है, और खंड अभी भी या तो सत्य या गलत हो सकता है, तो दूसरा वेरिएबल इस तरह से सेट किया जाता है जो खंड को सत्य बनने के लिए विवश करता है।
 *शेष स्तिथि में, प्रत्येक खंड के या तो सत्य होने की आश्वासन है, चाहे शेष वेरिएबल कैसे भी निर्दिष्ट किए गए हों, या इसके दो वेरिएबल में से किसी को भी अभी तक निर्दिष्ट नहीं किया गया है। इस स्तिथि में एल्गोरिदम नया विकल्प बिंदु बनाता है और किसी भी अनअसाइन किए गए वेरिएबल को इच्छानुसार चुने गए मान पर सेट करता है।
-सहज रूप से, एल्गोरिथ्म अपने प्रत्येक विकल्प को चुनने के पश्चात अनुमान की सभी श्रृंखलाओं का पालन करता है। इससे या तो विरोधाभास उत्पन्न  होता है और कदम पीछे हट जाता है, या, यदि कोई विरोधाभास नहीं निकलता है, तो इसका अर्थ यह है कि चुनाव सही था जो संतोषजनक असाइनमेंट की ओर ले जाता है। इसलिए, एल्गोरिदम या तो सही रूप से संतोषजनक असाइनमेंट पाता है या यह सही रूप से निर्धारित करता है कि इनपुट असंतोषजनक है।<ref name="EIS76" />
+सहज रूप से, एल्गोरिथ्म अपने प्रत्येक विकल्प को चुनने के पश्चात अनुमान की सभी श्रृंखलाओं का पालन करता है। इससे या तो विरोधाभास उत्पन्न होता है और कदम पीछे हट जाता है, या, यदि कोई विरोधाभास नहीं निकलता है, तो इसका अर्थ यह है कि चुनाव सही था जो संतोषजनक असाइनमेंट की ओर ले जाता है। इसलिए, एल्गोरिदम या तो सही रूप से संतोषजनक असाइनमेंट पाता है या यह सही रूप से निर्धारित करता है कि इनपुट असंतोषजनक है।<ref name="EIS76" />
 यहां तक कि एट अल. इस एल्गोरिथम को कुशलतापूर्वक कैसे कार्यान्वित किया जाए, इसका विस्तार से वर्णन नहीं किया गया। वह केवल यह बताते हैं कि किसी भी निर्णय के निहितार्थ खोजने के लिए उपयुक्त डेटा संरचनाओं का उपयोग करके, एल्गोरिदम के प्रत्येक चरण (बैकट्रैकिंग के अतिरिक्त ) को जल्दी से निष्पादित किया जा सकता है। चूँकि कुछ इनपुट के कारण एल्गोरिदम अनेक बार बैकट्रैक कर सकता है, हर बार बैकट्रैकिंग से पहले अनेक चरण निष्पादित करता है, इसलिए इसकी समग्र सम्मिश्र ता अरेखीय हो सकती है। इस समस्या से बचने के लिए, वह एल्गोरिदम को संशोधित करते हैं जिससे , प्रत्येक विकल्प बिंदु पर पहुंचने के पश्चात, यह विकल्प बिंदु पर वेरिएबल सेट के लिए दो असाइनमेंट का साथ परीक्षण करना प्रारंभ कर दे, दोनों असाइनमेंट में से प्रत्येक पर समान संख्या में चरण खर्च करें। जैसे ही इन दो असाइनमेंट में से का परीक्षण और विकल्प बिंदु बनाता है, दूसरा परीक्षण रोक दिया जाता है, जिससे एल्गोरिदम के किसी भी चरण में बैकट्रैकिंग ट्री की केवल दो शाखाएं हों जिनका अभी भी परीक्षण किया जा रहा हो। इस प्रकार, किसी भी वेरिएबल के लिए दो परीक्षण करने में बिताया गया कुल समय इनपुट सूत्र के उन वेरिएबलों और खंडों की संख्या के समानुपाती होता है जिनके मान स्थायी रूप से निर्दिष्ट होते हैं। परिणामस्वरूप, एल्गोरिथ्म कुल मिलाकर रैखिक समय लेता है।<ref name="EIS76" />
@@ Line 82: / Line 82: @@
 {{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
+निर्देशित ग्राफ़ में दो शीर्षों को एक-दूसरे से शक्ति से जुड़ा हुआ माना जाता है यदि से दूसरे तक कोई निर्देशित पथ हो और इसके विपरीत। यह तुल्यता संबंध है, और ग्राफ़ के शीर्षों को दृढ़ता से जुड़े अवयवों , उपसमुच्चयों में विभाजित किया जा सकता है जिनके अंदर प्रत्येक दो शीर्ष दृढ़ता से जुड़े हुए हैं। [[गहराई-पहली खोज|डेप्थ -फर्स्ट सर्च]] के आधार पर ग्राफ़ के दृढ़ता से जुड़े अवयवों को खोजने के लिए अनेक कुशल रैखिक समय एल्गोरिदम हैं: टार्जन के दृढ़ता से जुड़े अवयव एल्गोरिदम<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.
   | last2 = Mehlhorn | first2 = K. | author2-link = Kurt Mehlhorn
@@ Line 102: / Line 102: @@
   | year = 2003}}.</ref> प्रत्येक एकल गहराई-पहली खोज करता है। कोसाराजू का एल्गोरिदम दो गहराई-पहली खोज करता है, किन्तु यह बहुत सरल है।
-निहितार्थ ग्राफ के संदर्भ में, जब भी शाब्दिक से दूसरे और इसके विपरीत निहितार्थ की श्रृंखला उपस्तिथ होती है, तो दो शाब्दिक ही दृढ़ता से जुड़े अवयव से संबंधित होते हैं। इसलिए, दिए गए 2-संतोषजनकता उदाहरण के लिए किसी भी संतोषजनक असाइनमेंट में दो शाब्दिकों का समान मान होना चाहिए। विशेष रूप से, यदि वेरिएबल और उसका निषेध दोनों ही शक्ति  से जुड़े अवयव से संबंधित हैं, तो उदाहरण को संतुष्ट नहीं किया जा सकता है, क्योंकि इन दोनों शाब्दिकों को समान मान निर्दिष्ट करना असंभव है। एस्पवॉल एट अल के रूप में दिखाया गया है, यह आवश्यक और पर्याप्त नियम है: 2-सीएनएफ सूत्र तभी संतोषजनक है जब कोई ऐसा वेरिएबल न हो जो इसके निषेध के समान शक्ति  से जुड़े अवयव से संबंधित हो जाते है ।<ref name="APT79"/>
+निहितार्थ ग्राफ के संदर्भ में, जब भी शाब्दिक से दूसरे और इसके विपरीत निहितार्थ की श्रृंखला उपस्तिथ होती है, तो दो शाब्दिक ही दृढ़ता से जुड़े अवयव से संबंधित होते हैं। इसलिए, दिए गए 2-संतोषजनकता उदाहरण के लिए किसी भी संतोषजनक असाइनमेंट में दो शाब्दिकों का समान मान होना चाहिए। विशेष रूप से, यदि वेरिएबल और उसका निषेध दोनों ही शक्ति से जुड़े अवयव से संबंधित हैं, तो उदाहरण को संतुष्ट नहीं किया जा सकता है, क्योंकि इन दोनों शाब्दिकों को समान मान निर्दिष्ट करना असंभव है। एस्पवॉल एट अल के रूप में दिखाया गया है, यह आवश्यक और पर्याप्त नियम है: 2-सीएनएफ सूत्र तभी संतोषजनक है जब कोई ऐसा वेरिएबल न हो जो इसके निषेध के समान शक्ति से जुड़े अवयव से संबंधित हो जाते है ।<ref name="APT79"/>
 यह तुरंत 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>
 *रिवर्स टोपोलॉजिकल ऑर्डर में प्रत्येक अवयव के लिए, यदि इसके वेरिएबल में पहले से ही सत्य असाइनमेंट नहीं हैं, तो अवयव में सभी शाब्दिक को सत्य पर सेट करें। इसके कारण पूरक अवयव के सभी अक्षर गलत पर सेट हो जाते हैं।
@@ Line 119: / Line 119: @@
 ===ज्यामितीय वस्तुओं का संघर्ष-मुक्त स्थान ===
-[[स्वचालित लेबल प्लेसमेंट]] समस्या के लिए अनेक स्पष्ट और अनुमानित एल्गोरिदम 2-संतोषजनकता पर आधारित हैं। यह समस्या किसी आरेख या मानचित्र की विशेषताओं पर पाठ्य लेबल लगाने से संबंधित है। सामान्यतः, प्रत्येक लेबल के लिए संभावित स्थानों का सेट अत्यधिक प्रतिबंधित होता है, जो न केवल मानचित्र द्वारा (प्रत्येक लेबल को उस सुविधा के पास होना चाहिए जिसे वह लेबल करता है, और अन्य सुविधाओं को अस्पष्ट नहीं करना चाहिए), किन्तु एक-दूसरे द्वारा: प्रत्येक दो लेबल को एक-दूसरे को ओवरलैप करने से बचना चाहिए, अन्यथा वह अस्पष्ट हो जाएंगे। सामान्यतः इन बाधाओं का पालन करने वाला लेबल प्लेसमेंट खोजता [[ एनपी कठिन |NP हार्ड]]  समस्या है। चूँकि , यदि प्रत्येक फीवेरिएबल में उसके लेबल के लिए केवल दो संभावित स्थान हैं (जैसे, फीवेरिएबल के बाईं और दाईं ओर विस्तार) तो लेबल प्लेसमेंट को बहुपद समय में हल किया जा सकता है। इस स्तिथि में, कोई 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>
+[[स्वचालित लेबल प्लेसमेंट]] समस्या के लिए अनेक स्पष्ट और अनुमानित एल्गोरिदम 2-संतोषजनकता पर आधारित हैं। यह समस्या किसी आरेख या मानचित्र की विशेषताओं पर पाठ्य लेबल लगाने से संबंधित है। सामान्यतः, प्रत्येक लेबल के लिए संभावित स्थानों का सेट अत्यधिक प्रतिबंधित होता है, जो न केवल मानचित्र द्वारा (प्रत्येक लेबल को उस सुविधा के पास होना चाहिए जिसे वह लेबल करता है, और अन्य सुविधाओं को अस्पष्ट नहीं करना चाहिए), किन्तु एक-दूसरे द्वारा: प्रत्येक दो लेबल को एक-दूसरे को ओवरलैप करने से बचना चाहिए, अन्यथा वह अस्पष्ट हो जाएंगे। सामान्यतः इन बाधाओं का पालन करने वाला लेबल प्लेसमेंट खोजता [[ एनपी कठिन |NP हार्ड]] समस्या है। चूँकि , यदि प्रत्येक फीवेरिएबल में उसके लेबल के लिए केवल दो संभावित स्थान हैं (जैसे, फीवेरिएबल के बाईं और दाईं ओर विस्तार) तो लेबल प्लेसमेंट को बहुपद समय में हल किया जा सकता है। इस स्तिथि में, कोई 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|फॉर्मैन |वैगनर|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>
@@ Line 125: / Line 125: @@
 अन्य ज्यामितीय प्लेसमेंट समस्याओं के लिए 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>
+{{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-संतोषजनक एल्गोरिदम का उपयोग करता है कि क्या उस जोड़ी को क्लस्टरिंग द्वारा अनुभव किया जा सकता है। व्यासों का अधिकतम योग ज्ञात करने के लिए कोई बाइनरी खोज कर सकता है जिसमें प्रत्येक चरण इस प्रकार का व्यवहार्यता परीक्षण होता है। यही दृष्टिकोण क्लस्टरिंग को खोजने के लिए भी कार्य करता है जो क्लस्टर व्यास के योग के अतिरिक्त अन्य संयोजनों को अनुकूलित करता है, और जो क्लस्टर के आकार को मापने के लिए इच्छानुसार असमानता संख्याओं (मीट्रिक स्थान में दूरी के अतिरिक्त ) का उपयोग करता है।<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>
@@ Line 133: / Line 133: @@
 ===शेड्यूलिंग===
-{{harvtxt|इवेन |इटाई|शमीर|1976}} कक्षा समय-निर्धारण के मॉडल पर विचार करें जिसमें छात्रों के प्रत्येक समूह को पढ़ाने के लिए n शिक्षकों का समूह निर्धारित किया जाना चाहिए। उस शिक्षक के प्रति सप्ताह घंटों की संख्या <math>i</math> समूह के साथ बिताता है जहाँ  <math>j</math> प्रविष्टि द्वारा वर्णित है और <math>R_{ij}</math> आव्युह का <math>R</math> समस्या के इनपुट के रूप में दिया गया है, और प्रत्येक शिक्षक के पास घंटों का सेट भी है जिसके समय वह शेड्यूल के लिए उपलब्ध रहता है। जैसा कि वह दिखाते हैं, समस्या NP-पूर्ण है, तथापि  प्रत्येक शिक्षक के पास अधिकतम तीन उपलब्ध घंटे हों, किन्तु इसे 2-संतोषजनकता के उदाहरण के रूप में हल किया जा सकता है जब प्रत्येक शिक्षक के पास केवल दो उपलब्ध घंटे हों। (केवल उपलब्ध घंटे वाले शिक्षकों को समस्या से आसानी से छुटकारा दिलाया जा सकता है।) इस समस्या में, प्रत्येक वेरिएबल <math>v_{ij}</math> उस शिक्षक के घंटे से मेल खाता है <math>i</math> समूह के साथ बिताना चाहिए जो की <math>j</math>, वेरिएबल के लिए असाइनमेंट निर्दिष्ट करता है कि क्या वह घंटा शिक्षक के उपलब्ध घंटों में से पहला या दूसरा है, और 2-संतोषजनकता खंड है जो दो प्रकार के किसी भी टकराव को रोकता है: शिक्षक को ही समय में एक-दूसरे को सौंपे गए दो समूह, या ही समय में दो शिक्षकों को निरुपित किय गए समूह होते है ।<ref name="EIS76"/>
+{{harvtxt|इवेन |इटाई|शमीर|1976}} कक्षा समय-निर्धारण के मॉडल पर विचार करें जिसमें छात्रों के प्रत्येक समूह को पढ़ाने के लिए n शिक्षकों का समूह निर्धारित किया जाना चाहिए। उस शिक्षक के प्रति सप्ताह घंटों की संख्या <math>i</math> समूह के साथ बिताता है जहाँ <math>j</math> प्रविष्टि द्वारा वर्णित है और <math>R_{ij}</math> आव्युह का <math>R</math> समस्या के इनपुट के रूप में दिया गया है, और प्रत्येक शिक्षक के पास घंटों का सेट भी है जिसके समय वह शेड्यूल के लिए उपलब्ध रहता है। जैसा कि वह दिखाते हैं, समस्या NP-पूर्ण है, तथापि प्रत्येक शिक्षक के पास अधिकतम तीन उपलब्ध घंटे हों, किन्तु इसे 2-संतोषजनकता के उदाहरण के रूप में हल किया जा सकता है जब प्रत्येक शिक्षक के पास केवल दो उपलब्ध घंटे हों। (केवल उपलब्ध घंटे वाले शिक्षकों को समस्या से आसानी से छुटकारा दिलाया जा सकता है।) इस समस्या में, प्रत्येक वेरिएबल <math>v_{ij}</math> उस शिक्षक के घंटे से मेल खाता है <math>i</math> समूह के साथ बिताना चाहिए जो की <math>j</math>, वेरिएबल के लिए असाइनमेंट निर्दिष्ट करता है कि क्या वह घंटा शिक्षक के उपलब्ध घंटों में से पहला या दूसरा है, और 2-संतोषजनकता खंड है जो दो प्रकार के किसी भी टकराव को रोकता है: शिक्षक को ही समय में एक-दूसरे को सौंपे गए दो समूह, या ही समय में दो शिक्षकों को निरुपित किय गए समूह होते है ।<ref name="EIS76"/>
-{{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>
+{{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>
@@ Line 142: / Line 142: @@
 [[File:Nonogram_wiki.svg|thumb|नॉनोग्राम पहेली का उदाहरण.]][[टोमोग्राफी]] उनके क्रॉस-सेक्शन से आकृतियों को पुनर्प्राप्त करने की प्रक्रिया है। [[असतत टोमोग्राफी]] में, समस्या का सरलीकृत संस्करण जिसका अधिकांशतः अध्ययन किया गया है, पुनर्प्राप्त किया जाने वाला आकार [[पॉलीओमिनो]] (द्वि-आयामी वर्ग जालक में वर्गों का उपसमूह) है, और क्रॉस-सेक्शन जालक की व्यक्तिगत पंक्तियों और स्तंभों में वर्गों के सेट के बारे में समग्र जानकारी प्रदान करते हैं। उदाहरण के लिए, लोकप्रिय [[पहेलियाँ खेलना]] पहेलियों में, जिन्हें संख्याओं या ग्रिडलर द्वारा पेंट के रूप में भी जाना जाता है, निर्धारित किए जाने वाले वर्गों का सेट बाइनरी छवि में डार्क [[ पिक्सेल |पिक्सेल]] का प्रतिनिधित्व करता है, और पहेली सॉल्वर को दिया गया इनपुट उसे बताता है कि छवि की प्रत्येक पंक्ति या स्तम्भ में डार्क पिक्सल के कितने निरंतर ब्लॉक सम्मिलित करने हैं, और उनमें से प्रत्येक ब्लॉक कितना लंबा होना चाहिए। डिजिटल टोमोग्राफी के अन्य रूपों में, प्रत्येक पंक्ति या स्तंभ के बारे में और भी कम जानकारी दी जाती है: वर्गों के ब्लॉक की संख्या और लंबाई के अतिरिक्त केवल वर्गों की कुल संख्या। समस्या का समतुल्य संस्करण यह है कि हमें आव्युह की प्रत्येक पंक्ति और प्रत्येक स्तम्भ में केवल मानों के योग को देखते हुए दिए गए [[0-1 मैट्रिक्स|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 पहचान आव्युह के रूप में किसी भी उपआव्युह को समाधान की शुद्धता को प्रभावित किए बिना पूरक किया जा सकता है। इसलिए, शोधकर्ताओं ने पुनर्निर्माण किए जाने वाले आकार पर बाधाओं की खोज की है जिसका उपयोग समाधानों के स्थान को प्रतिबंधित करने के लिए किया जा सकता है। उदाहरण के लिए, कोई यह मान सकता है कि आकृति जुड़ी हुई है; चूँकि, यह परीक्षण करना कि क्या कोई कनेक्टेड समाधान उपस्तिथ है, NP-पूर्ण है।<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|क्रोबक|ड्यूर|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=बटेनबर्ग|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>
+यद्यपि पंक्ति और स्तंभ के योग वाले आव्युह को खोजने के लिए बहुपद समय एल्गोरिदम उपस्तिथ हैं,<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 पहचान आव्युह के रूप में किसी भी उपआव्युह को समाधान की शुद्धता को प्रभावित किए बिना पूरक किया जा सकता है। इसलिए, शोधकर्ताओं ने पुनर्निर्माण किए जाने वाले आकार पर बाधाओं की खोज की है जिसका उपयोग समाधानों के स्थान को प्रतिबंधित करने के लिए किया जा सकता है। उदाहरण के लिए, कोई यह मान सकता है कि आकृति जुड़ी हुई है; चूँकि, यह परीक्षण करना कि क्या कोई कनेक्टेड समाधान उपस्तिथ है, NP-पूर्ण है।<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|क्रोबक|ड्यूर|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=बटेनबर्ग|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>
@@ Line 168: / Line 168: @@
 ===अन्य अनुप्रयोग===
--संतोषजनकता को [[अप्रत्यक्ष ग्राफ]] को पहचानने की समस्याओं पर भी प्रयुक्त किया गया है जिन्हें [[स्वतंत्र सेट (ग्राफ़ सिद्धांत)]] और [[पूर्ण द्विदलीय ग्राफ]] की छोटी संख्या में विभाजित किया जा सकता है,<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>
+-संतोषजनकता को [[अप्रत्यक्ष ग्राफ]] को पहचानने की समस्याओं पर भी प्रयुक्त किया गया है जिन्हें [[स्वतंत्र सेट (ग्राफ़ सिद्धांत)]] और [[पूर्ण द्विदलीय ग्राफ]] की छोटी संख्या में विभाजित किया जा सकता है,<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 227: / Line 227: @@
 ===संतोषजनक असाइनमेंट की संख्या की गिनती===
-##2एसएटी  किसी दिए गए 2-सीएनएफ सूत्र में संतोषजनक असाइनमेंट की संख्या की गणना करने की समस्या है। यह गिनती समस्या #पी-पूर्ण है,<ref>{{citation
+##2एसएटी किसी दिए गए 2-सीएनएफ सूत्र में संतोषजनक असाइनमेंट की संख्या की गणना करने की समस्या है। यह गिनती समस्या #पी-पूर्ण है,<ref>{{citation
   | last1 = Valiant | first1 = Leslie G. | author-link = Leslie Valiant
   | year = 1979
@@ Line 235: / Line 235: @@
   | pages= 410–421
   | doi = 10.1137/0208032
-  | issue = 3}}</ref> जिसका अर्थ है कि यह बहुपद समय में हल करने योग्य नहीं है जब तक कि P = NP न हो। इसके अतिरिक्त , #2एसएटी  के लिए कोई पूरी तरह से बहुपद यादृच्छिक सन्निकटन योजना नहीं है जब तक कि NP = RP न हो और यह तब भी प्रयुक्त होता है जब इनपुट मोनोटोन 2-CNF फ़ार्मुलों तक सीमित होता है, यानी, 2-सीएनएफ सूत्र जिसमें प्रत्येक शाब्दिक एक चर की सकारात्मक घटना होती है<ref>{{citation
+  | issue = 3}}</ref> जिसका अर्थ है कि यह बहुपद समय में हल करने योग्य नहीं है जब तक कि P = NP न हो। इसके अतिरिक्त , #2एसएटी के लिए कोई पूरी तरह से बहुपद यादृच्छिक सन्निकटन योजना नहीं है जब तक कि NP = RP न हो और यह तब भी प्रयुक्त होता है जब इनपुट मोनोटोन 2-CNF फ़ार्मुलों तक सीमित होता है, यानी, 2-सीएनएफ सूत्र जिसमें प्रत्येक शाब्दिक एक चर की सकारात्मक घटना होती है<ref>{{citation
   | last1 = Welsh | first1 = Dominic | author1-link = Dominic Welsh
   | last2 = Gale | first2 = Amy
@@ Line 265: / Line 265: @@
   }}.</ref>
-यदि अद्वितीय गेम का अनुमान सत्य है, तो बहुपद समय में 0.943... से उत्तम  अनुमानित अनुपात के साथ, मैक्स 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> अशक्त धारणा के अनुसार कि P बनाम NP समस्या या  P ≠ NP, समस्या को केवल 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>
+यदि अद्वितीय गेम का अनुमान सत्य है, तो बहुपद समय में 0.943... से उत्तम अनुमानित अनुपात के साथ, मैक्स 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> अशक्त धारणा के अनुसार कि P बनाम NP समस्या या P ≠ NP, समस्या को केवल 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>
 विभिन्न लेखकों ने मैक्स-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>
@@ Line 272: / Line 272: @@
 भारित 2-संतोषजनकता समस्या (W2सैट ) में, इनपुट है जो <math>n</math>-परिवर्तनीय 2एसएटी उदाहरण और पूर्णांक {{math|''k''}}, और समस्या यह तय करना है कि वास्तव में कोई संतोषजनक असाइनमेंट उपस्तिथ है या नहीं जिससे कि यह पता चलता कि {{math|''k''}} वेरिएबल सत्य हैं।<ref name=fg06/>
-W2सैट समस्या में विशेष स्तिथि के रूप में सेट खोजने की [[वर्टेक्स कवर समस्या]] सम्मिलित है जो की  {{mvar|k}} शीर्ष जो किसी दिए गए अप्रत्यक्ष ग्राफ़ के सभी किनारों को साथ छूते हैं। शीर्ष कवर समस्या के किसी भी उदाहरण के लिए, कोई ग्राफ़ के प्रत्येक शीर्ष के लिए वेरिएबल के साथ समतुल्य W2सैट समस्या का निर्माण कर सकता है। प्रत्येक किनारा ''u'' ∨ ''v'' को 2एसएटी खंड द्वारा दर्शाया जा सकता है {{math|''u'' ∨ ''v''}} जिसे दोनों में से किसी को सम्मिलित करके ही संतुष्ट किया जा सकता है जिसमे यह  {{mvar|u}} या {{mvar|v}} समाधान के वास्तविक वेरिएबलों के मध्य फिर परिणामी 2एसएटी सूत्र के संतोषजनक उदाहरण वर्टेक्स कवर समस्या के समाधान को एन्कोड करते हैं, और इसके साथ संतोषजनक असाइनमेंट होता है {{math|''k''}} सत्य वेरिएबल यदि और केवल यदि कोई शीर्ष आवरण है {{math|''k''}} शिखर. इसलिए, वर्टेक्स कवर की तरह, W2सैट NP-पूर्ण है।
+W2सैट समस्या में विशेष स्तिथि के रूप में सेट खोजने की [[वर्टेक्स कवर समस्या]] सम्मिलित है जो की {{mvar|k}} शीर्ष जो किसी दिए गए अप्रत्यक्ष ग्राफ़ के सभी किनारों को साथ छूते हैं। शीर्ष कवर समस्या के किसी भी उदाहरण के लिए, कोई ग्राफ़ के प्रत्येक शीर्ष के लिए वेरिएबल के साथ समतुल्य W2सैट समस्या का निर्माण कर सकता है। प्रत्येक किनारा ''u'' ∨ ''v'' को 2एसएटी खंड द्वारा दर्शाया जा सकता है {{math|''u'' ∨ ''v''}} जिसे दोनों में से किसी को सम्मिलित करके ही संतुष्ट किया जा सकता है जिसमे यह {{mvar|u}} या {{mvar|v}} समाधान के वास्तविक वेरिएबलों के मध्य फिर परिणामी 2एसएटी सूत्र के संतोषजनक उदाहरण वर्टेक्स कवर समस्या के समाधान को एन्कोड करते हैं, और इसके साथ संतोषजनक असाइनमेंट होता है {{math|''k''}} सत्य वेरिएबल यदि और केवल यदि कोई शीर्ष आवरण है {{math|''k''}} शिखर. इसलिए, वर्टेक्स कवर की तरह, W2सैट NP-पूर्ण है।
 इसके अतिरिक्त , पैरामीटरयुक्त सम्मिश्र ता में W2सैट प्राकृतिक W(1)|W[1]-पूर्ण समस्या प्रदान करता है,<ref name=fg06>{{Citation

Anonymous

Search

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

Namespaces

More

Page actions

Revision as of 10:06, 7 August 2023

Contents

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

एल्गोरिदम

संकल्प और सकर्मक समापन

सीमित बैकट्रैकिंग

शक्ति से जुड़े अवयव

अनुप्रयोग

ज्यामितीय वस्तुओं का संघर्ष-मुक्त स्थान

डेटा क्लस्टरिंग

शेड्यूलिंग

असतत टोमोग्राफी

नाम बदलने योग्य हॉर्न संतुष्टि

अन्य अनुप्रयोग

सम्मिश्रता और विस्तार

एनएल-पूर्णता

सभी समाधानों का समुच्चय

संतोषजनक असाइनमेंट की संख्या की गिनती

यादृच्छिक 2-संतोषजनक उदाहरण

अधिकतम-2-संतोषजनकता

भारित-2-संतोषजनकता

मात्राबद्ध बूलियन सूत्र

अनेक-मूल्यवान तर्क

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Revision as of 10:06, 7 August 2023

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

एल्गोरिदम

संकल्प और सकर्मक समापन

सीमित बैकट्रैकिंग

शक्ति से जुड़े अवयव

अनुप्रयोग

ज्यामितीय वस्तुओं का संघर्ष-मुक्त स्थान

डेटा क्लस्टरिंग

शेड्यूलिंग

असतत टोमोग्राफी

नाम बदलने योग्य हॉर्न संतुष्टि

अन्य अनुप्रयोग

सम्मिश्रता और विस्तार

एनएल-पूर्णता

सभी समाधानों का समुच्चय

संतोषजनक असाइनमेंट की संख्या की गिनती

यादृच्छिक 2-संतोषजनक उदाहरण

अधिकतम-2-संतोषजनकता

भारित-2-संतोषजनकता

मात्राबद्ध बूलियन सूत्र

अनेक-मूल्यवान तर्क

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Categories