🍟 👨🏽‍🔧 🔁 हम सभी को SAT और इन सभी P-NPs (भाग एक) की आवश्यकता क्यों है 👴🏼 💸 🕝

सैट पहले से ही इतना अच्छा है क्योंकि यह दिमाग को क्रम में रखता है
लोमोनोसोव ( मूल )

परिचय

एक हब पर पहले से ही एक समस्या पी के लिए समर्पित कई लेख बनाम। एनपी और सैटिसिबिलिटी समस्या। हालांकि, उनमें से अधिकांश सबसे महत्वपूर्ण सवालों के जवाब नहीं देते हैं। यह समस्या वास्तव में हमारे लिए महत्वपूर्ण क्यों है? अगर यह तय हो गया तो क्या होगा? यह सब कहां लागू होता है? और इसके बारे में कम से कम एक सामान्य विचार होना क्यों आवश्यक है?

अगर हम इस विषय पर [ १ , २ , ३ , ४ , ५ , ६ ,,] में हबर पर सबसे उल्लेखनीय काम का विश्लेषण करते हैं, तो हम ध्यान दें कि एक तरफ, कम्प्यूटेशनल जटिलता के क्षेत्र में ज्ञान रखने वाले लोग मौलिक रूप से नया कुछ भी नहीं सीख सकते हैं दिए गए लेख। दूसरी ओर, ये लेख अभी भी सार्वजनिक रूप से उपलब्ध नहीं हैं। शीर्षक से चित्रण स्पष्ट रूप से समस्या को प्रदर्शित करता है: जो लोग समझ नहीं पाए, इससे कुछ भी स्पष्ट नहीं है, और जो लोग पहले ही इसके बारे में सुन चुके हैं, उन्हें इसकी आवश्यकता नहीं है।

इस लेख के दो लक्ष्य हैं: पहला है समस्या का एक सामान्य विचार देना और प्रश्न का उत्तर देना, हमें इस समस्या (पहले भाग) के बारे में क्यों जानना चाहिए, दूसरा "विकास के लिए" सामग्री प्रदान करना है जो विषय में रुचि रखने वाले लोगों के लिए दिलचस्प होगा, साथ ही साथ विषय के दूसरे अध्ययन (दूसरा भाग) के लिए उपयोगी हो सकता है।

लेख संरचना

पढ़ने और नेविगेशन में आसानी के लिए, हम लेख की सामग्री का एक संक्षिप्त अवलोकन प्रदान करते हैं।

सार्वजनिक सामग्री
1. SAT हम सभी के लिए महत्वपूर्ण क्यों है? अनुप्रयोग / दिलचस्प एनपी कार्य और सैट
2. सैट और एनपी पूर्णता का इतिहास
3. एसएटी, एनपी और पी की सहज परिभाषा
4. क्या होता है अगर ... पी! = एनपी, पी = एनपी
5. 2-सैट बहुपद है: एल्गोरिथ्म और अंतर्ज्ञान
6. सोचने के लिए टास्क
विशिष्ट सामग्री (अगली श्रृंखला में देखें)
1. औपचारिक परिभाषा एनपी और CoNP के लिए घुलनशीलता समस्या की विषमता
2. 2 + पी-सैट बहुपद है?
3. चर की संख्या पर जटिलता की निर्भरता
4. मैंने P बनाम का फैसला किया एनपी, मुझे क्या करना चाहिए? कहाँ लिखूँ?
5. अनुभवहीनता प्रमेय: क्यों रोमनोव [ 3 ] का लेख अस्वीकार करने की अपेक्षा करता है
6. आधुनिक सैट सॉल्वर के बारे में
7. क्या पढ़ना है?
8. सोचने के लिए टास्क

त्याग

यह काम एक सामान्य शैक्षिक सामग्री है और इसका उद्देश्य केवल SAT मुद्दों से खुद को परिचित करना है। कम्प्यूटेशनल जटिलता और सैट मेरे शोध की मुख्य दिशाएं नहीं हैं, लेकिन संबंधित वैज्ञानिक क्षेत्र में झूठ हैं, इसलिए यदि संदेह है, तो हमेशा निर्दिष्ट स्रोत को देखें।

सार्वजनिक सामग्री

SAT हम सभी के लिए महत्वपूर्ण क्यों है? क्षुधा

इस प्रश्न का उत्तर देने के लिए, आपको पहले यह समझना होगा कि गणितीय समस्याएं हमारे ज्ञान के बिना वास्तविक रूप में हमारे रोजमर्रा के जीवन को कैसे प्रभावित करती हैं और ये समस्याएं सैट से कैसे संबंधित हैं।

यहां उन कार्यों की एक सूची दी गई है जो हमारे आसपास होते हैं और कहते हैं कि वे एसएटी से कैसे संबंधित हैं।

सबसे पहले, हम आरएसए क्रिप्टोग्राफिक एल्गोरिदम का उल्लेख करते हैं , जिसका उपयोग बैंक लेनदेन की सुरक्षा सुनिश्चित करने के लिए किया जाता है, साथ ही एक सुरक्षित कनेक्शन बनाने के लिए भी किया जाता है। आरएसए एल्गोरिथ्म को सैट का उपयोग करके "हैक" किया जा सकता है।
कई सिफारिश प्रणाली (उदाहरण के लिए, नेटफ्लिक्स के हिस्से के रूप में) सामग्री की सिफारिश करने के लिए एक बूलियन मैट्रिक्स अपघटन एल्गोरिथ्म का उपयोग करती है। इस तरह के मेट्रिसेस का इष्टतम अपघटन SAT का उपयोग करके पाया जा सकता है।
प्रोसेसर के बीच कार्यों के इष्टतम वितरण का कार्य SAT का उपयोग करके हल किया जा सकता है। उदाहरण के लिए, बड़ी संख्या में नियोजन कार्यों को SAT में घटाया जाता है, उदाहरण के लिए, दुकान शेड्यूलिंग , जहाँ कार्य (नौकरी) को कुछ चरणों (कुछ श्रमिकों द्वारा पूरा) के माध्यम से जाना चाहिए और सभी कार्यों के कुल प्रसंस्करण समय को कम करना आवश्यक है।
NASA अपने सॉफ्टवेयर विनिर्देशों और इसके हार्डवेयर मॉडल की जाँच करता है, जो सीधे SAT से जुड़ी मॉडल जाँच विधियों का उपयोग करता है।
SAT का उपयोग करके लोकप्रिय k- साधन क्लस्टरिंग विधि (k- साधन विधि) को हल किया जा सकता है।
ग्राफ़ से संबंधित अधिकांश दिलचस्प कार्य (उदाहरण के लिए, सोशल नेटवर्क पर, ग्राफ़ उपयोगकर्ताओं के बीच दोस्ती का रिश्ता है) सबसे बड़े समुदाय की खोज है, जहां हर कोई हर किसी के साथ दोस्त है, सबसे लंबे रास्ते की खोज और ग्राफ़ पर कई अन्य कार्यों को SAT का उपयोग करके हल किया जा सकता है। मॉस्को क्षेत्र (और न केवल) के जीवन से कार्य: कचरा ट्रकों की एक अनुसूची संकलित करना ताकि वे कम से कम समय के लिए एक बार सभी कचरा संग्रह बिंदुओं के आसपास जाएं। रसद में बड़ी संख्या में कार्य SAT कार्य के लिए आते हैं।
यहां तक कि एसएटी का उपयोग करके भी समस्या को हल किया जा सकता है। कार्य एक निश्चित आकार का एक उप-समूह है, इसमें सबसे बड़ी मूल्य की वस्तुओं को इकट्ठा करने के लिए (अग्रिम में सभी वस्तुओं के आकार को जानते हुए)।
SAT (और यहां तक कि मारियो !) सुडोकू पहेली और ध्यान का उपयोग करके कई वीडियो गेम हल किए जा सकते हैं, Minesweeper को SAT का उपयोग करके हल किया जा सकता है!
डेटाबेस में धारावाहिक इतिहास को क्रमबद्ध करने के कार्यों को SAT का उपयोग करके हल किया जा सकता है।

सैट का उपयोग करके हल किए गए कार्यों का विज़ुअलाइज़ेशन (बार्ट सेल्मन के कारण, यहाँ से लिया गया )

"हल किया जा सकता है" का क्या मतलब है और एनपी को इसके साथ क्या करना है?

सीधे शब्दों में कहें, अगर हमारे पास SAT समस्या का एक प्रभावी समाधान है, तो हम इन सभी समस्याओं को प्रभावी ढंग से हल कर सकते हैं। दक्षता से वास्तव में क्या मतलब है यह विशिष्ट कार्य पर निर्भर करता है, लेकिन यहां हम यह मानेंगे कि उपयोगकर्ता के लिए काम करने का समय स्वीकार्य है (एक सेमेस्टर के लिए एक स्कूल का समय निर्धारित करने के लिए, हम कंप्यूटिंग के लिए कुछ दिनों को समर्पित कर सकते हैं, और क्लस्टरिंग विधि के लिए, हम अंतःक्रियात्मक रूप से परिणाम प्राप्त करना चाहेंगे। )। और उपरोक्त कई समस्याओं के लिए रिवर्स भी सही है, अगर हम उन्हें प्रभावी ढंग से हल कर सकते हैं, तो हम कुशलता से SAT को हल कर सकते हैं (इसे एनपी-पूर्णता कहा जाता है - यह परिभाषा अनौपचारिक है, लेकिन एक सामान्य समझ के लिए पर्याप्त है)।

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

सैट और एनपी पूर्णता का इतिहास

एनपी पूर्णता

कम्प्यूटेशनल जटिलता का सिद्धांत , जिसमें भाषा और कार्यों को उनकी गणना के लिए आवश्यक समय और मेमोरी के अनुसार विभिन्न वर्गों को आवंटित किया जाता है, कम्प्यूटेबिलिटी के सिद्धांत (यानी, गोडेल, चर्च और ट्यूरिंग द्वारा 30 के काम) से पैदा हुआ था, जब हार्टमैनिस, स्टर्न, लुईस (1965) ) कार्यों के पहले ऐसे वर्गीकरणों में से एक का प्रस्ताव (मूल कार्य: यहां और यहां )।

1960 और 1970 के दशक में यूएसएसआर और यूएसए (एडमंड्स, लेविन, यबलोनस्की एट अल।) में एनपी-पूर्णता की अवधारणा स्वतंत्र रूप से विकसित हुई। 1971 में, स्टीफन कुक ने पी बनाम की परिकल्पना तैयार की। एन पी। प्रमेय कि एसएटी वर्ग एनपी के लिए एक "सार्वभौमिक समस्या" है और इस वर्ग (एनपी-पूर्णता) में किसी भी समस्या को हल करने की अनुमति देता है, लियोनिद लेविन (1973) और स्टीफन कुक द्वारा स्वतंत्र रूप से सिद्ध किया गया था, और इसे लेविन-कुक प्रमेय कहा जाता है । 1982 में, कुक को इस कार्य के लिए एक ट्यूरिंग पुरस्कार मिलेगा।

1972 में, कार्प ने कॉम्बीनेटरियल समस्याओं के बीच Reducibility प्रकाशित की, एक सूची जो दिखाती है कि सैट एनपी में केवल दिलचस्प काम से दूर है और एनपी में बड़ी संख्या में कार्य झूठ हैं और सैट के बराबर हैं। 1985 में, कार्प को इस काम के लिए ट्यूरिंग अवार्ड मिलेगा।

1974 में, फागिन दिखाएगा कि एनपी शास्त्रीय तर्क से निकटता से संबंधित है, अर्थात्, एनपी दूसरे क्रम के विद्यमान तार्किक संरचनाओं ( फागिन की प्रमेय ) के बराबर है।

1975 में, बेकर, जिल, और सोलोवे ने समस्या के प्रति अस्थिरता पर पहला मौलिक मेटा-परिणाम प्राप्त किया। नियमित तरीकों का उपयोग करते हुए एन.पी. यह पहला परिणाम है जो दिखा रहा है कि विधियों का एक पूरा वर्ग समानता बनाम P के प्रश्न का उत्तर नहीं दे सकता है। एनपी (इसके बारे में अधिक यहां लिखा गया है )।

1979 में, गैरी और जॉनसन ने " कम्प्यूटिंग मशीन एंड हार्ड प्रॉब्लम्स " लिखा, जो एनपी-पूर्णता और कार्यों की एक विस्तृत सूची पर जानकारी के सबसे व्यापक स्रोतों में से एक है। इस तथ्य के बावजूद कि कुछ सैद्धांतिक परिणामों को वर्तमान में अप्रचलित माना जाता है, यह कम्प्यूटेशनल जटिलता के क्षेत्र में सबसे मौलिक कार्यों में से एक है।

औपचारिक भाषाओं, कम्प्यूटेशनल जटिलता के सिद्धांत और कंप्यूटिंग के सिद्धांत ( यहां से ) के बीच संबंधों का दृश्य:

SAT-solvers का एक बहुत संक्षिप्त इतिहास

1960 में, डेविस और पुटमैन ने SAT ( मूल कार्य ) को हल करने के लिए शास्त्रीय रूप से घटात्मक (इसे सरलता से, प्रमेयों को सिद्ध करने के तरीके) लागू करने के तरीके लागू करने शुरू किए।

1962 में, डेविस, पुतनाम, लोगमैन, लवलैंड ने एक डीपीएलएल एल्गोरिदम का प्रस्ताव किया, जो कि नियतात्मक कंप्यूटिंग (इकाई-प्रसार) की वापसी और वितरण के साथ खोज पर आधारित था। इसे सीधे शब्दों में कहें, एल्गोरिथ्म ने कुछ चर के मूल्य को सत्य के बराबर माना और इस तरह के समाधान के सभी निर्धारक परिणामों की गणना की और एक समाधान मिलने तक दोहराया। इस एल्गोरिथ्म ने दशकों के लिए कई सैट सॉल्वरों के आधार के रूप में कार्य किया है।

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

1996 में, मार्किस-सिल्वा और सकलाह ने डीपीएलएल की तरह संघर्ष-प्रेरित-क्लॉज-लर्निंग ( सीडीसीएल ) एल्गोरिथ्म का प्रस्ताव दिया, यह चर के मूल्य पर निर्णय लेता है और निर्धारक गणना करता है, दूसरी तरफ, यह एनिमेशन का ग्राफ संग्रहीत करता है और कुछ को याद करता है। संयोजन जो समाधान का नेतृत्व नहीं करते हैं और प्रभावी रूप से "बेकार" समाधानों से बच सकते हैं और पहले से स्थापित संघर्ष वाले समाधानों के स्थान को प्रभावी ढंग से काट सकते हैं।

2001 के बाद से, स्थानीयता आधारित खोज सैट-सॉल्वर दिखाई देने लगे हैं, प्रभावी रूप से स्थानीय जानकारी, जैसे कि बर्कमिन (बर्कले-मिन्स्क) और कई अन्य लोगों के आधार पर एक पूर्ण खोज के लिए उप-स्थान का चयन करते हैं।

एसएटी, एनपी और पी की सहज परिभाषा

सैट

हम यह परिभाषित करना शुरू करते हैं कि प्रस्तावक तर्क क्या है : चर का एक सेट {x, y, z, ...} और कनेक्टर्स का एक सेट {और, या, - (नहीं), →}। प्रत्येक चर या तो "गलत" या "सत्य" हो सकता है। कनेक्टर्स को मानक के रूप में परिभाषित किया गया है:

x और y सत्य है यदि और केवल अगर (संक्षिप्तता के लिए हम iff लिखेंगे - यदि और केवल यदि) x सत्य है और y सत्य है, तो क्लासिक "और"
x या y सही iff कम से कम एक चर x \ y सच है, क्लासिक "OR"
-x सच iff x गलत, क्लासिक नकार
x → y गलत है अगर x सही है, और y गलत है - एक उदाहरण पर विचार करें:
"अगर बारिश हो रही थी, तो घास गीली है"
कथन असत्य है अगर और केवल तभी बारिश (x सच) थी और घास अभी भी सूखी (y झूठी) है।

फॉर्मूला एफ वैरिएबल और कनेक्टर्स का एक वाक्यविन्यास रूप से सही सेट है, अर्थात, →, और, या वैरिएबल या अन्य फ़ार्मुलों को कनेक्ट करने के लिए, - (नहीं) एक वेरिएबल या फॉर्मूला से पहले खड़ा होता है। उदाहरण, F = (x → (y या z)) और (z → -x)।

वे कहते हैं कि सूत्र एफ संतोषजनक है (सैट), अगर इसके चर को "सही" \ "असत्य" मान दिया जा सकता है (हम इस तरह के फ़ंक्शन को अंग्रेजी I nterpretation से कॉल करते हैं), ताकि एफ सच हो। संक्षिप्तता के लिए, हम I (F) = "सत्य" लिखते हैं।

किसी भी प्रपोजल फॉर्मूला F को CNF (कंजंक्टिव नॉर्मल फॉर्म) के रूप में कम किया जा सकता है, अर्थात, के रूप में दर्शाया जाए
एफ '= सी ₁ और सी ₂ और ... सी _एन
जहाँ c _मैं है (x या y या z), और x, y, z चर या उनके नकार हैं।

उदाहरण F = (x or -y or -z) और (-x or -y या h) और (z या h)।

इस परिवर्तन के बारे में अधिक विवरण यहां लिखे गए हैं (प्रत्येक वाक्य के लिए तीन से अधिक चर नहीं होने के लिए, आपको अतिरिक्त चर पेश करने की आवश्यकता होगी, लेकिन ये केवल तकनीकी विवरण हैं)।

इस रूप में, जब सूत्र में ऊपर वर्णित रूप होता है, तो कार्य को 3-SAT कहा जाता है, इस तथ्य पर बल देते हुए कि प्रत्येक वाक्य c _i में तीन से अधिक चर या उनके नकारात्मक शामिल नहीं हैं।

3-SAT समस्या का विवरण इस प्रकार है:
दिया गया: 3-सीएनएफ के रूप में प्रपोजल फॉर्मूला एफ
खोजें :: फ़ंक्शन I , सभी चर के लिए "सही" \ "असत्य" मान प्रदान करता है, जैसे कि मैं (एफ) = सही "

कक्षा पी

P यह PTIME है - बहुपद समय में हल करने वाले कार्य, इसका मतलब है कि इस वर्ग में एल्गोरिथ्म चरणों की संख्या इनपुट डेटा से एक निश्चित बहुपद से अधिक नहीं बढ़ती है। पीटीआईएमई में विभिन्न एल्गोरिदम और जटिलता विश्लेषण के बारे में अधिक पहले ही हैबर [ 9 , 10 , 11 , 12 , 13 ] पर लिखा जा चुका है।

उदाहरण के लिए, यहां एक सरल उदाहरण है: एक बुलबुला सॉर्ट एल्गोरिथ्म (विकी से स्यूडोकोड )

procedure bubbleSort( A : list of sortable items ) n = length(A) repeat swapped = false for i = 1 to n-1 inclusive do if A[i-1] > A[i] then swap(A[i-1], A[i]) swapped = true end if end for n = n - 1 until not swapped end procedure

इनपुट पैरामीटर सॉर्ट करने के लिए संख्याओं की एक सरणी है। हम सरणी की लंबाई के आधार पर समय की वृद्धि में रुचि रखते हैं अर्थात्। n पर TIME समय की निर्भरता। ध्यान दें कि दोहराए गए लूप का प्रत्येक पुनरावृत्ति 3 * n चरणों से अधिक नहीं करता है और सरणी के कम से कम एक तत्व को वांछित स्थान पर सेट करता है। इसका मतलब यह है कि रिपीट लूप को n से अधिक बार निष्पादित किया जाता है। इसका मतलब है कि ऑपरेशन की संख्या (उर्फ टाइम) सरणी की लंबाई के एक निश्चित वर्ग के रूप में बढ़ती है (और "n = लंबाई (ए)" से रैखिक शब्द) यानी।

TIME (n) = a * n ² + b * n + C

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

कक्षा एनपी

एनपी nondeterministic बहुपद समय के लिए खड़ा है। बहुत बार इसे गलती से गैर-बहुपद समय कहा जाता है, इस बारे में एक मजाक पैदा हुआ था:

बहुपद और गैर-बहुपद में एल्गोरिदम को विभाजित करना ब्रह्मांड को केले और गैर-केले में विभाजित करने के समान है।

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

SAT के दृष्टिकोण से, समाधान स्थान चर मानों के सभी प्रकार के सेट हैं, यदि हमारे पास सूत्र में k भिन्न चर हैं, तो हमारे पास सूत्र के 2 ^k "व्याख्या" संभव हैं, अर्थात् खोज स्थान I घातीय। हालाँकि, अगर हमने "अनुमान लगाया" I , तो हम बहुपद समय में सूत्र की सच्चाई को सत्यापित कर सकते हैं।

क्या होता है अगर पी! = एनपी

कुछ भी नहीं होगा, केवल किसी को एक मिलियन डॉलर प्राप्त होगा ।

क्या होता है अगर पी = एनपी

दो खबरें हैं: अच्छी और बुरी।

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

बुरे लोग। सभी आधुनिक क्रिप्टोग्राफी ढह रही है, और इसके साथ बैंकिंग प्रणाली हिट है। लोग मारियो के लिए बॉट लिखना शुरू कर देंगे।

2-SAT में पी।

SAT के एक दिलचस्प बदलाव पर विचार करें, जिसमें प्रत्येक खंड दो चर तक सीमित है। इसके बाद, लेखक सामग्री की धारणा को सुविधाजनक बनाने के लिए सब कुछ सरल करता है।

यह देखते हुए : F फॉर्म c ₁ और c ₂ और c ₃ ... और c _n का एक सूत्र है,
जहाँ c में _i का रूप (x या y) और x है, y चर या उनके नकारात्मक हैं, अर्थात x कुछ चर v या -v है।
खोजें : फ़ंक्शन I , सभी वेरिएबल्स के लिए "सही" \ "असत्य" मान के कारण, जैसे कि मैं (F) = सही "
कथन : एक बहुपद एल्गोरिथ्म P है जैसे कि यदि फ़ंक्शन मैं मौजूद है, तो P (F) = I , अन्यथा, P (F) = {}।

(*) फ़ंक्शन मैं अद्वितीय नहीं है अगर यह मौजूद है और पी कुछ फ़ंक्शन I (एल्गोरिदम और जटिलता के सिद्धांत पर पुस्तकों में) देता है, तो सब कुछ औपचारिक भाषा में लिखा जाएगा, लेकिन ये विवरण 2-SAT के बहुपद क्यों है के सामान्य विचार को समझने के लिए आवश्यक नहीं हैं )

सबूत के स्केच:

पहले, हम निम्नलिखित समानता का उपयोग करके मूल सूत्र को बदलते हैं:

आप इसे सत्य तालिका का उपयोग करके देख सकते हैं। इस नियम के पीछे अंतर्ज्ञान इस प्रकार है:
"अगर बारिश हो रही थी, तो घास गीली है" (x → y, x - यह बारिश हो रही थी, y - घास गीली है)
इसका मतलब है कि अगर घास सूखी है (गीली नहीं है: y झूठी है), तो निश्चित रूप से बारिश नहीं होती है (x झूठी है)।
यदि घास गीली है, तो या तो बारिश हुई थी (एक्स एक अर्थ में, x सही है, एक्स "बताते हैं" क्यों y सच है), या कोई बारिश नहीं थी (एक्स झूठी है), एक सहज स्तर पर, हमारा मतलब है कि एक और कारण है कि वाई सच (z - एक पड़ोसी ने घास डाली और इसलिए घास गीली है)।

हम F का उपयोग करते हुए (*) को फॉर्म c ' ₁ और c' ₂ ... और c ' _{n में बदल देते हैं,} जहां c' _i का फॉर्म है (x → y), x, y वेरिएबल या उनके नेगेटिव हैं। नतीजतन, एफ एक निहितार्थ ग्राफ है। नीचे एक समान ग्राफ का एक उदाहरण:
s ₁ = यदि बारिश हो रही थी, तो घास गीली है।
c ₂ = यदि किसी पड़ोसी ने लॉन में पानी डाला है, तो घास गीली है।
c ₃ = यदि घास गीली है, तो खरपतवार अच्छी तरह से बढ़ते हैं।

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

ऐसे कितने निर्णय लिए जाने की आवश्यकता है? N से अधिक कोई वाक्यों की संख्या नहीं है। एक निर्णय लेते समय आपको कितने ऑपरेशन करने होंगे? प्रत्येक समाधान के लिए, हमें ग्राफ़ के किनारों पर एक बार से अधिक नहीं जाना चाहिए, अर्थात, एक समाधान पर n संचालन से अधिक नहीं। इसका मतलब है कि I को खोजने के लिए n ² से अधिक ऑपरेशन नहीं किए जाने चाहिए । ■

कार्य "सोचने के लिए"

इस कार्य के लिए अतिरिक्त अध्ययन और साहित्य खोज की आवश्यकता हो सकती है।

तुच्छ सैट समाधान

शर्त
प्रत्येक प्रपोजल फॉर्मूला F = c ₁ और c ₂ और c ₃ और c _n को एक विवादास्पद सामान्य रूप (DNF) में लाया जा सकता है, अर्थात, F '= c' ₁ या c ' ₂ ... या c' _k , जहाँ c ' _मेरे पास फॉर्म (x और y और z) है, x, y, z वैरिएबल या उनके नेगेटिव हैं। उदाहरण के लिए, डी मॉर्गन नियमों (लिंक) के संगत अनुप्रयोग और कोष्ठक के प्रकटीकरण का उपयोग करना।
एफ 'के लिए, फ़ंक्शन I के लिए एक तुच्छ खोज एल्गोरिदम मौजूद है। यह आवश्यक है कि कम से कम एक सी' _मैं सच हो। आइए समस्या को हल करने वाला एक सरल छद्म कोड लिखें:

 #Input: F — propositional formula in disjunctive normal form (DNF) #Output: {SAT, UNSAT} for each c in F do if c is SAT: return SAT return UNSAT

प्रत्येक वाक्य (क्लॉज़) c _{i के लिए,} खोज एल्गोरिथ्म मैं भी तुच्छ है, यदि वाक्य c _i में कुछ चर v और इसकी नकारात्मकता एक ही समय में नहीं है, तो c _i संतोषजनक है (SAT)।
कुल : हमें संतुष्टि के लिए सूत्र की जांच के लिए एक तुच्छ एल्गोरिथ्म मिलता है
ढूँढें : त्रुटि कहाँ है?

सन्दर्भ और सूत्र

हम सभी को SAT और इन सभी P-NPs (भाग एक) की आवश्यकता क्यों है