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

पिछले भाग में , SAT और P-NP से संबंधित सार्वजनिक रूप से उपलब्ध प्रश्नों पर प्रकाश डाला गया था: समस्या का इतिहास, कक्षाओं और कार्यों की सहज परिभाषाएँ, SAT के मुख्य अनुप्रयोग और P के हल के मामले में मुख्य परिणाम? = NP (वहाँ आप विभिन्न सामग्रियों के लिए पर्याप्त संख्या में संदर्भ पा सकते हैं? स्व-अध्ययन विषयों के लिए)।

इस लेख में हम मुद्दे के तकनीकी पक्ष पर विचार करेंगे, साथ ही पिछले लेख से सामग्री को औपचारिक रूप से प्रस्तुत करेंगे।



लेख बूलियन संतुष्टि से छवि : सैद्धांतिक सफलता से व्यावहारिक सफलता (एसीएम के संचार)

लेख संरचना

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

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

क्या होगा अगर ...

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

विभिन्न समाधानों के इर्द-गिर्द चर्चा का वर्णन करने के लिए यह कलात्मक दृष्टि से काफी दिलचस्प है।

पी = एनपी

स्थिति के विकास के लिए कई विकल्प हैं।

• रचनात्मक समाधान
  
  1. बहुपद में एक कम डिग्री और मध्यम गुणांक होते हैं: फिर विवरण पिछले लेख के पी = एनपी भाग में वर्णित हैं; संक्षेप में: सभी क्रिप्टोग्राफी ढह जाएगी
  2. बहुपद में एक उच्च डिग्री होती है - फिर व्यावहारिक दृष्टिकोण से कुछ भी नहीं बदलेगा पी! = एनपी
  
  
• असंयमित समाधान
  
  1. यदि हम इस प्रमाण से एल्गोरिथ्म प्राप्त नहीं कर सकते हैं, तो व्यावहारिक दृष्टिकोण से पी! = एनपी
  2. यदि हम कर सकते हैं, तो प्रश्न पी? = एनपी समय के एक प्रश्न और सबूत से एक एल्गोरिथ्म के निर्माण में बदल जाता है
  
  

पी! = एनपी

पिछले मामले की तरह, समाधान रचनात्मक और गैर-रचनात्मक हो सकता है। रचनात्मक मामले पर विचार करें (पिछले मामले के समान संरचनात्मक रूप से असंवैधानिक)

• समाधान की जटिलता हमेशा घातीय है: कोई परिवर्तन नहीं, दुनिया की वर्तमान तस्वीर पूरी तरह से संरक्षित होगी, एल्गोरिदम में कोई परिवर्तन नहीं
• समाधान की जटिलता हमेशा घातीय ( इस पोस्ट को देखें) नहीं है, लेकिन पर्याप्त संख्या में मामलों के लिए यह बहुपद है। इस मामले में, यह अंदाजा लगाना लगभग असंभव है कि क्या होगा और कोई केवल अनुमान लगा सकता है: यदि फैक्टराइजेशन समस्या "आसान कार्यों के वर्ग" में आती है, तो व्यावहारिक दृष्टिकोण से यह आरएसए पर हमला करने के लिए पी = एनपी के बराबर होगा।
• समाधान की जटिलता मध्यम या निम्न (जैसे n ^{लॉग (n)} ) है, इस मामले में, व्यावहारिक दृष्टिकोण से, यह P = NP के बराबर होगा

P बनाम एनपी स्वयंसिद्ध ZFC में हल नहीं है

विवरण और दिलचस्प लेख में लिखा है पी वर्सस एनपी औपचारिक रूप से स्वतंत्र है? स्कॉट आरोनसन द्वारा (लेख को समझने के लिए पर्याप्त गणितीय संस्कृति की आवश्यकता है; अनुमानित पढ़ने का समय ~ दोपहर 1/2 बजे)। यहां लेख की सामग्री का संक्षिप्त अवलोकन दिया गया है।

निम्नलिखित में लेख का मुख्य संदेश, यह पता चल सकता है कि दोनों परिकल्पना पी = एनपी और पी! = एनपी सेट सिद्धांत के अनुरूप हैं। यह हो सकता है अगर P बनाम एनपी सेट सिद्धांत के स्वयंसिद्धों से स्वतंत्र है, जैसे चुनाव का स्वयंसिद्ध सेट सिद्धांत के अन्य स्वयंसिद्धों से स्वतंत्र है। व्यावहारिक दृष्टिकोण से, इसका मतलब यह होगा कि पी! = एनपी।

औपचारिक परिभाषा एनपी के लिए घुलनशीलता समस्या की विषमता। CoNP वर्ग।

जटिलता सिद्धांत में, यह "घुलनशीलता समस्याओं" के रूप में समस्याओं को तैयार करने के लिए प्रथागत है ऐसे कार्य जिनके लिए उत्तर केवल "हां" या "नहीं" हो सकता है। P और NP को औपचारिक रूप से भाषाओं और ट्यूरिंग मशीनों के संदर्भ में परिभाषित किया गया है।

जहाँ L _M मशीन M द्वारा प्राप्त भाषा है।
हम कहते हैं कि एक निश्चित समस्या p वर्ग P की है यदि एक नियतात्मक ट्यूरिंग मशीन है जो बहुपद संख्या के लिए भाषा L (p) को लेती है।

एनपी वर्ग के साथ, सब कुछ थोड़ा और दिलचस्प है, यह समस्याओं का एक वर्ग है जहां समाधान की शुद्धता को बहुपद समय में जांचा जा सकता है। औपचारिक रूप से, हम कहते हैं कि भाषा L, NP से संबंधित है, यदि केवल और केवल अगर कोई निर्धारक ट्यूरिंग मशीन M मौजूद है, तो किसी भी पंक्ति x के लिए यह सत्य है:

कहाँ | y | - एक बहुपद से घिरा हुआ है और M एक बहुपद संख्या का प्रदर्शन करता है। एक प्रमाण पत्र "y" के लिए एक विशेष शब्द है। वास्तव में, परिभाषा निम्नानुसार पढ़ती है - समस्या एनपी से संबंधित है यदि एक बहुपद समाधान है, जिसकी शुद्धता को बहुपद समय में सत्यापित किया जा सकता है। ध्यान दें कि यह परिभाषा उस प्रश्न के संबंध में असममित है जब भाषा एनपी से संबंधित नहीं होती है यानी सवाल यह नहीं है कि क्या एनपी एक अलग वर्ग का है।

Co-NP का वर्ग क्या है? सह-एनपी - एनपी के पूरक, सहजता से, यह एक ऐसा वर्ग है जिसमें एनपी में कार्यों का निषेध है। यदि SAT पूछता है कि क्या यह असाइनमेंट वेरिएबल्स के लिए सही / गलत है कि फॉर्मूला सही है, तो UNSAT पूछता है कि क्या फॉर्मूला सभी असाइनमेंट के लिए गलत है? यानी दूसरे शब्दों में, क्या यह सच है कि प्रमाणपत्र मौजूद नहीं है।

या दूसरे तरीके से इसे निम्न प्रकार से तैयार किया जा सकता है:
एनपी संबद्धता के संक्षिप्त प्रमाण पत्र के साथ भाषाओं का एक संग्रह है
सह-एनपी संबद्धता से वंचित प्रमाण पत्र के साथ भाषाओं का एक संग्रह है (= कोई प्रतिज्ञान प्रमाणपत्र मौजूद नहीं है)

यदि एनपी! = को-एनपी, तो एनपी-पूर्ण और सह-एनपी-पूर्ण समस्याओं का सेट इंटरसेक्ट नहीं करता है ( महाने की प्रमेय की कोरोलरी )।

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

आधुनिक अवधारणाओं के अनुसार, NP, Co-NP और P के बीच का संबंध इस प्रकार है:

(तस्वीर यहां से ली गई है )
अधिकांश विकल्प (डी) की ओर झुके हुए हैं, लेकिन कुछ का मानना ​​है कि अन्य विकल्प भी संभव हैं जैसे ड्राफ्ट में नॉट द आर्ट ऑफ़ प्रोग्रामिंग 4, 6 ए: संतुष्टि - पृष्ठ 1, फुटनोट (*): "... इस पुस्तक के लेखक, हालांकि, संदेह है कि बहुपद एल्गोरिथ्म [SAT के लिए - लेखक के नोट] वास्तव में मौजूद हैं, केवल वे अभी तक हमारे लिए ज्ञात नहीं हैं ... "।

2 + पी-सैट बहुपद है?

पिछले लेख में, यह दिखाया गया था कि 2-SAT बहुपद है, अर्थात यदि हम प्रत्येक खंड को दो चर के लिए प्रतिबंधित करते हैं, तो समस्या को कुशलता से हल किया जा सकता है। आइए इस समस्या के एक प्राकृतिक सामान्यीकरण पर विचार करें, क्या होगा यदि हमारे पास केवल 3 चर वाले वाक्यों का एक हिस्सा है?

आज्ञा देना वाक्य की संख्या 3 चर के साथ वाक्य की कुल संख्या है। फिर 2 + p SAT समस्या एक 3-SAT समस्या है जिसमें 3 चर के साथ वाक्यों की संख्या पहले से तय होती है अर्थात। p, क्रमशः (1 - p) वाक्यों में 1 या 2 चर होते हैं।

सैद्धांतिक दृष्टिकोण से, भले ही पी ऑसिलोकोकिनम में बार्बेरियन बतख की एकाग्रता है यानी कोई भी सकारात्मक संख्या, तो एनपी समस्या पूर्ण है, लेकिन व्यवहार में यह पूरी तरह से अलग दिखती है।
X अक्ष के साथ सूत्र में कुल चर हो सकते हैं, Y अक्ष के साथ इस सूत्र के लिए समाधान की "कम्प्यूटेशनल लागत" हो सकती है (आमतौर पर यह अत्याधुनिक SAT-सोल एल्गोरिथम के कॉल \ समाधान की संख्या है, DPLL और CDCL का संक्षिप्त विवरण देखें पिछला लेख)।

(ग्राफ 2 + पी-सैट से लिया गया है : चरण संक्रमण की प्रकृति के लिए ठेठ-मामले की जटिलता का संबंध )।

यदि पी <= 0.4, तो समस्या बहुपद है, और इससे भी अधिक, इनपुट डेटा में रैखिक। यदि p> 0.4, तो हम क्लासिक 3-सैट के समान व्यवहार का निरीक्षण करते हैं। इस आशय की व्याख्या करने के लिए, क्लासिक डीपीएलएल एल्गोरिथ्म पर विचार करें (आर्मिन बिरे स्लाइड से लिया गया):


आइए एक साधारण उदाहरण देखें।

एल्गोरिथ्म को x ₂ = 1 चुनें

फिर सूत्र सरल किया गया है और हमारे पास एक एकल चर के साथ दो वाक्य हैं - इसका मतलब है, बूलियन बाधा प्रसार उनमें से एक का चयन करता है, उदाहरण के लिए x ₃ और इसके लिए उपलब्ध एकमात्र मान असाइन करता है

X ₃ = 1 असाइन करने के बाद, BCP फिर से एक एकल चर x _{1 के} साथ एक वाक्य पाता है, और x ₁ = 1 असाइन करता है

इस प्रकार, एक एकल सैट सॉल्वर समाधान के बाद, बूलियन बाधा प्रसार आपको पूरे सूत्र का समाधान खोजने की अनुमति देता है। यह मुख्य रूप से होता है क्योंकि दो चर के साथ एक वाक्य में एक चर पर निर्णय, वास्तव में, विशिष्ट रूप से दूसरे चर का मूल्य निर्धारित करता है, जो असाइनमेंट की एक पूरी झरना का कारण बनता है और BCP प्रभावी रूप से सूत्र को कम करता है। यदि इस तरह का कैस्केड सूत्र में पर्याप्त संख्या में चर को कवर करता है, तो समाधान रैखिक है।

चर की संख्या पर जटिलता की निर्भरता

एक और दिलचस्प निर्भरता तथाकथित खंड-चर-अनुपात है: वाक्यों की संख्या का अनुपात चर की संख्या। सहज रूप से, अधिक वाक्य, अधिक प्रतिबंध, अधिक संभावना है कि सूत्र संभव नहीं है - बहुत सारे प्रतिबंध। इस तरह की समस्या को अतिरंजित कहा जाता है। यदि कुछ प्रस्ताव हैं, लेकिन कई चर हैं, तो इसका मतलब है कि स्वतंत्रता की कई डिग्री हैं, और कुछ प्रतिबंध हैं। इससे समाधान खोजना आसान हो जाता है, और संभावना है कि सूत्र संभव है। वे उसके बारे में कहती हैं कि वह कमज़ोर है।

चूंकि हम पहले से ही 2 + पी सैट पर विचार कर चुके हैं, इसलिए इस निर्भरता में पैरामीटर पी को ध्यान में रखना भी दिलचस्प होगा, समस्या की "रैखिकता" की डिग्री के रूप में, बड़ा पी, कम प्रभावी बूलियन बाधा अवरोध और समाधान खोजने के लिए अधिक कठिन है।

2 + पी सैट के लिए SAT / UNSAT संक्रमण

प्रकृति से ग्राफ़: रेमी मॉनसन, रिकार्डो ज़ेचिना, स्कॉट किर्कपैट्रिक, बार्ट सेल्मैन और लिडरॉफ़ ट्रोएन्स्की द्वारा विशेषता `चरण संक्रमण 'से कम्प्यूटेशनल जटिलता का निर्धारण

वास्तव में, यह ग्राफ हमें लगता है कि हमें कुछ और देता है: यह हमें "जटिल" यादृच्छिक सूत्र उत्पन्न करने की अनुमति देता है। यदि फॉर्मूला SAT और UNSAT के बीच में कहीं है, तो इसका मतलब है कि इसके लिए एक मॉडल ढूंढना मुश्किल है और अव्यवहारिकता का प्रमाण उत्पन्न करना मुश्किल है।
एसएटी / यूएनएसएटी संक्रमण की स्थिति पर डीपीएलएल कॉल की संख्या की निर्भरता इस प्रकार है

लेख से ग्राफ में सतीस क्षमता समस्या के हार्ड इंस्टेंस को खोजना: एस। कुक, डी। मिशेल द्वारा एक सर्वेक्षण

आधुनिक सैट सॉल्वर के बारे में

यहां तक ​​कि बुनियादी सिद्धांतों, एल्गोरिदम और हेयूरिस्टिक्स का एक सौ से अधिक पृष्ठों का वर्णन होगा, इसलिए हम खुद को सबसे लोकप्रिय और महत्वपूर्ण एसएटी एल्गोरिदम में से एक के विवरण तक सीमित रखेंगे: सीडीसीएल - संघर्ष प्रेरित क्लॉज लर्निंग। जैसा कि नाम का अर्थ है, इस एल्गोरिथ्म की मुख्य विशेषताओं में से एक निर्णय को याद रखने की क्षमता है जो समाधान का नेतृत्व नहीं करता है, अर्थात्, एल्गोरिथ्म उन्हें वाक्यों के रूप में याद करता है। यदि हमने निर्णय लिया x ₁ = 1, x ₂ = 2, x ₃ = 1 और इससे संघर्ष होता है, तो CDCL संघर्ष संयोजन के निषेध को याद रखेगा।

डी मॉर्गन के नियम के अनुसार, हम CNF को फॉर्म देते हैं

और इसे सूत्र में जोड़ें


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

आइए CDCL एल्गोरिथ्म के उदाहरण पर करीब से नज़र डालें:

मासाहिरो सकई से

CDCL के बारे में अधिक जानकारी निम्नलिखित कार्यों में लिखी गई है:
हैंडबुक ऑफ़ सैटिस: क्षमता: अध्याय 4. कॉन Dri ict-ड्रिवेन क्लॉज लर्निंग सैट सॉल्वर्स द्वारा जोआओ मार्केस-सिल्वा, इनेस लिनस और शरद मलिक
CDCL द्वारा SAT / SMT समर स्कूल 2013 स्लाइड्स: CDCL SAT सॉल्वर एंड सैट-बेस्ड प्रॉब्लम सॉल्विंग
एल्गोरिथ्म और आंतरिक संरचनाओं का विस्तृत और पर्याप्त तकनीकी विवरण: प्रैक्टिकल सैट सॉल्विंग: कॉन ict-संचालित सैट सॉल्वर

मैंने P बनाम का फैसला किया एनपी, मुझे क्या करना चाहिए? कहाँ लिखूँ?

सबसे पहले, सामान्य ज्ञान के समाधान की अनुरूपता पर कई प्रश्नों का उत्तर देना आवश्यक है

1. क्या कार्य समझा सकता है कि समस्या को हल करने के अन्य प्रयास विफल क्यों हुए, लेकिन हमारा काम नहीं है
2. यह कार्य अक्षमता प्रमेय को कैसे रोकता है अर्थात्। स्पष्ट रूप से दिखाते हैं कि ये प्रमेय (जैसे बेकर-गिल-सोलोवे प्रमेय) इस कार्य के लिए लागू नहीं हैं
3. यदि पी = एनपी और प्रमाण रचनात्मक है, तो एक प्रोटोटाइप की आवश्यकता होती है, अन्यथा कोई भी समाधान में विश्वास नहीं करेगा
4. कार्य आत्मनिर्भर है और विशेषज्ञ को समझने के लिए उपलब्ध है अर्थात्। इसमें सभी आवश्यक परिभाषाएँ हैं, विस्तारित रूप में साक्ष्य (सहस्राब्दी कार्य, चित्रलिपि और एक दुर्गम भाषा के साथ 3 पृष्ठों पर लिखा गया है, इससे निरीक्षक को संदेह होता है और उसे टोकरी में जहर देने की इच्छा होती है)
5. लेखकों को जटिलता सिद्धांत की अच्छी समझ है यानी वे सभी मुख्य कार्यों और कार्यों से परिचित हैं और जानते हैं कि हाल के वर्षों में इस वैज्ञानिक क्षेत्र में क्या हुआ है

मान लीजिए कि इन सभी शर्तों को पूरा किया जाता है, तो दूसरा, एक मान्यता प्राप्त निर्णय क्या माना जाएगा? "स्वचालन और यांत्रिकी" पत्रिका में प्रकाशन? पी बनाम एनपी समस्या के लिए उपयुक्त कई सम्मेलन हैं:
STOC, कम्प्यूटिंग के सिद्धांत पर वार्षिक ACM संगोष्ठी
TAGL, ACM लेनदेन एल्गोरिदम पर
एफओसीएस, कंप्यूटर विज्ञान की नींव पर IEEE वार्षिक संगोष्ठी

यदि वे (इन सम्मेलनों में से कोई भी) आपके निर्णय को पहचानते हैं, तो आप सुरक्षित रूप से अपने मिलियन पर भरोसा कर सकते हैं - उस क्षण तक, निर्णय को कई गलत निर्णयों में से एक माना जाता है P बनाम। एन पी।

पी बनाम चेकिंग के मुद्दे पर एक दिलचस्प रोडमैप (अधिक सटीक, यहां तक ​​कि सवालों की एक इंटरैक्टिव सूची) एनपी समाधान यहां प्रस्तुत किए गए हैं ।

क्यों रोमनोव के लेख को अस्वीकार करने की उम्मीद है

यदि आप एक संक्षिप्त उत्तर देते हैं, तो क्योंकि लेख "सामान्य ज्ञान" की सूची से किसी भी प्रश्न का उत्तर नहीं देता है:

1. लेख में "संबंधित कार्य" बिल्कुल नहीं है, ऐसा लगता है कि 40 वर्षों से जटिलता सिद्धांत में कोई प्रगति नहीं हुई है (लेखक ने केवल तीन बार खुद को संदर्भित किया है): उदाहरण के लिए, आप एनपी-पूर्णता स्तम्भ पर एक नज़र डाल सकते हैं : अनुमोदन द्वारा कई सीमाएँ डेविड एस। जॉनसन , संक्षेप में इस मामले पर संक्षेप में सभी संबंधित कार्यों के बारे में बताते हैं, टीएजीएल में सामान्य उच्च गुणवत्ता वाले काम
2. यह काम एक बीजगणितीय प्रतिनिधित्व (चर से गोलियां, इन गोलियों पर एक ग्राफ और गुणों की जाँच के लिए लगभग एक संवादात्मक प्रश्न) को स्वीकार करता है - आरोनसन-विगडरसन प्रमेय (सामान्यता बेकर-गिल-सोलोविज प्रमेय) की डिकैडेबिलिटी पी बनाम पर सीधे लागू होती है। बीजीय बीजीय तरीकों का उपयोग कर। वैसे, यदि समीक्षकों को संदेह है कि आप इस तरह के परिणामों को उद्देश्य से अनदेखा करते हैं, तो यह प्रस्तुत कार्य के खिलाफ व्याख्या की जाएगी
3. कहाँ है कि प्रोटोटाइप asymptotics में एक घातीय तक नहीं चल रहा है?
4. एल्गोरिथ्म का छद्म कोड कहां है? एक पूर्ण-कार्यशील उदाहरण कहां है: इनपुट एक प्रसिद्ध जटिल उदाहरण है, क्या एल्गोरिथ्म और आउटपुट डेटा का संचालन चरणबद्ध है? औपचारिकता कहाँ है? 17-पृष्ठ के लेख में, फ़ॉर्म के दो सूत्र (a = b) और आत्मा में अनौपचारिक वाक्यांश: "तीन गैर-खाली कॉलम की समान संख्या के साथ F की पंक्तियों को समूहीकृत करना;"
5. काम में कोई महत्वपूर्ण संदर्भ नहीं हैं, उदाहरण के लिए, लेविन-कुक के काम के लिए।

इसके अलावा, मान लीजिए कि काम सही हो गया है, तब भी किसी को खुले पत्र लिखने का कोई मतलब नहीं है - आधुनिक विज्ञान उस तरह से काम नहीं करता है, सही निर्णय के जनता को समझाने के लिए यह आपका काम है। यह केवल विशेषज्ञ राय के चश्मे के माध्यम से किया जा सकता है, ऊपर वर्णित सम्मेलनों को देखें।

क्या पढ़ना है?

आमतौर पर, SAT / श्रीमती गर्मियों के स्कूलों में सब कुछ अच्छी तरह से और आसानी से समझाया जाता है:
स्कूल सामग्री 2013
स्कूल सामग्री 2012

जल्द ही सैट के बारे में एक नया विवरण होगा - एक मसौदा उपलब्ध है: प्रोग्रामिंग 4 की कला, 6 ए: संतुष्टि

पिछली पोस्ट में बड़ी संख्या में लिंक मौजूद हैं। हम सभी को SAT और इन सभी P-NPs (भाग एक) की आवश्यकता क्यों है
यहाँ प्रमुख हैं:
सैट-सॉल्वर के बारे में:
सैट सॉल्वर: ए कंडेंस्ड हिस्ट्री
आधुनिक सैट सॉल्वर को समझना आर्मिन बिरे के लेखक हैं, जो शायद दुनिया में सबसे प्रसिद्ध सैट सॉल्वर डेवलपर है। डोनाल्ड नुथ, जो अब द आर्ट ऑफ़ कंप्यूटर प्रोग्रामिंग: वॉल्यूम 4 बी, प्री-फ़्रीकॉल 6 ए सैटिसेबिलिटी लिख रहे हैं, का कहना है कि वह कई मुद्दों पर उनके साथ काम करते हैं।
सैट सॉल्वर के एक नए युग की ओर

एनपी के इतिहास के बारे में:
माइकल सिपसर द्वारा पी बनाम एनपी प्रश्न का इतिहास और स्थिति
एल बनाम मेवेरोमो द्वारा पी बनाम एनपी

जटिलता के सिद्धांत पर सबसे प्रसिद्ध और सम्मानित कार्यों में से एक:
गैरी एम।, जॉनसन डी। - कम्प्यूटिंग मशीनों और कठिन समस्याओं [1982]

सोचने के लिए टास्क

एसएटी की विसंगति, संबंधपरक बीजगणित और ब्रेकप्वाइंट समस्याएं।
तीन कथन दिए गए हैं:
1. प्रथम-क्रम तर्क और संबंधपरक बीजगणित में एक ही "कम्प्यूटेशनल जटिलता" है, अर्थात, यदि किसी कार्य में एक औपचारिकता में जटिलता X है, तो उसी जटिलता ( लिंक ) के साथ एक और औपचारिकता में इसकी अभिव्यक्ति है।
2. संबंधपरक बीजगणित सकर्मक समापन को व्यक्त करने में सक्षम नहीं है - कक्षा P में एक कार्य ( रिलेशनल बीजगणित: पारगमन बंद )
3. पहले क्रम के तर्क के लिए SAT एक स्टॉप समस्या के बराबर है और एल्गोरिदमिक रूप से असाध्य ( लिंक ) है।
प्रश्न: यह कैसे हो सकता है?