2-संतोषजनकता

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

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

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

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

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

File:Implication graph.svg

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

इस प्रकार के विशेष प्रतिबंधित रूप के साथ बूलियन अभिव्यक्ति का उपयोग करके 2-संतुष्टि समस्या का वर्णन किया जा सकता है। यह क्लॉज (तर्क) का तार्किक संयोजन (एक बूलियन और ऑपरेशन) है, जहां प्रत्येक क्लॉज दो वेरिएबल या ऋणात्मक वेरिएबल का वियोजन (एक बूलियन या ऑपरेशन) है। इस सूत्र में आने वाले वेरिएबल या उनके निषेधन को शाब्दिक (गणितीय तर्क) कहा जाता है। उदाहरण के लिए, निम्नलिखित सूत्र संयोजक सामान्य रूप में है, जिसमें सात वेरिएबल , ग्यारह उपवाक्य और 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 प्रति खंड शाब्दिकों की संख्या को दर्शाता है, और सीएनएफ संयोजक सामान्य रूप के लिए है, विच्छेदन के संयोजन के रूप में प्रकार की बूलियन अभिव्यक्ति है। कैलिफ़ोर्निया विश्वविद्यालय, डेविस के गणितज्ञ मेल्वेन आर. क्रॉम के कार्य के पश्चात, उन्हें क्रॉम सूत्र भी कहा जाता है, जिनका 1967 का पेपर 2-संतुष्टि समस्या पर सबसे शुरुआती कार्यों में से था।

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

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

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

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

एल्गोरिदम

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

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

क्रोम (1967) 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$ का अनुमान लगाना होता है .

क्रॉम लिखते हैं कि सूत्र सुसंगत है यदि इस अनुमान नियम को बार-बार प्रयुक्त करने से दोनों खंड उत्पन्न नहीं हो सकते हैं $(x\lor x)$ और $(\lnot x\lor \lnot x)$, किसी भी वेरिएबल के लिए $x$. जैसा कि उन्होंने साबित किया है, 2-सीएनएफ फॉर्मूला तभी संतोषजनक है जब यह सुसंगत हो। क्योंकि, यदि कोई सूत्र सुसंगत नहीं है, तो दोनों खंडों को संतुष्ट करना संभव नहीं है $(x\lor x)$ और $(\mathrm{\neg <!--\; \neg \; -->}x\vee <!--\; \vee \; -->$