सबूत है कि रोकथाम समस्या एनपी-हार्ड है?

Question

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

this answer में, और एन पी-सम्पूर्ण, जेसन दावा करता है कि

हॉल्टिंग समस्या क्लासिक एनपी-हार्ड समस्या है। यह समस्या है कि एक प्रोग्राम पी और इनपुट I दिया, यह रोक दिया जाएगा? यह एक निर्णय समस्या है लेकिन यह एनपी में नहीं है। यह स्पष्ट है कि किसी भी एनपी-पूर्ण समस्या को इस पर कम किया जा सकता है।

जबकि मैं मानता हूँ कि हॉल्टिंग समस्या सहज एनपी में कुछ भी की तुलना में काफी "कठिन" समस्या है, मैं ईमानदारी से नहीं ऊपर एक औपचारिक, गणितीय प्रमाण है कि हॉल्टिंग समस्या एनपी कठिन है के साथ आ सकते हैं। विशेष रूप से, मुझे रोकथाम की समस्या पर एनपी (या कम से कम, किसी भी ज्ञात एनपी-पूर्ण समस्या) में हर समस्या के उदाहरणों से बहुपद-समय-एक मानचित्रण प्रतीत नहीं होता है।

क्या कोई सीधा प्रमाण है कि रोकथाम समस्या एनपी-हार्ड है?

Answer 1

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

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