बहुपद-समय सन्निकटन योजना: Difference between revisions
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
{{short description|Type of approximation algorithm}} | {{short description|Type of approximation algorithm}} | ||
[[कंप्यूटर विज्ञान]] (विशेष रूप से [[एल्गोरिथम]]) में, एक बहुपद-समय सन्निकटन योजना (पीटीएएस) [[अनुकूलन समस्या]]ओं ( | [[कंप्यूटर विज्ञान]] (विशेष रूप से [[एल्गोरिथम]]) में, '''एक बहुपद-समय सन्निकटन योजना (पीटीएएस)''' [[अनुकूलन समस्या]]ओं (अधिकांशतः, [[ एनपी कठिन |एनपी-कठोरता]] अनुकूलन समस्याओं) के लिए एक प्रकार का सन्निकटन एल्गोरिदम होता है। | ||
पीटीएएस एक एल्गोरिदम है जो एक अनुकूलन समस्या और एक पैरामीटर | पीटीएएस एक एल्गोरिदम होता है जो एक अनुकूलन समस्या और एक पैरामीटर {{math|ε > 0}} का उदाहरण लेता है और एक समाधान उत्पन्न करता है जो एक सर्वोत्तम होने का कारक {{math|1 + ε}} (या {{math|1 – ε}} अधिकतमीकरण समस्याओं के लिए) के भीतर उपस्होथित होता है। उदाहरण के लिए, यूक्लिडियन [[ट्रैवलिंग सेल्समैन की समस्या]] के लिए, एक पीटीएएस अधिकतम {{math|(1 + ε)''L''}} लंबाई वाला यात्रा करेगा, जहाँ {{mvar|L}} सबसे छोटे यात्रा की लंबाई होती है।<ref>[[Sanjeev Arora]], Polynomial-time Approximation Schemes for Euclidean TSP and other Geometric Problems, Journal of the ACM 45(5) 753–782, 1998.</ref> इस प्रकार प्रत्येक निश्चित ε के लिए समस्या आकार में पीटीएएस का चलने का समय बहुपद का उपस्थित होना आवश्यक होता है, परन्तु विभिन्न ε के लिए भिन्न हो सकता है। इस प्रकार समय में चलने वाला एक एल्गोरिदम {{math|''[[Big O notation|O]]''(''n''{{sup|1/ε}})}} या और भी {{math|''O''(''n''{{sup|exp(1/ε)}})}} को पीटीएएस के रूप में गिना जाता है। | ||
== | ==भिन्न रूप== | ||
===नियतात्मक=== | ===नियतात्मक=== | ||
पीटीएएस एल्गोरिदम के साथ एक व्यावहारिक समस्या यह है कि ε सिकुड़ने पर बहुपद का घातांक नाटकीय रूप से बढ़ सकता है, उदाहरण के लिए यदि रनटाइम | पीटीएएस एल्गोरिदम के साथ एक व्यावहारिक समस्या यह होती है कि ε सिकुड़ने पर बहुपद का घातांक नाटकीय रूप से बढ़ सकता है, उदाहरण के लिए यदि रनटाइम {{math|''O''(''n''{{sup|(1/ε)!}})}} होता है। इसे संबोधित करने का एक विधि '''कुशल बहुपद-समय सन्निकटन योजना या ईपीटीएएस''' को परिभाषित करना पड़ता है, जिसमें {{math|ε}} से स्वतंत्र निरंतर {{mvar|c}} के लिए चलने का समय {{math|''O''(''n''{{sup|''c''}})}} होना आवश्यक होता है। यह सुनिश्चित करता है कि समस्या के आकार में वृद्धि का रनटाइम पर समान सापेक्ष प्रभाव पड़ता है, भले ही ε का उपयोग किया जा रहा हो; यघपि, [[ बिग ओ अंकन |बिग ओ अंकन]] के तहत स्थिरांक अभी भी इच्छानुसार ढंग से ε पर निर्भर हो सकता है। दूसरे शब्दों में, एक ईपीटीएएस [[फिक्स्ड-पैरामीटर एल्गोरिदम]] समय में चलता है जहां पैरामीटर ε होता है। | ||
इससे भी अधिक प्रतिबंधात्मक, और व्यवहार में उपयोगी, [[पूरी तरह से बहुपद-समय सन्निकटन योजना]] या '''एफपीटीएएस''' उपस्थित होती है, जिसके लिए एल्गोरिथ्म को समस्या आकार n और 1/ε दोनों में बहुपद होना आवश्यक होता है। | |||
जब तक कि P = NP समस्या | जब तक कि P = NP समस्या ना हो, तब तक {{nowrap|FPTAS ⊊ PTAS ⊊ [[APX]]}} होता है।<ref name=Jansen>{{citation|first=Thomas|last=Jansen|contribution=Introduction to the Theory of Complexity and Approximation Algorithms|pages=5–28|title=Lectures on Proof Verification and Approximation Algorithms|editor1-first=Ernst W.|editor1-last=Mayr|editor2-first=Hans Jürgen|editor2-last=Prömel|editor3-first=Angelika|editor3-last=Steger|editor3-link=Angelika Steger|publisher=Springer|year=1998|isbn=9783540642015|doi=10.1007/BFb0053011}}. See discussion following Definition 1.30 on [https://books.google.com/books?id=_C8Ly1ya4cgC&pg=PA20 p. 20].</ref> परिणामस्वरूप, इस धारणा के अनुसार, APX-कठोर समस्याओं में PTAS नहीं होते हैं। | ||
पीटीएएस का एक अन्य नियतात्मक संस्करण [[अर्ध-बहुपद-समय सन्निकटन योजना]] | पीटीएएस का एक अन्य नियतात्मक संस्करण [[अर्ध-बहुपद-समय सन्निकटन योजना]] या '''क्यूपीटीएएस''' होता है। एक क्यूपीटीएएस में प्रत्येक निश्चित ε > 0 के लिए समय जटिलता {{math|''n''{{sup|[[Polylogarithmic function|polylog]](''n'')}}}} होती। इसके अतिरिक्त, इस प्रकार पीटीएएस समस्या के कुछ मानकीकरण के लिए फिक्स्ड-पैरामीटर एल्गोरिदम FPT समय में चल सकता है, जो एक पैरामीटराइज्ड सन्निकटन एल्गोरिदम की ओर ले जाता है। | ||
===यादृच्छिक=== | ===यादृच्छिक=== | ||
कुछ समस्याएं जिनमें पीटीएएस नहीं है, वे समान गुणों वाले एक [[यादृच्छिक एल्गोरिदम]], एक बहुपद-समय यादृच्छिक सन्निकटन योजना या पीआरएएस को स्वीकार कर सकती हैं। पीआरएएस एक एल्गोरिदम है जो एक अनुकूलन या गिनती समस्या और एक पैरामीटर | कुछ समस्याएं जिनमें पीटीएएस नहीं होती है, वे समान गुणों वाले एक [[यादृच्छिक एल्गोरिदम]], एक '''बहुपद-समय यादृच्छिक सन्निकटन योजना या पीआरएएस''' को स्वीकार कर सकती हैं। पीआरएएस एक एल्गोरिदम होता है जो एक अनुकूलन या गिनती समस्या और एक पैरामीटर {{math|ε > 0}} का उदाहरण लेता है और, बहुपद समय में, एक समाधान उत्पन्न करता है जिसकी एक कारक {{math|ε}} के भीतर होने की उच्च संभावना होती है। परंपरागत रूप से, "उच्च संभावना" का अर्थ 3/4 से अधिक संभावना का होना होता है, चूकिं अधिकांश संभाव्य जटिलता वर्गों के साथ परिभाषा इस स्पष्ट मूल्य में भिन्नता के लिए मजबूत होती है (न्यूनतम आवश्यकता सामान्यतः 1/2 से अधिक होती है)। पीटीएएस की तरह, पीआरएएस में रनिंग टाइम बहुपद {{mvar|n}} होना चाहिए, लेकिन आवश्यक नहीं कि {{math|ε}} में ही हो; {{math|ε}} में चलने के समय पर अतिरिक्त प्रतिबंधों के साथ, कोई ईपीटीएएस के समान एक '''कुशल बहुपद-समय यादृच्छिक सन्निकटन योजना''' या '''ईपीआरएएस''' को परिभाषित कर सकता है, और एफपीटीएएस के समान एक पूर्ण बहुपद-समय यादृच्छिक सन्निकटन योजना या '''एफपीआरएएस''' को परिभाषित कर सकता है।<ref name="vvv">{{cite book | ||
| last = Vazirani | | last = Vazirani | ||
| first = Vijay V. | | first = Vijay V. | ||
| Line 29: | Line 29: | ||
== एक जटिलता वर्ग के रूप में == | == एक जटिलता वर्ग के रूप में == | ||
पीटीएएस शब्द का उपयोग पीटीएएस वाली अनुकूलन समस्याओं के वर्ग को संदर्भित करने के लिए भी किया जा सकता है। पीटीएएस [[ APX | | पीटीएएस शब्द का उपयोग पीटीएएस वाली अनुकूलन समस्याओं के वर्ग को संदर्भित करने के लिए भी किया जा सकता है। पीटीएएस [[ APX |एपीएक्स]] का एक उपसमुच्चय होता है, और जब तक P = NP न हो, तब तक यह एक सख्त उपसमुच्चय होता है। | ||
पीटीएएस में सदस्यता को पीटीएएस | |||
पीटीएएस में सदस्यता को पीटीएएस कमी(रिडक्शन), एल-कमी, या पी-कमी का उपयोग करके दिखाया जा सकता है, जो सभी पीटीएएस सदस्यता को संरक्षित करते हैं, और इनका उपयोग पीटीएएस-पूर्णता प्रदर्शित करने के लिए भी किया जा सकता है। दूसरी ओर, पीटीएएस में गैर-सदस्यता दिखाना (अर्थात्, पीटीएएस का अस्तित्वहीन होना), यह दिखाकर किया जा सकता है कि समस्या एपीएक्स-कठोरता होती है, जिसके बाद पीटीएएस का अस्तित्व P = NP दिखाता है। इस प्रकार एपीएक्स-कठोरता अधिकांशतः पीटीएएस कमी या एपी-कमी के माध्यम से दिखाई जाती है। <ref name="Jansen"></ref> | |||
== यह भी देखें == | == यह भी देखें == | ||
* पैरामीटरयुक्त सन्निकटन | * पैरामीटरयुक्त सन्निकटन योजना होती है, एक सन्निकटन योजना जो FPT समय में चलती है। | ||
==संदर्भ== | ==संदर्भ== | ||
Revision as of 11:31, 5 July 2023
कंप्यूटर विज्ञान (विशेष रूप से एल्गोरिथम) में, एक बहुपद-समय सन्निकटन योजना (पीटीएएस) अनुकूलन समस्याओं (अधिकांशतः, एनपी-कठोरता अनुकूलन समस्याओं) के लिए एक प्रकार का सन्निकटन एल्गोरिदम होता है।
पीटीएएस एक एल्गोरिदम होता है जो एक अनुकूलन समस्या और एक पैरामीटर ε > 0 का उदाहरण लेता है और एक समाधान उत्पन्न करता है जो एक सर्वोत्तम होने का कारक 1 + ε (या 1 – ε अधिकतमीकरण समस्याओं के लिए) के भीतर उपस्होथित होता है। उदाहरण के लिए, यूक्लिडियन ट्रैवलिंग सेल्समैन की समस्या के लिए, एक पीटीएएस अधिकतम (1 + ε)L लंबाई वाला यात्रा करेगा, जहाँ L सबसे छोटे यात्रा की लंबाई होती है।[1] इस प्रकार प्रत्येक निश्चित ε के लिए समस्या आकार में पीटीएएस का चलने का समय बहुपद का उपस्थित होना आवश्यक होता है, परन्तु विभिन्न ε के लिए भिन्न हो सकता है। इस प्रकार समय में चलने वाला एक एल्गोरिदम O(n1/ε) या और भी O(nexp(1/ε)) को पीटीएएस के रूप में गिना जाता है।
भिन्न रूप
नियतात्मक
पीटीएएस एल्गोरिदम के साथ एक व्यावहारिक समस्या यह होती है कि ε सिकुड़ने पर बहुपद का घातांक नाटकीय रूप से बढ़ सकता है, उदाहरण के लिए यदि रनटाइम O(n(1/ε)!) होता है। इसे संबोधित करने का एक विधि कुशल बहुपद-समय सन्निकटन योजना या ईपीटीएएस को परिभाषित करना पड़ता है, जिसमें ε से स्वतंत्र निरंतर c के लिए चलने का समय O(nc) होना आवश्यक होता है। यह सुनिश्चित करता है कि समस्या के आकार में वृद्धि का रनटाइम पर समान सापेक्ष प्रभाव पड़ता है, भले ही ε का उपयोग किया जा रहा हो; यघपि, बिग ओ अंकन के तहत स्थिरांक अभी भी इच्छानुसार ढंग से ε पर निर्भर हो सकता है। दूसरे शब्दों में, एक ईपीटीएएस फिक्स्ड-पैरामीटर एल्गोरिदम समय में चलता है जहां पैरामीटर ε होता है।
इससे भी अधिक प्रतिबंधात्मक, और व्यवहार में उपयोगी, पूरी तरह से बहुपद-समय सन्निकटन योजना या एफपीटीएएस उपस्थित होती है, जिसके लिए एल्गोरिथ्म को समस्या आकार n और 1/ε दोनों में बहुपद होना आवश्यक होता है।
जब तक कि P = NP समस्या ना हो, तब तक FPTAS ⊊ PTAS ⊊ APX होता है।[2] परिणामस्वरूप, इस धारणा के अनुसार, APX-कठोर समस्याओं में PTAS नहीं होते हैं।
पीटीएएस का एक अन्य नियतात्मक संस्करण अर्ध-बहुपद-समय सन्निकटन योजना या क्यूपीटीएएस होता है। एक क्यूपीटीएएस में प्रत्येक निश्चित ε > 0 के लिए समय जटिलता npolylog(n) होती। इसके अतिरिक्त, इस प्रकार पीटीएएस समस्या के कुछ मानकीकरण के लिए फिक्स्ड-पैरामीटर एल्गोरिदम FPT समय में चल सकता है, जो एक पैरामीटराइज्ड सन्निकटन एल्गोरिदम की ओर ले जाता है।
यादृच्छिक
कुछ समस्याएं जिनमें पीटीएएस नहीं होती है, वे समान गुणों वाले एक यादृच्छिक एल्गोरिदम, एक बहुपद-समय यादृच्छिक सन्निकटन योजना या पीआरएएस को स्वीकार कर सकती हैं। पीआरएएस एक एल्गोरिदम होता है जो एक अनुकूलन या गिनती समस्या और एक पैरामीटर ε > 0 का उदाहरण लेता है और, बहुपद समय में, एक समाधान उत्पन्न करता है जिसकी एक कारक ε के भीतर होने की उच्च संभावना होती है। परंपरागत रूप से, "उच्च संभावना" का अर्थ 3/4 से अधिक संभावना का होना होता है, चूकिं अधिकांश संभाव्य जटिलता वर्गों के साथ परिभाषा इस स्पष्ट मूल्य में भिन्नता के लिए मजबूत होती है (न्यूनतम आवश्यकता सामान्यतः 1/2 से अधिक होती है)। पीटीएएस की तरह, पीआरएएस में रनिंग टाइम बहुपद n होना चाहिए, लेकिन आवश्यक नहीं कि ε में ही हो; ε में चलने के समय पर अतिरिक्त प्रतिबंधों के साथ, कोई ईपीटीएएस के समान एक कुशल बहुपद-समय यादृच्छिक सन्निकटन योजना या ईपीआरएएस को परिभाषित कर सकता है, और एफपीटीएएस के समान एक पूर्ण बहुपद-समय यादृच्छिक सन्निकटन योजना या एफपीआरएएस को परिभाषित कर सकता है।[3]
एक जटिलता वर्ग के रूप में
पीटीएएस शब्द का उपयोग पीटीएएस वाली अनुकूलन समस्याओं के वर्ग को संदर्भित करने के लिए भी किया जा सकता है। पीटीएएस एपीएक्स का एक उपसमुच्चय होता है, और जब तक P = NP न हो, तब तक यह एक सख्त उपसमुच्चय होता है।
पीटीएएस में सदस्यता को पीटीएएस कमी(रिडक्शन), एल-कमी, या पी-कमी का उपयोग करके दिखाया जा सकता है, जो सभी पीटीएएस सदस्यता को संरक्षित करते हैं, और इनका उपयोग पीटीएएस-पूर्णता प्रदर्शित करने के लिए भी किया जा सकता है। दूसरी ओर, पीटीएएस में गैर-सदस्यता दिखाना (अर्थात्, पीटीएएस का अस्तित्वहीन होना), यह दिखाकर किया जा सकता है कि समस्या एपीएक्स-कठोरता होती है, जिसके बाद पीटीएएस का अस्तित्व P = NP दिखाता है। इस प्रकार एपीएक्स-कठोरता अधिकांशतः पीटीएएस कमी या एपी-कमी के माध्यम से दिखाई जाती है। [2]
यह भी देखें
- पैरामीटरयुक्त सन्निकटन योजना होती है, एक सन्निकटन योजना जो FPT समय में चलती है।
संदर्भ
- ↑ 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.
