APX

For other uses, see APX (disambiguation).

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

एक सन्निकटन कलन विधि को a कहा जाता है $f(n)$-इनपुट आकार के लिए सन्निकटन एल्गोरिथ्म $n$ यदि यह सिद्ध किया जा सके कि एल्गोरिथम जो समाधान ढूंढता है वह अधिकतम गुणात्मक कारक है $f(n)$ इष्टतम समाधान से कई गुना बदतर। यहाँ, $f(n)$ सन्निकटन अनुपात कहलाता है। एपीएक्स में समस्याएं एल्गोरिदम के साथ होती हैं जिनके लिए सन्निकटन अनुपात होता है $f(n)$ एक स्थिरांक है $c$. सन्निकटन अनुपात पारंपरिक रूप से 1 से अधिक बताया गया है। न्यूनतमकरण समस्याओं के मामले में, $f(n)$ पाए गए समाधान के स्कोर को इष्टतम समाधान के स्कोर से विभाजित किया जाता है, जबकि अधिकतमकरण समस्याओं के लिए स्थिति विपरीत होती है। अधिकतमीकरण समस्याओं के लिए, जहां निम्नतर समाधान का स्कोर छोटा होता है, $f(n)$ कभी-कभी 1 से कम बताया जाता है; ऐसे मामलों में, का पारस्परिक $f(n)$ पाए गए समाधान के स्कोर का इष्टतम समाधान के स्कोर से अनुपात है।

एक समस्या को एक बहुपद-समय सन्निकटन योजना कहा जाता है | बहुपद-समय सन्निकटन योजना (पीटीएएस) यदि इष्टतम के प्रत्येक गुणक कारक के लिए 1 से भी बदतर समस्या को हल करने के लिए एक बहुपद-समय एल्गोरिथ्म है। कारक। जब तक पी = एनपी समस्या नहीं है|पी = एनपी ऐसी समस्याएं मौजूद हैं जो एपीएक्स में हैं लेकिन पीटीएएस के बिना, इसलिए पीटीएएस के साथ समस्याओं का वर्ग सख्ती से एपीएक्स में निहित है। ऐसी ही एक समस्या है बिन पैकिंग की समस्या।

एपीएक्स-कठोरता और एपीएक्स-पूर्णता

किसी समस्या को एपीएक्स-हार्ड कहा जाता है यदि एपीएक्स में प्रत्येक समस्या से उस समस्या में पीटीएएस कमी होती है, और यदि समस्या एपीएक्स-हार्ड है और एपीएक्स में भी है तो उसे एपीएक्स-पूर्ण कहा जाता है। P ≠ NP ⇒ PTAS ≠ APX के परिणामस्वरूप, यदि P ≠ NP मान लिया जाए, तो किसी APX-हार्ड समस्या में PTAS नहीं है। व्यवहार में, एपीएक्स-पूर्णता प्रदर्शित करने के लिए एक समस्या को दूसरे में कम करना अक्सर अन्य कटौती योजनाओं का उपयोग करके किया जाता है, जैसे कि एल-कटौती, जो पीटीएएस कटौती का संकेत देती है।

उदाहरण

सबसे सरल APX-पूर्ण समस्याओं में से एक MAX-3SAT|MAX-3SAT-3 है, जो बूलियन संतुष्टि समस्या का एक रूप है। इस समस्या में, हमारे पास संयोजनात्मक सामान्य रूप में एक बूलियन सूत्र है जहां प्रत्येक चर अधिकतम 3 बार दिखाई देता है, और हम अधिकतम संख्या में खंड जानना चाहते हैं जिन्हें चर के लिए सही/गलत मानों के एकल असाइनमेंट द्वारा एक साथ संतुष्ट किया जा सकता है।

अन्य APX-पूर्ण समस्याओं में शामिल हैं:

• स्वतंत्र सेट (ग्राफ़ सिद्धांत)#बाउंड-डिग्री ग्राफ़ में सन्निकटन एल्गोरिदम (यहां, सन्निकटन अनुपात ग्राफ़ की अधिकतम डिग्री पर निर्भर करता है, लेकिन अधिकतम डिग्री तय होने पर स्थिर होता है)।
• वर्टेक्स कवर#अनुमानित मूल्यांकन। किसी भी अधिकतम स्वतंत्र सेट का पूरक एक शीर्ष आवरण होना चाहिए।
• डॉमिनेटिंग सेट#एल्गोरिदम और बाउंडेड-डिग्री ग्राफ़ में कम्प्यूटेशनल जटिलता।
• ट्रैवलिंग सेल्समैन समस्या#अनुमान की जटिलता जब ग्राफ़ में दूरियाँ एक मीट्रिक (गणित) की शर्तों को पूरा करती हैं। टीएसपी सामान्य स्थिति में कॉम्बिनेटोरियल_ऑप्टिमाइज़ेशन#एनपी_ऑप्टिमाइज़ेशन_प्रॉब्लम|एनपीओ-पूर्ण है।
• सेट कवर से एल-कमी के माध्यम से टोकन पुनटोकन पुनर्विन्यास समस्या।

संबंधित जटिलता वर्ग

पीटीएएस

Main article: Polynomial-time approximation scheme

पीटीएएस (बहुपद समय सन्निकटन योजना) में ऐसी समस्याएं शामिल हैं जिनका अनुमान 1 समय के अलावा किसी भी स्थिर कारक के भीतर लगाया जा सकता है जो कि इनपुट आकार के लिए बहुपद है, लेकिन बहुपद ऐसे कारक पर निर्भर करता है। यह वर्ग APX का एक उपसमुच्चय है।

एपीएक्स-मध्यवर्ती

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

संभावित एपीएक्स-मध्यवर्ती समस्या का एक अन्य उदाहरण एज कलरिंग#एल्गोरिदम है जो रंगों की इष्टतम संख्या से अधिक का उपयोग करता है।

एफ(एन)-एपीएक्स

कोई जटिलता वर्गों के परिवार को भी परिभाषित कर सकता है $f(n)$-एपीएक्स, कहां $f(n)$-एपीएक्स में बहुपद समय सन्निकटन एल्गोरिदम के साथ समस्याएं हैं $O(f(n))$ सन्निकटन अनुपात. कोई अनुरूप रूप से परिभाषित कर सकता है $f(n)$-एपीएक्स-पूर्ण कक्षाएं; ऐसी कुछ कक्षाओं में सुप्रसिद्ध अनुकूलन समस्याएँ होती हैं। लॉग-एपीएक्स-पूर्णता और पॉली-एपीएक्स-पूर्णता को पीटीएएस-कटौती के बजाय अनुमान-संरक्षण कमी#एपी-कमी|एपी-कटौती के संदर्भ में परिभाषित किया गया है; ऐसा इसलिए है क्योंकि पीटीएएस-कटौती लॉग-एपीएक्स और पॉली-एपीएक्स में सदस्यता को संरक्षित करने के लिए पर्याप्त मजबूत नहीं है, भले ही वे एपीएक्स के लिए पर्याप्त हों।

लॉग-एपीएक्स-पूर्ण, जिसमें सबसे कठिन समस्याएं शामिल हैं जिन्हें इनपुट आकार में कारक लॉगरिदमिक के भीतर कुशलतापूर्वक अनुमानित किया जा सकता है, इसमें डोमिनेटिंग सेट # एल्गोरिदम और डिग्री असीमित होने पर कम्प्यूटेशनल जटिलता शामिल है।

पॉली-एपीएक्स-पूर्ण, जिसमें सबसे कठिन समस्याएं शामिल हैं जिन्हें इनपुट आकार में एक कारक बहुपद के भीतर कुशलतापूर्वक अनुमानित किया जा सकता है, इसमें सामान्य मामले में स्वतंत्र सेट (ग्राफ सिद्धांत) #अनुमान एल्गोरिदम शामिल हैं।

ऐसी समस्याएं भी मौजूद हैं जो exp-APX-पूर्ण हैं, जहां इनपुट आकार में सन्निकटन अनुपात घातीय है। ऐसा तब हो सकता है जब सन्निकटन समस्या उदाहरण के भीतर संख्याओं के मान पर निर्भर हो; इन संख्याओं को उनके मान में अंतरिक्ष लघुगणक में व्यक्त किया जा सकता है, इसलिए यह घातीय कारक है।

यह भी देखें

• अनुमान-संरक्षण कमी
• जटिलता वर्ग
• सन्निकटन एल्गोरिथ्म
• अधिकतम/मिनट सीएसपी/वन्स वर्गीकरण प्रमेय - प्रमेयों का एक सेट जो बूलियन संबंधों के बारे में समस्याओं के यांत्रिक वर्गीकरण को अनुमानित जटिलता वर्गों में सक्षम बनाता है
• मैक्सएसएनपी - एक निकट से संबंधित उपवर्ग

संदर्भ

• Complexity Zoo: APX
• C. Papadimitriou and M. Yannakakis. Optimization, approximation and complexity classes. Journal of Computer and System Sciences, 43:425–440, 1991.
• Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski and Gerhard Woeginger. Maximum Satisfiability Archived 2007-04-13 at the Wayback Machine. A compendium of NP optimization problems Archived 2007-04-05 at the Wayback Machine.