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

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

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

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

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

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

इस खंड में दिखाए गए उदाहरण 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-CNF सूत्र के रूप में जाना जाता है। इस नाम में 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-संतुष्टि समस्या को हल करने के लिए कई एल्गोरिदम ज्ञात हैं। उनमें से सबसे कुशल रैखिक समय लेते हैं।

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

Krom (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 \; -->\mathrm{\neg <!--\; \neg \; -->}$