बहुपद-समय सन्निकटन योजना
कंप्यूटर विज्ञान (विशेष रूप से एल्गोरिथम) में, एक बहुपद-समय सन्निकटन योजना (पीटीएएस) अनुकूलन समस्याओं (अक्सर, एनपी कठिन अनुकूलन समस्याओं) के लिए एक प्रकार का सन्निकटन एल्गोरिदम है।
पीटीएएस एक एल्गोरिदम है जो एक अनुकूलन समस्या और एक पैरामीटर का उदाहरण लेता है ε > 0 और एक समाधान उत्पन्न करता है जो एक कारक के भीतर होता है 1 + ε इष्टतम होने का (या 1 – ε अधिकतमीकरण समस्याओं के लिए)। उदाहरण के लिए, यूक्लिडियन ट्रैवलिंग सेल्समैन की समस्या के लिए, एक पीटीएएस अधिकतम लंबाई वाला टूर तैयार करेगा (1 + ε)L, साथ L सबसे छोटे दौरे की लंबाई है।[1] प्रत्येक निश्चित ε के लिए समस्या आकार में PTAS का चलने का समय बहुपद होना आवश्यक है, लेकिन विभिन्न ε के लिए भिन्न हो सकता है। इस प्रकार समय में चलने वाला एक एल्गोरिदम O(n1/ε) या और भी O(nexp(1/ε)) को पीटीएएस के रूप में गिना जाता है।
वेरिएंट
नियतात्मक
पीटीएएस एल्गोरिदम के साथ एक व्यावहारिक समस्या यह है कि ε सिकुड़ने पर बहुपद का घातांक नाटकीय रूप से बढ़ सकता है, उदाहरण के लिए यदि रनटाइम है O(n(1/ε)!). इसे संबोधित करने का एक तरीका कुशल बहुपद-समय सन्निकटन योजना या ईपीटीएएस को परिभाषित करना है, जिसमें चलने का समय आवश्यक है O(nc) एक स्थिरांक के लिए c स्वतंत्र ε. यह सुनिश्चित करता है कि समस्या के आकार में वृद्धि का रनटाइम पर समान सापेक्ष प्रभाव पड़ता है, भले ही ε का उपयोग किया जा रहा हो; हालाँकि, बिग ओ अंकन के तहत स्थिरांक | बिग-ओ अभी भी मनमाने ढंग से ε पर निर्भर हो सकता है। दूसरे शब्दों में, एक ईपीटीएएस फिक्स्ड-पैरामीटर एल्गोरिदम समय में चलता है जहां पैरामीटर ε है।
व्यवहार में और भी अधिक प्रतिबंधात्मक और उपयोगी, पूरी तरह से बहुपद-समय सन्निकटन योजना या एफपीटीएएस है, जिसके लिए एल्गोरिदम को समस्या आकार दोनों में बहुपद होना आवश्यक है n और 1/ε.
जब तक कि P = NP समस्या नहीं है|P = NP, यह ऐसा ही मानता है FPTAS ⊊ PTAS ⊊ APX.[2] नतीजतन, इस धारणा के तहत, APX-कठिन समस्याओं में PTAS नहीं होते हैं।
पीटीएएस का एक अन्य नियतात्मक संस्करण अर्ध-बहुपद-समय सन्निकटन योजना है|अर्ध-बहुपद-समय सन्निकटन योजना या क्यूपीटीएएस। QPTAS में समय जटिलता होती है npolylog(n)प्रत्येक निश्चित के लिए ε > 0. इसके अलावा, एक पीटीएएस समस्या के कुछ पैरामीटराइजेशन के लिए फिक्स्ड-पैरामीटर एल्गोरिदम समय में चल सकता है, जो एक पैरामीटराइज्ड सन्निकटन एल्गोरिदम की ओर ले जाता है।
यादृच्छिक
कुछ समस्याएं जिनमें पीटीएएस नहीं है, वे समान गुणों वाले एक यादृच्छिक एल्गोरिदम, एक बहुपद-समय यादृच्छिक सन्निकटन योजना या पीआरएएस को स्वीकार कर सकती हैं। पीआरएएस एक एल्गोरिदम है जो एक अनुकूलन या गिनती समस्या और एक पैरामीटर का उदाहरण लेता है ε > 0 और, बहुपद समय में, एक समाधान उत्पन्न करता है जिसकी एक कारक के भीतर होने की उच्च संभावना होती है ε इष्टतम का. परंपरागत रूप से, उच्च संभावना का मतलब 3/4 से अधिक संभावना है, हालांकि अधिकांश संभाव्य जटिलता वर्गों के साथ परिभाषा इस सटीक मूल्य में भिन्नता के लिए मजबूत है (न्यूनतम आवश्यकता आम तौर पर 1/2 से अधिक है)। पीटीएएस की तरह, पीआरएएस में रनिंग टाइम बहुपद होना चाहिए n, लेकिन जरूरी नहीं कि अंदर ही हो ε; चलने के समय पर अतिरिक्त प्रतिबंधों के साथ ε, कोई EPTAS के समान एक कुशल बहुपद-समय यादृच्छिक सन्निकटन योजना या EPRAS को परिभाषित कर सकता है, और FPTAS के समान एक पूर्ण बहुपद-समय यादृच्छिक सन्निकटन योजना या FPRAS को परिभाषित कर सकता है।[3]
एक जटिलता वर्ग के रूप में
पीटीएएस शब्द का उपयोग पीटीएएस वाली अनुकूलन समस्याओं के वर्ग को संदर्भित करने के लिए भी किया जा सकता है। पीटीएएस APX का एक उपसमुच्चय है, और जब तक पी = एनपी समस्या नहीं है|पी = एनपी, यह एक सख्त उपसमुच्चय है। [2] पीटीएएस में सदस्यता को पीटीएएस कटौती, एल-कमी, या अनुमान-संरक्षण कटौती#ए-कमी और पी-कमी|पी-कमी का उपयोग करके दिखाया जा सकता है, जो सभी पीटीएएस सदस्यता को संरक्षित करते हैं, और इनका उपयोग पीटीएएस को प्रदर्शित करने के लिए भी किया जा सकता है- पूर्णता. दूसरी ओर, पीटीएएस में गैर-सदस्यता दिखाना (अर्थात्, पीटीएएस का अस्तित्वहीन होना), यह दिखाकर किया जा सकता है कि समस्या एपीएक्स-हार्ड है, जिसके बाद पीटीएएस का अस्तित्व पी = एनपी दिखाएगा। APX-कठोरता को आमतौर पर PTAS कमी या सन्निकटन-संरक्षण कमी#AP-कमी|AP-कमी के माध्यम से दिखाया जाता है।
यह भी देखें
- पैरामीटरयुक्त सन्निकटन एल्गोरिथ्म, एक सन्निकटन योजना जो फिक्स्ड-पैरामीटर एल्गोरिथ्म समय में चलती है
संदर्भ
- ↑ Sanjeev Arora, Polynomial-time Approximation Schemes for Euclidean TSP and other Geometric Problems, Journal of the ACM 45(5) 753–782, 1998.
- ↑ 2.0 2.1 Jansen, Thomas (1998), "Introduction to the Theory of Complexity and Approximation Algorithms", in Mayr, Ernst W.; Prömel, Hans Jürgen; Steger, Angelika (eds.), Lectures on Proof Verification and Approximation Algorithms, Springer, pp. 5–28, doi:10.1007/BFb0053011, ISBN 9783540642015. See discussion following Definition 1.30 on p. 20.
- ↑ Vazirani, Vijay V. (2003). Approximation Algorithms. Berlin: Springer. pp. 294–295. ISBN 3-540-65367-8.
बाहरी संबंध
- Complexity Zoo: PTAS, EPTAS.
- Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski, and Gerhard Woeginger, A compendium of NP optimization problems – list which NP optimization problems have PTAS.
