एनपी-हार्ड और अपरिहार्य समस्याओं के बीच संबंध

Question

अनावश्यक समस्याओं और एनपी हार्ड समस्याओं के बीच संबंधों के बारे में थोड़ा उलझन में हूँ। क्या एनपी हार्ड समस्याएं अनावश्यक समस्याओं का एक उप-समूह हैं, या वे समान और समान हैं, या यह है कि वे तुलनीय नहीं हैं?

मेरे लिए, मैं अपने दोस्तों से बहस कर रहा हूं कि अनिश्चित समस्याएं एनपी हार्ड समस्याओं के लिए सुपरसैट हैं। वहां कुछ समस्याएं मौजूद होंगी जो एनपी हार्ड में नहीं हैं लेकिन अपरिहार्य हैं। लेकिन मुझे यह तर्क कमजोर होने के लिए मिल रहा है और थोड़ा उलझन में हूं। क्या एनपी-पूर्ण समस्याएं हैं जो अयोग्य हैं। क्या एनपी हार्ड में कोई समस्या है जो निर्णायक है .??

कुछ चर्चा बहुत मददगार होगी! धन्यवाद!

Answer 1

कुछ इनपुट के लिए अनिश्चित = असफल। इससे कोई फर्क नहीं पड़ता कि आप अपना एल्गोरिदम कितना (परिमित) समय देते हैं, यह हमेशा कुछ इनपुट पर गलत होगा।

एनपी-हार्ड ~ = सुपर-बहुपद चलने का समय (मानते हुए पी! = एनपी)। यह हाथ से भरा है, लेकिन मूल रूप से एनपी-हार्ड का मतलब है कि यह कम से कम उतना कठिन है जितना एनपी में सबसे कठिन समस्या है।

निश्चित रूप से ऐसी समस्याएं हैं जो एनपी-हार्ड हैं जो अपरिहार्य नहीं हैं (= निर्णायक हैं)। एसएटी का कहना है कि कोई एनपी-पूर्ण समस्या उनमें से एक होगी।

क्या ऐसी अनिश्चित समस्याएं हैं जो एनपी-हार्ड नहीं हैं? मुझे ऐसा नहीं लगता है, लेकिन इसे रद्द करना आसान नहीं है - मुझे एक स्पष्ट तर्क नहीं दिख रहा है कि एसएटी से सभी संभावित अपरिहार्य समस्याओं में कमी होनी चाहिए। कुछ अजीब अनावश्यक समस्याएं हो सकती हैं जो बहुत उपयोगी नहीं हैं। लेकिन मानक अपरिहार्य समस्याएं (रोकना समस्या, कहें) एनपी-हार्ड हैं।

Answer 2

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

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

इसलिए ट्यूरिंग-पूर्ण अपरिहार्य समस्या एनपी-हार्ड समस्याओं का एक सबसेट है।

Answer 3

अपरिहार्य समस्या उदा। ट्यूरिंग हैल्टिंग समस्या केवल एनपी-हार्ड है।

    <---------NP Hard------> 
|------------|-------------||-------------|------------|--------> Computational Difficulty 

|<----P--->| 

|<----------NP---------->| 

|<-----------Exponential----------->| 

|<---------------R (Finite Time)---------------->| 

इस चित्र में, कि छोटे पाइप एनपी और एनपी हार्ड और जो के अतिव्यापी से पता चलता एनपी पूर्णता, उन समस्याओं जो एनपी के साथ-साथ एनपी हार्ड हैं अर्थात् सेट दिखाता है।

अनिश्चित समस्याएं एनपी हार्ड समस्याएं हैं जिनके पास समाधान नहीं है और जो एनपी में नहीं हैं।