एनपी-हार्ड समस्याएं जो एनपी-पूर्ण नहीं हैं, कठिन हैं?

Question

मेरी समझ से, सभी एनपी-पूर्ण समस्याएं एनपी-हार्ड हैं लेकिन कुछ एनपी-हार्ड समस्याओं को एनपी-पूर्ण नहीं माना जाता है, और एनपी-हार्ड समस्याएं कम से कम एनपी-पूर्ण समस्याओं के रूप में कठिन होती हैं।

क्या इसका मतलब एनपी-हार्ड समस्याएं हैं जो एनपी-पूर्ण नहीं हैं? और यह कैसे कठिन है?

Answer 1

http://en.wikipedia.org/wiki/NP-hard#Examples

से भी निर्णय समस्याओं कि एनपी कठिन नहीं बल्कि एन पी-सम्पूर्ण हॉल्टिंग समस्या, उदाहरण के लिए कर रहे हैं। यह समस्या है जो "एक कार्यक्रम और उसके इनपुट को देखते हुए पूछता है, क्या यह हमेशा के लिए चलेगा?" यह एक हां/नहीं सवाल है, इसलिए यह एक निर्णय समस्या है। यह साबित करना आसान है कि रोकथाम की समस्या एनपी-हार्ड है लेकिन एनपी-पूर्ण नहीं है।

Answer 2

एनपी-हार्ड समस्याओं का सेट एनपी-पूर्ण समस्याओं के सेट का एक सुपरसेट है। एनपी की तुलना में जटिलता वर्ग अधिक "कठिन" हैं, उदाहरण के लिए PSPACE, EXPTIME या EXPSPACE, और इनमें से सभी में एनपी-हार्ड है लेकिन एनपी-पूर्ण समस्याएं नहीं हैं।

Answer 3

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

(i) एक निर्णय समस्या,
(ii) समस्या के समाधान की संख्या सीमित होना चाहिए और प्रत्येक समाधान बहुपद लंबाई का होना चाहिए, और
(iii) एक बहुपद लम्बाई समाधान दिया गया है, हमें यह कहने में सक्षम होना चाहिए कि समस्या का उत्तर हाँ/नहीं

अब यह देखना आसान है कि कई एनपी-हार्ड समस्याएं हो सकती हैं जो सेट से संबंधित नहीं हैं एनपी और हल करने के लिए कठिन हैं। एक सहज उदाहरण के रूप में, यात्रा विक्रेता के ऑप्टिमाइज़ेशन-संस्करण जहां हमें वास्तविक शेड्यूल ढूंढना है, यात्रा करने वाले विक्रेता के निर्णय-संस्करण से कठिन है, जहां हमें यह निर्धारित करने की आवश्यकता है कि लंबाई < = k मौजूद है या नहीं।

Answer 4

ट्यूरिंग मशीन रोकना समस्या ट्यूरिंग मशीनों और एनपी-हार्ड पर अनिश्चित है, लेकिन एनपीसी नहीं है। जाहिर है यह कठिन है;)

Answer 5

ट्यूरिंग रोक समस्या समस्या अनिश्चित है और यह एनपी-हार्ड सेट से संबंधित है। टिकाऊ समस्या को हल करने के लिए हमारे पास कोई निर्णायक नहीं है क्योंकि यह एक आरई भाषा है। तो हमारे पास इसे हल करने के लिए कोई एल्गोरिदम नहीं है। इस प्रकार यह स्पष्ट है कि एनपी-हार्ड सेट में असफल समस्याएं भी हैं। इसलिए एनपी-हार्ड सेट में ऐसी भाषाएं या समस्याएं भी होती हैं जिनके लिए हमारे पास हल करने के लिए कोई एल्गोरिदम नहीं है।

Answer 6

1. एनपी-पूर्ण एनपी और एनपी-हार्ड होना चाहिए।
2. और एनपी-हार्ड जो एनपी-पूर्ण नहीं हैं एनपी नहीं हैं।
3. अब एनपी की परिभाषा के अनुसार कोई ऐसा व्यक्ति है जो समस्या के लिए उत्तर उदाहरण देता है। और सत्यापित करने के लिए सत्यापनकर्ता है।
4. इसका मतलब है कि एनपी-हार्ड में उनमें से कोई भी नहीं है। इसलिए उन्हें हल करना मुश्किल है।

की