सशक्त एनपी-पूर्णता
कम्प्यूटेशनल काम्प्लेक्स सिद्धांत में, सशक्त NP-पूर्णता कम्प्यूटेशनल समस्याओं की प्रोपर्टी है जो NP-पूर्णता का विशेष स्थिति है। सामान्य कम्प्यूटेशनल समस्या में संख्यात्मक मापदंड हो सकते हैं। उदाहरण के लिए, बिन पैकिंग समस्या का इनपुट विशिष्ट आकार की वस्तुओं की सूची है और बिन्स के लिए आकार है जिसमें वस्तुएं होनी चाहिए - यह वस्तु आकार और बिन आकार संख्यात्मक मापदंड हैं।
किसी समस्या को दृढ़ता से NP-पूर्ण (सशक्त अर्थ में NP-पूर्ण) कहा जाता है, यदि वह NP-पूर्ण बनी रहती है, तथापि उसके सभी संख्यात्मक मापदंड इनपुट की लंबाई में बहुपद से बंधे होंते है।[1] समस्या को दृढ़ता से NP हार्ड कहा जाता है यदि दृढ़ता से NP-पूर्ण समस्या में बहुपद कमी होती है; कॉम्बिनेटरियल ऑप्टिमाइज़ेशन में, विशेष रूप से, दृढ़ता से NP-हार्ड वाक्यांश उन समस्याओं के लिए आरक्षित है जिन्हें किसी अन्य दृढ़ता से NP-पूर्ण समस्या के लिए बहुपद कमी के रूप में नहीं जाना जाता है।
सामान्यतः किसी समस्या के संख्यात्मक मापदंड पोजिसनल नोटेशन में दिए जाते हैं, इसलिए इनपुट आकार n की समस्या में ऐसे मापदंड हो सकते हैं जिनका आकार n में घातीय फ़ंक्शन है। यदि हम समस्या को यूनरी नोटेशन में दिए गए मापदंडों के लिए फिर से परिभाषित करते हैं, जिससे मापदंडों को इनपुट आकार द्वारा सीमित किया जाना चाहिए। इस प्रकार सशक्त NP-पूर्णता या NP-कठोरता को समस्या के इस एकल वर्जन की NP-पूर्णता या NP-कठोरता के रूप में भी परिभाषित किया जा सकता है।
उदाहरण के लिए, बिन पैकिंग दृढ़ता से NP-पूर्ण है जबकि 0-1 नैपसैक समस्या केवल अशक्त NP-पूर्ण है। इस प्रकार बिन पैकिंग का वर्जन जहां ऑब्जेक्ट और बिन आकार बहुपद से घिरे पूर्णांक होते हैं, NP-पूर्ण रहता है, जबकि नैपसैक समस्या के संबंधित वर्जन को डायनामिक प्रोग्रामिंग द्वारा छद्म-बहुपद समय में हल किया जा सकता है।
सैद्धांतिक दृष्टिकोण से, बहुपद से बंधे उद्देश्य फ़ंक्शन के साथ किसी भी दृढ़ता से NP-हार्ड अनुकूलन समस्या में फुली-पालीनोमिअल-टाइम-अप्प्रोक्सिमेशन-स्कीम (या fptas) नहीं हो सकती है जब तक कि P = NP नही होता है।[2][3] चूँकि, उलटा विफल रहता है: उदा. यदि P, NP के सामान नहीं है, तो नैपसैक समस्याओं की सूची एकाधिक बाधाएं दृढ़ता से NP-हार्ड नहीं हैं, किन्तु ओप्तिमम उद्देश्य बहुपद रूप से बंधे होने पर भी कोई एफपीटीएएस नहीं है।[4]
कुछ दृढ़तापूर्वक NP-पूर्ण समस्याओं को अभी भी औसतन हल करना सरल हो सकता है, किन्तु इसकी अधिक संभावना है कि व्यवहार में कठिन उदाहरणों का सामना करना पड़ता है।
Strong and weak NP-hardness vs. strong and weak polynomial-time algorithms
Assuming P ≠ NP, the following are true for computational problems on integers:[5]
- 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.
संदर्भ
- ↑ Garey, M. R.; Johnson, D. S. (July 1978). "'Strong' NP-Completeness Results: Motivation, Examples, and Implications". Journal of the Association for Computing Machinery. New York, NY: ACM. 25 (3): 499–508. doi:10.1145/322077.322090. ISSN 0004-5411. MR 0478747. S2CID 18371269.
- ↑ Vazirani, Vijay V. (2003). Approximation Algorithms. Berlin: Springer. pp. 294–295. ISBN 3-540-65367-8. MR 1851303.
- ↑ Garey, M. R.; Johnson, D. S. (1979). Victor Klee (ed.). Computers and Intractability: A Guide to the Theory of NP-Completeness. A Series of Books in the Mathematical Sciences. San Francisco, Calif.: W. H. Freeman and Co. pp. x+338. ISBN 0-7167-1045-5. MR 0519066.
- ↑ H. Kellerer; U. Pferschy; D. Pisinger (2004). बस्ता समस्याएँ. Springer.
- ↑ Demaine, Erik. "Algorithmic Lower Bounds: Fun with Hardness Proofs, Lecture 2".
