MAX-3SAT
मैक्स-3सैट कंप्यूटर विज्ञान के कम्प्यूटेशनल जटिलता उपक्षेत्र में एक समस्या है। यह बूलियन संतुष्टि समस्या (एस. ए. टी.) को सामान्यीकृत करता है जो जटिलता सिद्धांत में विचार की जाने वाली एक निर्णय समस्या है। इसे इस प्रकार परिभाषित किया गया हैः 3-सी. एन. एफ. सूत्र को देखते हुए (अर्थात। प्रति खंड अधिकतम 3 चर के साथ), एक ऐसा कार्य खोजें जो खंडों की सबसे बड़ी संख्या को संतुष्ट करता हो। MAX-3SAT जटिलता वर्ग MAXSNP के लिए एक विहित पूर्ण समस्या है (पापाडिमिट्रियो pg में पूरी तरह से दिखाई गई है। 314)। सन्निकटन मैक्स-3सैट का निर्णय संस्करण एनपी-पूर्ण है। इसलिए, एक बहुपद-समय समाधान केवल तभी प्राप्त किया जा सकता है जब पी = एनपी। 2 के कारक के भीतर एक अनुमान इस सरल एल्गोरिथ्म के साथ प्राप्त किया जा सकता है, हालांकिः उस समाधान को आउटपुट करें जिसमें अधिकांश खंड संतुष्ट हैं, जब या तो सभी चर = TRUE या सभी चर = FALSE। प्रत्येक खंड दो समाधानों में से एक से संतुष्ट होता है, इसलिए एक समाधान कम से कम आधे खंडों को संतुष्ट करता है। कार्लॉफ-ज़विक एल्गोरिथ्म बहुपद-समय में चलता है और खंडों के ≤7/8 को संतुष्ट करता है। जबकि यह एल्गोरिथ्म यादृच्छिक है, इसे उपयोग करके विकृत किया जा सकता है, उदाहरण के लिए, एक ही सन्निकटन गारंटी के साथ एक निर्धारक (बहुपद-समय) एल्गोरिथ्म प्राप्त करने की तकनीक। प्रमेय 1 (अप्रासंगिकता) पी. सी. पी. प्रमेय का तात्पर्य है कि एक ε> 0 ऐसा मौजूद है कि मैक्स-3सैट का (1-ε)-सन्निकटन एन. पी.-कठोर है। प्रमाणः पीसीपी प्रमेय द्वारा कोई भी एनपी-पूर्ण समस्या। एक 3-सी. एन. एफ. सूत्र का निर्माण किया जाता है ताकि x ω L ωx संतोषजनक हो x ω L ωx के (1-ω) m खंडों से अधिक संतोषजनक न हों। सत्यापनकर्ता V सभी आवश्यक बिट्स को एक साथ पढ़ता है। गैर-अनुकूली प्रश्न करता है। यह वैध है क्योंकि प्रश्नों की संख्या स्थिर रहती है। मान लीजिए कि q प्रश्नों की संख्या है। सभी यादृच्छिक तारों की गणना करते हुए, हम प्रत्येक तार की लंबाई से पॉली (x) तार प्राप्त करते हैं। प्रत्येक Ri V के लिए q स्थिति i1,., iq और एक बूलियन फलन fR: {0,1} q-> {0,1} का चयन करता है और स्वीकार करता है यदि और केवल यदि fR (π (i1,., iq))। यहाँ π ओरेकल से प्राप्त प्रमाण को संदर्भित करता है। इसके बाद हम इसका अनुकरण करने के लिए एक बूलियन सूत्र खोजने की कोशिश करते हैं। हम बूलियन चर x1,., xl का परिचय देते हैं, जहाँ l प्रमाण की लंबाई है। यह प्रदर्शित करने के लिए कि सत्यापनकर्ता संभावित बहुपद-समय में चलता है, हमें संतोषजनक खंडों की संख्या और सत्यापनकर्ता द्वारा स्वीकार की जाने वाली संभावना के बीच एक पत्राचार की आवश्यकता है। प्रत्येक आर के लिए, 2क्यू एस. ए. टी. खंडों का उपयोग करके एफ. आर. (xi1,., xiq) का प्रतिनिधित्व करने वाले खंड जोड़ें। लंबाई q के खंडों को नए (सहायक) चर जोड़कर लंबाई 3 में परिवर्तित किया जाता है। x2 * x10 * x11 * x12 = (x2 * x10 * yR) (R * x11 * x12)। इसके लिए अधिकतम q2q 3-SAT खंडों की आवश्यकता होती है। यदि z ω L है तो एक प्रमाण π है कि Vπ (z) प्रत्येक Ri के लिए स्वीकार करता है। यदि xi = π (i) और सहायक चर सही ढंग से जोड़े जाते हैं तो सभी खंड संतुष्ट होते हैं। यदि इनपुट z′L है तो x1,., xl और yR के प्रत्येक असाइनमेंट के लिए, संबंधित प्रमाण π (i) = xi सत्यापनकर्ता को सभी R ω {0,1} r (|z।) के आधे के लिए अस्वीकार करने का कारण बनता है। प्रत्येक आर के लिए, एफआर का प्रतिनिधित्व करने वाला एक खंड विफल हो जाता है। इसलिए, खंडों का एक अंश विफल हो जाता है। यह निष्कर्ष निकाला जा सकता है कि यदि यह प्रत्येक एन. पी.-पूर्ण समस्या के लिए लागू होता है तो पी. सी. पी. प्रमेय सही होना चाहिए। प्रमेय 2 उस्ताद प्रमेय 1 की तुलना में एक कठिन परिणाम प्रदर्शित करता है। ε के लिए सबसे अच्छा ज्ञात मान। वह 3-सैट के लिए एक पी. सी. पी. सत्यापनकर्ता का निर्माण करता है जो प्रमाण से केवल 3 बिट पढ़ता है। प्रत्येक ε> 0 के लिए, 3-SAT के लिए एक पी. सी. पी.-सत्यापनकर्ता M होता है जो लंबाई की एक यादृच्छिक स्ट्रिंग r को पढ़ता है और प्रमाण π और एक बिट बी. आर. में क्वेरी स्थितियों आई. आर., जे. आर., के. आर. की गणना करता है। यह तभी स्वीकार करता है जब 'π (ir) ωπ (jr) ωπ (kr) = br. सत्यापनकर्ता में पूर्णता (1 − ε) और ध्वनि (पी. सी. पी. (जटिलता) का संदर्भ लें) हो। यदि इन दो समीकरणों में से पहले को हमेशा की तरह "= 1" के बराबर किया गया था, तो कोई भी रैखिक समीकरणों की एक प्रणाली को हल करके एक प्रमाण पा सकता है (MAX-3LIN-EQN देखें) जिसका अर्थ है P = NP। यदि z ω L है, तो खंडों का एक अंश (1 − ε) संतुष्ट होता है। यदि z′L, तो R के (1/2−ε) अंश के लिए, 1/4 खंड विरोधाभासी हैं। यह सन्निकटन अनुपात की कठोरता को साबित करने के लिए पर्याप्त है संबंधित समस्याएं MAX-3SAT (B) MAX-3SAT का प्रतिबंधित विशेष मामला है जहां प्रत्येक चर अधिकतम B खंडों में होता है। पी. सी. पी. प्रमेय सिद्ध होने से पहले, पापाडिमित्रिउ और यन्नाकाकिस ने दिखाया कि कुछ निश्चित स्थिरांक बी के लिए, यह समस्या मैक्स एस. एन. पी.-हार्ड है। नतीजतन, पी. सी. पी. प्रमेय के साथ, यह ए. पी. एक्स-हार्ड भी है। यह उपयोगी है क्योंकि मैक्स-3सैट (बी) का उपयोग अक्सर पी. टी. ए. एस.-संरक्षित कमी प्राप्त करने के लिए इस तरह से किया जा सकता है कि मैक्स-3सैट नहीं कर सकता है। बी के स्पष्ट मूल्यों के प्रमाणों में शामिल हैंः सभी बी ≤ 13, संजीव अरोड़ा, "सबूतों की संभावित जाँच और सन्निकटन समस्याओं की कठोरता", अगस्त 1994 में सी. एस. डिवीजन, यू. सी. बर्कले में प्रस्तुत एक शोध प्रबंध का संशोधित संस्करण। CS-TR-476-94। धारा 7.2. और सभी बी ≤ 3 (जो सबसे अच्छा संभव है)। इसके अलावा, हालांकि निर्णय समस्या 2सैट बहुपद समय में हल करने योग्य है, मैक्स-2सैट (3) भी एपीएक्स-हार्ड है। बी के फलन के रूप में मैक्स-3एसएटी (बी) के लिए सबसे अच्छा संभव सन्निकटन अनुपात कम से कम और अधिक से अधिक है, जब तक कि एनपी = आरपी न हो। बी के कुछ मूल्यों के लिए अनुमानितता स्थिरांक पर कुछ स्पष्ट सीमाएँ ज्ञात हैं। बर्मन, कार्पिंस्की और स्कॉट ने साबित किया कि मैक्स-3सैट के "महत्वपूर्ण" उदाहरणों के लिए जिसमें प्रत्येक शाब्दिक ठीक दो बार होता है, और प्रत्येक खंड बिल्कुल आकार 3 का होता है, समस्या कुछ स्थिर कारक के लिए अनुमानित कठिन है। मैक्स-एकसैट, मैक्स-3सैट का एक मानकीकृत संस्करण है जहाँ प्रत्येक खंड में ठीक-ठीक अक्षर होते हैं, के "≤3 के लिए। कोडिंग सिद्धांत के विचारों का उपयोग करके इसे सन्निकटन अनुपात के साथ कुशलता से अनुमानित किया जा सकता है। यह साबित किया गया है कि मैक्स-3सैट के यादृच्छिक उदाहरणों को कारक के भीतर अनुमानित किया जा सकता है। कैलिफोर्निया विश्वविद्यालय, बर्कले से संदर्भ व्याख्यान नोट्स कोडिंग सिद्धांत बफ़ेलो संतुष्टि समस्याओं एनपी-कठिन समस्याओं में विश्वविद्यालय में नोट करता है