Valiant–Vazirani theorem
वीरता-वजीरानी प्रमेय कम्प्यूटेशनल जटिलता सिद्धांत में एक प्रमेय है जिसमें कहा गया है कि यदि असंदिग्ध-एसएटी के लिए एक बहुपद समय एल्गोरिथ्म है, तो एनपी = आरपी। यह लेस्ली वैलियंट और विजय वजीरानी द्वारा अपने पेपर एन. पी. में साबित किया गया था जो 1986 में प्रकाशित अद्वितीय समाधानों का पता लगाने जितना आसान है। सबूत मुलमुली-वजीरानी-वजीरानी अलगाव लेम्मा पर आधारित है, जिसका उपयोग बाद में सैद्धांतिक कंप्यूटर विज्ञान में कई महत्वपूर्ण अनुप्रयोगों के लिए किया गया था। वीरता-वजीरानी प्रमेय का तात्पर्य है कि बूलियन संतोषजनक समस्या, जो एन. पी.-पूर्ण है, एक कम्प्यूटेशनल रूप से कठिन समस्या बनी हुई है, भले ही इनपुट उदाहरणों में अधिक से अधिक एक संतोषजनक कार्य होने का वादा किया गया हो। सबूत की रूपरेखा असंदिग्ध-एसएटी यह तय करने की समस्या है कि क्या एक दिया गया बूलियन सूत्र जिसमें अधिक से अधिक एक संतोषजनक कार्य है, असंतोषजनक है या वास्तव में एक संतोषजनक कार्य है। पहले मामले में, असंदिग्ध-एसएटी के लिए एक एल्गोरिथ्म को अस्वीकार कर देना चाहिए, और दूसरे में इसे सूत्र को स्वीकार करना चाहिए। यदि सूत्र में एक से अधिक संतोषजनक कार्य हैं, तो एल्गोरिथ्म के व्यवहार पर कोई शर्त नहीं है। वादा समस्या असंदिग्ध-एसएटी को एक गैर-निर्धारक ट्यूरिंग मशीन द्वारा तय किया जा सकता है जिसमें अधिकतम एक स्वीकार करने वाला गणना मार्ग होता है। इस अर्थ में, यह वादा समस्या जटिलता वर्ग यूपी (जिसे आमतौर पर केवल भाषाओं के लिए परिभाषित किया जाता है) से संबंधित है। वीरता-वजीरानी प्रमेय के प्रमाण में एस. ए. टी. से एस. ए. टी. में एक संभावित कमी शामिल है, जैसे कि कम से कम संभावना के साथ, उत्पादन सूत्र में अधिक से अधिक एक संतोषजनक कार्य होता है, और इस प्रकार असंदिग्ध-एस. ए. टी. समस्या के वादे को पूरा करता है। अधिक सटीक रूप से, कमी एक यादृच्छिक बहुपद-समय एल्गोरिथ्म है जो एक बूलियन सूत्र के लिए चर के साथ एक बूलियन सूत्र का मानचित्रण करता है जैसे कि प्रत्येक संतोषजनक कार्य भी संतुष्ट करता है, और यदि संतोषजनक है, तो, कम से कम संभावना के साथ, एक अद्वितीय संतोषजनक कार्य है। कमी को कई बार बहुपद संख्या में चलाने से, हर बार ताजा स्वतंत्र यादृच्छिक बिट्स के साथ, हमें सूत्र मिलते हैं। चुनने पर, हम पाते हैं कि कम से कम एक सूत्र के विशिष्ट रूप से संतोषजनक होने की संभावना कम से कम संतोषजनक है। यह ट्यूरिंग को एस. ए. टी. से असंदिग्ध-एस. ए. टी. में कमी देता है क्योंकि असंदिग्ध-एस. ए. टी. के लिए एक अनुमानित एल्गोरिथ्म को एस. ए. टी. पर लागू किया जा सकता है। फिर एस. ए. टी. की आत्म-न्यूनीकरण क्षमता का उपयोग एक संतोषजनक कार्य की गणना करने के लिए किया जा सकता है, यदि यह मौजूद है। कुल मिलाकर, यह साबित करता है कि एनपी = आरपी यदि असंदिग्ध-एसएटी को आरपी में हल किया जा सकता है। कमी का विचार सूत्र के समाधान स्थान को यादृच्छिक एफ़ाइन हाइपरप्लेन के साथ काटना है, जहां यादृच्छिक रूप से समान रूप से चुना जाता है। एक वैकल्पिक प्रमाण मुलमुली, वजीरानी और वजीरानी द्वारा अलग किए गए सिद्धांत पर आधारित है। वे एक अधिक सामान्य सेटिंग पर विचार करते हैं, और यहाँ सेटिंग पर लागू किया जाता है यह केवल एक अलगाव संभावना देता है। संरचनात्मक जटिलता सिद्धांत कम्प्यूटेशनल जटिलता सिद्धांत में प्रमेय