सशक्त एनपी-पूर्णता

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

किसी समस्या को दृढ़ता से एनपी-पूर्ण (मजबूत अर्थ में एनपी-पूर्ण) कहा जाता है, यदि वह एनपी-पूर्ण बनी रहती है, भले ही उसके सभी संख्यात्मक पैरामीटर इनपुट की लंबाई में एक बहुपद से बंधे हों। एक समस्या को दृढ़ता से एनपी कठिन कहा जाता है यदि एक दृढ़ता से एनपी-पूर्ण समस्या में बहुपद कमी होती है; कॉम्बिनेटरियल ऑप्टिमाइज़ेशन में, विशेष रूप से, दृढ़ता से एनपी-हार्ड वाक्यांश उन समस्याओं के लिए आरक्षित है जिन्हें किसी अन्य दृढ़ता से एनपी-पूर्ण समस्या के लिए बहुपद कमी के रूप में नहीं जाना जाता है।

आम तौर पर किसी समस्या के संख्यात्मक पैरामीटर स्थितीय संकेतन में दिए जाते हैं, इसलिए इनपुट आकार n की समस्या में ऐसे पैरामीटर हो सकते हैं जिनका आकार n में घातीय फ़ंक्शन है। यदि हम समस्या को एकात्मक अंक प्रणाली में दिए गए मापदंडों के लिए फिर से परिभाषित करते हैं, तो मापदंडों को इनपुट आकार द्वारा सीमित किया जाना चाहिए। इस प्रकार मजबूत एनपी-पूर्णता या एनपी-कठोरता को समस्या के इस एकल संस्करण की एनपी-पूर्णता या एनपी-कठोरता के रूप में भी परिभाषित किया जा सकता है।

उदाहरण के लिए, बिन पैकिंग दृढ़ता से एनपी-पूर्ण है जबकि 0-1 नैपसैक समस्या केवल कमजोर एनपी-पूर्ण है। इस प्रकार बिन पैकिंग का संस्करण जहां ऑब्जेक्ट और बिन आकार एक बहुपद से घिरे पूर्णांक होते हैं, एनपी-पूर्ण रहता है, जबकि नैपसैक समस्या के संबंधित संस्करण को गतिशील प्रोग्रामिंग द्वारा छद्म-बहुपद समय में हल किया जा सकता है।

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

Strong and weak NP-hardness vs. strong and weak polynomial-time algorithms

Assuming P ≠ NP, the following are true for computational problems on integers:

• If a problem is weakly NP-hard, then it does not have a weakly polynomial time algorithm (polynomial in the number of integers and the number of bits in the largest integer), but it may have a pseudopolynomial time algorithm (polynomial in the number of integers and the magnitude of the largest integer). An example is the partition problem. Both weak NP-hardness and weak polynomial-time correspond to encoding the input agents in binary coding.

• If a problem is strongly NP-hard, then it does not even have a pseudo-polynomial time algorithm. It also does not have a fully-polynomial time approximation scheme. An example is the 3-partition problem. Both strong NP-hardness and pseudo-polynomial time correspond to encoding the input agents in unary coding.