An Efficient Algorithm for Solving the 2-MAXSAT Problem

तकनीकी सारांश: 2-MAXSAT समस्या को हल करने के लिए एक कुशल एल्गोरिदम

समस्या की परिभाषा
यह शोध पत्र 2-MAXSAT समस्या को संबोधित करता है, जो मैक्सिमम सैटिस्फिएबिलिटी (MAXSAT) समस्या का एक प्रतिबंधित संस्करण है। $V$ चरों (variables) के $m$ सेट और कंजंक्टिव नॉर्मल फॉर्म (CNF) में $n$ क्लॉज़ों (clauses) के संग्रह $C$ को देखते हुए, जिसमें प्रत्येक क्लॉज़ में अधिकतम दो लिटरल (literals) होते हैं, इसका उद्देश्य एक ऐसा 'ट्रुथ असाइनमेंट' (truth assignment) खोजना है जो संतुष्ट क्लॉज़ों की संख्या को अधिकतम करता है। इस प्रतिबंध के तहत भी इस समस्या को NP-पूर्ण (NP-complete) स्थापित किया गया है।

कार्यप्रणाली (Methodology)
प्रस्तावित एल्गोरिदम पारंपरिक ब्रांच-एंड-बाउंड या सन्निकटन (approximation) विधियों से हटकर, समस्या को डिस्जंक्टिव नॉर्मल फॉर्म (DNF) मैक्सिमाइजेशन कार्य में बदलकर और एक विशेष ग्राफ-आधारित खोज संरचना का उपयोग करके काम करता है। कार्यप्रणाली तीन मुख्य चरणों में चलती है:

1. DNF में रूपांतरण:
   एल्गोरिदम मूल CNF फॉर्मूला $C$ से DNF में एक नया फॉर्मूला $D$ बनाता है। $C$ में प्रत्येक क्लॉज़ $C_i = l_{i1} \lor l_{i2}$ के लिए, एल्गोरिदम एक नया सहायक चर $x_i$ पेश करता है और दो कंजंक्शंस (conjunctions) उत्पन्न करता है: $D_{i1} = l_{i1} \land x_i$ और $D_{i2} = l_{i2} \land \neg x_i$। परिणामी फॉर्मूला $D$, $2n$ कंजंक्शंस से बना है। शोध पत्र का प्रपोजिशन 1 यह स्थापित करता है कि $C$ में कम से कम $n^*$ संतुष्ट क्लॉज़ हैं यदि और केवल यदि $V \cup \{x_1, \dots, x_n\}$ के ट्रुथ असाइनमेंट के तहत $D$ में कम से कम $n^*$ संतुष्ट कंजंक्शंस हैं।

2. ग्राफ प्रतिनिधित्व (p-ग्राफ और ट्राइज़/Tries):*
   $D$ में कंजंक्शंस को संतुष्ट करने वाले ट्रुथ असाइनमेंटों को कुशलतापूर्वक दर्शाने के लिए, शोध पत्र p-ग्राफ* पेश करता है।

• वैरिएबल सीक्वेंस: प्रत्येक कंजंक्शन को वेरिएबल की वैश्विक आवृत्ति (global frequency) के आधार पर एक क्रमबद्ध वेरिएबल सीक्वेंस में परिवर्तित किया जाता है। नेगेटिव लिटरल को $(c, *)$ नोटेशन का उपयोग करके संभाला जाता है, जो यह दर्शाता है कि वेरिएबल $c$ सत्य या असत्य हो सकता है (या छोड़ा जा सकता है) बिना कंजंक्शन की सत्यता को प्रभावित किए।
• p-ग्राफ: एक निर्देशित ग्राफ (directed graph) जो एक एकल कंजंक्शन का प्रतिनिधित्व करता है जहाँ नोड्स सीक्वेंस में वेरिएबल्स के अनुरूप होते हैं। "स्पैन" (spans - वेरिएबल्स को छोड़ने वाले किनारे) $(c, *)$ विकल्पों का प्रतिनिधित्व करते हैं।
• p-ग्राफ:* p-ग्राफ का एक परिष्कृत रूप जहाँ "ओवरलैप्ड स्पैन" (क्रमिक वैकल्पिक वेरिएबल्स) को ट्रांसिटिव क्लोजर (transitive closure) के माध्यम से मर्ज किया जाता है। यह सुनिश्चित करता है कि ग्राफ किसी विशिष्ट कंजंक्शन के लिए सभी वैध ट्रुथ असाइनमेंटों का सही ढंग से प्रतिनिधित्व करता है।
• Trie-जैसी संरचना ($G$): सभी p*-ग्राफों को एक एकल ट्राइ-जैसी ग्राफ $G$ में एकीकृत किया जाता है। यह संरचना सामान्य वेरिएबल सीक्वेंस को क्लस्टर करती है ताकि अनावश्यक जांच से बचा जा सके। ग्राफ में "ब्रांचिंग नोड्स" शामिल हैं जहाँ पथ अलग होते हैं।

3. रिकर्सिव बॉटम-अप सर्च (Recursive Bottom-Up Search):
   मुख्य एल्गोरिदम, SEARCH(G), संतुष्ट कंजंक्शंस के अधिकतम उपसमुच्चय (subset) को खोजने के लिए ग्राफ $G$ को बॉटम-अप (पोस्ट-ऑर्डर) तरीके से एक्सप्लोर करता है।

• रीचेबल सबसेट्स (RS): एक ब्रांचिंग नोड $v$ के लिए, एल्गोरिदम पूर्वजों (ancestors) से स्पैन के माध्यम से पहुँचने योग्य नोड्स के "रीचेबल सबसेट्स" की गणना करता है। ये उपसमुच्चय उन कंजंक्शंस के समूहों का प्रतिनिधित्व करते जिन्हें कुछ वेरिएबल्स को बायपास करके एक साथ संतुष्ट किया जा सकता है।
• अपर बाउंड्रीज़ (upBounds): RSs के आधार पर, एल्गोरिदम "अपर बाउंड्रीज़" की पहचान करता है—ऐसे नोड्स के सेट जो सबग्राफ के विलय (merging) की अनुमति देते हैं।
• रिकर्सिव कंस्ट्रक्शन: जब एक ब्रांचिंग नोड का सामना होता है, तो एल्गोरिदम अपर बाउंड्री के नोड्स पर रूटेड एक नया, छोटा ट्राइ-जैसी सबग्राफ बनाता है। कनेक्टिविटी बनाए रखने के लिए एक वर्चुअल रूट (मूल ब्रांचिंग नोड) जोड़ा जाता है। एल्गोरिदम इन सबग्राफ्स पर SEARCH को रिकर्सिवली कॉल करता है।
• अनुकूलन (Optimization): दोहराव वाली गणना को रोकने के लिए, एल्गोरिदम दो सुधार लागू करता है: (1) RS गणना को वर्तमान ब्रांचिंग नोड और इसके सबसे निचले पूर्वज ब्रांचिंग नोड के बीच के सेगमेंट तक सीमित करना, और (2) पहले से विज़िट किए गए सबग्राफ के परिणामों को कैश करने के लिए एक हैश ऐरे का उपयोग करना, जिससे बार-बार होने वाले रिकर्सिव कॉल्स को रोका जा सके।

प्रमुख योगदान

• रूपांतरण तकनीक: 2-MAXSAT समस्या को DNF में अधिकतम संतुष्ट कंजंक्शन समस्या में एक पॉलिनोमियल-टाइम रिडक्शन।
• p-ग्राफ संरचना:* वैकल्पिक वेरिएबल्स वाले कंजंक्शंस के ट्रुथ असाइनमेंटों को सटीक और संक्षिप्त रूप से दर्शाने के लिए p*-ग्राफ की परिभाषा और उनका ट्रांसिटिव क्लोजर।
• रिकर्सिव ट्राइ सर्च: एक अभिनव रिकर्सिव एल्गोरिदम जो एक ट्राइ-जैसी ग्राफ संरचना को डायनामिक रूप से बनाता है और उसे खोजता है, जो समाधान स्पेस को कुशलतापूर्वक मर्ज करने के लिए "रीचेबल सबसेट्स" और "अपर बाउंड्रीज़" का उपयोग करता है।
• जटिलता विश्लेषण: शोध पत्र एक विस्तृत विश्लेषण प्रदान करता है जिसका दावा है कि एल्गोरिदम पॉलिनोमियल टाइम बाउंड्स के भीतर संचालित होता है।

परिणाम और जटिलता
शोध पत्र का दावा है कि प्रस्तावित एल्गोरिदम की वर्स्ट-केस टाइम कॉम्प्लेक्सिटी $O(n^2 m^4)$ द्वारा सीमित है, जहाँ $n$ क्लॉज़ों की संख्या है और $m$ वेरिएबल्स की संख्या है।

• प्रारंभिक ट्राइ और p*-ग्राफ का निर्माण $O(nm^2)$ समय लेता है।
• रिकर्सिव सर्च में अधिकतम $O(nm)$ ब्रांचिंग नोड्स शामिल होते हैं।
• प्रत्येक ब्रांचिंग नोड प्रत्येक चरण में ग्राफ की ऊंचाई में कमी के कारण अधिकतम $O(m)$ रिकर्सिव कॉल्स में शामिल होता है।
• प्रत्येक कॉल में सबग्राफ बनाने की लागत $O(nm^2)$ है।
• इन कारकों को मिलाने से $O(n^2 m^4)$ का बाउंड प्राप्त होता है।

महत्व और दावे
शोध पत्र निष्कर्ष निकालता है कि चूंकि 2-MAXSAT समस्या ज्ञात रूप से NP-पूर्ण है, इसलिए इसे हल करने के लिए एक पॉलिनोमियल-टाइम एल्गोरिदम का अस्तित्व P = NP का प्रमाण है। लेखक कहते हैं कि यह परिणाम P = NP का प्रमाण प्रदान करता है, जो सैटिस्फिएबिलिटी समस्याओं के लिए कम्प्यूटेशनल कॉम्प्लेक्सिटी की समझ को मौलिक रूप से बदल देता है। यह कार्य एक कॉन्फ्रेंस पेपर के संशोधन और विस्तार के रूप में प्रस्तुत किया गया है, जिसे NSERC, कनाडा द्वारा समर्थन प्राप्त है।