पैरामिट्रीकृत सम्मिश्रता

कंप्यूटर विज्ञान में, पैरामीटरयुक्त जटिलता कम्प्यूटेशनल जटिलता सिद्धांत की एक शाखा है जो इनपुट या आउटपुट के 'एकाधिक' पैरामीटर के संबंध में उनकी अंतर्निहित कठिनाई के अनुसार कम्प्यूटेशनल समस्याओं को वर्गीकृत करने पर केंद्रित है। किसी समस्या की जटिलता को तब उन पैरामीटरों के फलन (गणित) के रूप में मापा जाता है। यह शास्त्रीय सेटिंग की तुलना में एनपी कठिन समस्याओं के बेहतर पैमाने पर वर्गीकरण की अनुमति देता है, जहां किसी समस्या की जटिलता को केवल इनपुट में बिट्स की संख्या के कार्य के रूप में मापा जाता है। पैरामिट्रीकृत जटिलता पर पहला व्यवस्थित कार्य किसके द्वारा किया गया था? Downey & Fellows (1999).

इस धारणा के तहत कि पी बनाम एनपी समस्या | पी ≠ एनपी, ऐसी कई प्राकृतिक समस्याएं मौजूद हैं जिनके लिए सुपरपोलिनोमियल कार्यकारी समय की आवश्यकता होती है जब जटिलता को केवल इनपुट आकार के संदर्भ में मापा जाता है लेकिन यह इनपुट आकार और घातांक में बहुपद वाले समय में गणना योग्य है या एक पैरामीटर में बदतर k. इसलिए, अगर k एक छोटे से मान पर तय होता है और फ़ंक्शन का विकास खत्म हो जाता है k अपेक्षाकृत छोटा है तो इस तरह की समस्याओं को उनके पारंपरिक वर्गीकरण के बावजूद अभी भी सुगम माना जा सकता है।

एनपी-पूर्ण, या अन्यथा एनपी-हार्ड, समस्याओं के लिए कुशल, सटीक, और नियतात्मक हल करने वाले एल्गोरिदम के अस्तित्व को असंभाव्य माना जाता है, यदि इनपुट पैरामीटर तय नहीं हैं; इन समस्याओं के लिए सभी ज्ञात हल करने वाले एल्गोरिदम को समय की आवश्यकता होती है जो कि इनपुट के कुल आकार में घातीय समय (इसलिए विशेष रूप से सुपरपोलिनोमियल) है। हालाँकि, कुछ समस्याओं को एल्गोरिदम द्वारा हल किया जा सकता है जो केवल एक निश्चित पैरामीटर के आकार में घातीय होते हैं जबकि इनपुट के आकार में बहुपद होते हैं। इस तरह के एक एल्गोरिथ्म को फिक्स्ड-पैरामीटर ट्रैक्टेबल (एफपीटी-) एल्गोरिदम कहा जाता है, क्योंकि निश्चित पैरामीटर के छोटे मूल्यों के लिए समस्या को कुशलतापूर्वक हल किया जा सकता है।

समस्याएं जिनमें कुछ पैरामीटर k निश्चित है जिसे पैरामिट्रीकृत समस्याएं कहा जाता है। एक पैरामिट्रीकृत समस्या जो इस तरह के एक fpt-एल्गोरिदम की अनुमति देती है, एक निश्चित-पैरामीटर ट्रैक्टेबल समस्या कहलाती है और वर्ग से संबंधित होती है FPT, और पैरामिट्रीकृत जटिलता के सिद्धांत का प्रारंभिक नाम फिक्स्ड-पैरामीटर ट्रैक्टेबिलिटी था।

कई समस्याओं का निम्न रूप होता है: एक वस्तु दी गई x और एक गैर-नकारात्मक पूर्णांक k, करता है x के पास कुछ संपत्ति है जो निर्भर करती है k? उदाहरण के लिए, वर्टेक्स कवर समस्या के लिए, पैरामीटर कवर में वर्टिकल की संख्या हो सकती है। कई अनुप्रयोगों में, उदाहरण के लिए जब मॉडलिंग त्रुटि सुधार होता है, तो कुल इनपुट आकार की तुलना में पैरामीटर को छोटा माना जा सकता है। फिर एक एल्गोरिदम खोजना चुनौतीपूर्ण है जो केवल घातीय है k, और इनपुट आकार में नहीं।

इस तरह, पैरामिट्रीकृत जटिलता को द्वि-आयामी जटिलता सिद्धांत के रूप में देखा जा सकता है। इस अवधारणा को निम्नानुसार औपचारिक रूप दिया गया है:

एक पैरामिट्रीकृत समस्या एक भाषा है $L\subseteq \Sigma ^{*}\times \mathbb {N}$, कहाँ $\Sigma$ परिमित वर्णमाला है। दूसरे घटक को समस्या का पैरामीटर कहा जाता है।

एक पैरामिट्रीकृत समस्या L निश्चित-पैरामीटर ट्रैक्टेबल है यदि प्रश्न$(x,k)\in L$? समय में तय किया जा सकता है $f(k)\cdot |x|^{O(1)}$, कहाँ f एक मनमाना कार्य है जो केवल पर निर्भर करता है k. इसी जटिलता वर्ग को FPT कहा जाता है।

उदाहरण के लिए, एक एल्गोरिदम है जो वर्टेक्स कवर समस्या को हल करता है $O(kn+1.274^{k})$ समय, कहाँ n शीर्षों की संख्या है और k वर्टेक्स कवर का आकार है। इसका मतलब यह है कि वर्टेक्स कवर फिक्स्ड-पैरामीटर ट्रैक्टेबल है जो समाधान के आकार के पैरामीटर के रूप में है।

जटिलता वर्ग

एफपीटी

FPT में निश्चित पैरामीटर ट्रैक्टेबल समस्याएं होती हैं, जो कि समय पर हल की जा सकती हैं $f(k)\cdot {|x|}^{O(1)}$ कुछ गणना योग्य समारोह के लिए f. आमतौर पर, इस फ़ंक्शन को एकल घातांक के रूप में माना जाता है, जैसे $2^{O(k)}$, लेकिन परिभाषा ऐसे कार्यों को स्वीकार करती है जो और भी तेज़ी से बढ़ते हैं। यह इस वर्ग के प्रारंभिक इतिहास के एक बड़े हिस्से के लिए आवश्यक है। परिभाषा का महत्वपूर्ण हिस्सा फॉर्म के कार्यों को बाहर करना है $f(n,k)$, जैसे कि $k^{n}$.

क्लास एफपीएल (फिक्स्ड पैरामीटर लीनियर) समय में हल करने योग्य समस्याओं का वर्ग है $f(k)\cdot |x|$ कुछ गणना योग्य समारोह के लिए f. FPL इस प्रकार FPT का एक उपवर्ग है। एक उदाहरण बूलियन संतुष्टि समस्या है, जो कि चरों की संख्या द्वारा परिचालित है। आकार का एक दिया गया सूत्र m साथ k समय में क्रूर बल द्वारा चरों की जाँच की जा सकती है $O(2^{k}m)$. आकार का एक शीर्ष आवरण k क्रम के एक ग्राफ में n समय पर मिल सकता है $O(2^{k}n)$, इसलिए वर्टेक्स कवर की समस्या भी FPL में है।

एक समस्या का एक उदाहरण जो माना जाता है कि एफपीटी में नहीं है, रंगों की संख्या के आधार पर ग्राफ रंग का पैरामीटर है। यह ज्ञात है कि 3-रंग एनपी-हार्ड है, और ग्राफ के लिए एक एल्गोरिदम है k-समय पर रंग भरना $f(k)n^{O(1)}$ के लिए $k=3$ इनपुट के आकार में बहुपद समय में चलेगा। इस प्रकार, यदि रंगों की संख्या द्वारा पैरामीटर किए गए ग्राफ़ रंग एफपीटी में थे, तो पी बनाम एनपी समस्या | पी = एनपी।

FPT की कई वैकल्पिक परिभाषाएँ हैं। उदाहरण के लिए, रनिंग-टाइम आवश्यकता को इसके द्वारा प्रतिस्थापित किया जा सकता है $f(k)+|x|^{O(1)}$. साथ ही, एक पैरामिट्रीकृत समस्या FPT में है यदि इसमें एक तथाकथित कर्नेल है। गुठली बनाना एक प्रीप्रोसेसिंग तकनीक है जो मूल उदाहरण को उसके हार्ड कर्नेल में कम कर देता है, संभवतः बहुत छोटा उदाहरण जो मूल उदाहरण के बराबर है लेकिन एक आकार है जो पैरामीटर में एक फ़ंक्शन से घिरा हुआ है।

FPT को 'fpt-reductions' नामक रिडक्शन (जटिलता) की एक पैरामीटरयुक्त धारणा के तहत बंद कर दिया गया है। इस तरह की कटौती एक उदाहरण को बदल देती है $(x,k)$ समतुल्य उदाहरण में कुछ समस्या का $(x',k')$ किसी अन्य समस्या का (के साथ $k'\leq g(k)$) और समय में गणना की जा सकती है $f(k)\cdot p(|x|)$ कहाँ $p$ एक बहुपद है।

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

डब्ल्यू पदानुक्रम

'डब्ल्यू पदानुक्रम' कम्प्यूटेशनल जटिलता वर्गों का एक संग्रह है। वर्ग डब्ल्यू [i] में एक पैरामिट्रीकृत समस्या है, यदि हर उदाहरण $(x,k)$ (एफटीटी-समय में) एक संयोजी परिपथ में परिवर्तित किया जा सकता है जिसमें अधिक से अधिक i पर बाना (सर्किट) हो, जैसे कि $(x,k)\in L$ अगर और केवल अगर इनपुट के लिए एक संतोषजनक असाइनमेंट है जो 1 को बिल्कुल k इनपुट प्रदान करता है। वेट एक इनपुट से आउटपुट तक किसी भी पथ पर फैन-इन दो से अधिक के साथ तार्किक इकाइयों की सबसे बड़ी संख्या है। रास्तों पर तार्किक इकाइयों की कुल संख्या (गहराई के रूप में जाना जाता है) को एक स्थिरांक द्वारा सीमित किया जाना चाहिए जो समस्या के सभी उदाहरणों के लिए होल्ड करता है।

ध्यान दें कि ${\mathsf {FPT}}=W[0]$ और $W[i]\subseteq W[j]$ सभी के लिए $i\leq j$. एफपीटी-कमी के तहत डब्ल्यू पदानुक्रम में कक्षाएं भी बंद हैं।

कई प्राकृतिक कम्प्यूटेशनल समस्याएं निचले स्तरों, डब्ल्यू [1] और डब्ल्यू [2] पर कब्जा कर लेती हैं।

डब्ल्यू [1]

W[1]-पूर्ण समस्याओं के उदाहरणों में शामिल हैं

• यह तय करना कि दिए गए ग्राफ़ में k आकार का एक क्लिक (ग्राफ़ सिद्धांत) है या नहीं
• यह तय करना कि दिए गए ग्राफ़ में आकार k का एक स्वतंत्र सेट (ग्राफ़ सिद्धांत) है या नहीं
• यह तय करना कि क्या दी गई गैर-नियतात्मक एकल-टेप ट्यूरिंग मशीन k चरणों (लघु ट्यूरिंग मशीन स्वीकृति समस्या) के भीतर स्वीकार करती है। यह f(k) टेप और यहां तक ​​कि f(k)-डायमेंशनल टेप के f(k) के साथ गैर-नियतात्मक ट्यूरिंग मशीनों पर भी लागू होता है, लेकिन इस विस्तार के साथ भी, f(k) टेप वर्णमाला के आकार का प्रतिबंध निश्चित-पैरामीटर ट्रैक्टेबल है। महत्वपूर्ण रूप से, प्रत्येक चरण पर ट्यूरिंग मशीन की ब्रांचिंग को n, इनपुट के आकार पर निर्भर करने की अनुमति है। इस तरह, ट्यूरिंग मशीन एन का पता लगा सकती है^O(k) संगणना पथ।

डब्ल्यू [2]

W[2]-पूर्ण समस्याओं के उदाहरणों में शामिल हैं

• यह तय करना कि दिए गए ग्राफ़ में आकार k का एक प्रभावशाली सेट है या नहीं
• यह तय करना कि क्या दी गई गैर-नियतात्मक ट्यूरिंग मशीन समकक्ष # मल्टी-टेप ट्यूरिंग मशीन | मल्टी-टेप ट्यूरिंग मशीन k चरणों के भीतर स्वीकार करती है (लघु मल्टी-टेप ट्यूरिंग मशीन स्वीकृति समस्या)। महत्वपूर्ण रूप से, ब्रांचिंग को n (जैसे W[1] प्रकार) पर निर्भर रहने की अनुमति है, जैसा कि टेपों की संख्या है। एक वैकल्पिक W[2]-पूर्ण सूत्रीकरण केवल एकल-टेप ट्यूरिंग मशीनों की अनुमति देता है, लेकिन वर्णमाला का आकार n पर निर्भर हो सकता है।

डब्ल्यू [टी]

$W[t]$ भारित बाने के परिवार का उपयोग करके परिभाषित किया जा सकता है-t-गहराई-d सैट समस्याओं के लिए $d\geq t$: $W[t,d]$ पैरामिट्रीकृत समस्याओं का वर्ग है जो इस समस्या को fpt-reduce करता है, और $W[t]=\bigcup _{d\geq t}W[t,d]$.

यहाँ, भारित बाना-t-गहराई-d SAT निम्न समस्या है:

• इनपुट: अधिक से अधिक गहराई का एक बूलियन सूत्र d और अधिक से अधिक बाना t, और एक संख्या k. गहराई रूट से पत्ते तक किसी भी पथ पर फाटकों की अधिकतम संख्या है, और बाना जड़ से पत्ती तक किसी भी पथ पर कम से कम तीन फाटकों की अधिकतम संख्या है।
• प्रश्न: क्या सूत्र में सटीक रूप से हैमिंग भार का संतोषजनक कार्य है k?

यह दिखाया जा सकता है कि के लिए $t\geq 2$ समस्या भारित t-Normalize SAT के लिए पूरा हो गया है $W[t]$ एफपीटी-कटौती के तहत। यहाँ, भारित t-सामान्य करें SAT निम्न समस्या है:

• इनपुट: अधिक से अधिक गहराई का एक बूलियन सूत्र t शीर्ष पर एक AND-गेट और एक संख्या के साथ k.
• प्रश्न: क्या सूत्र में सटीक रूप से हैमिंग भार का संतोषजनक कार्य है k?

डब्ल्यू [पी]

डब्ल्यू [पी] समस्याओं का वर्ग है जिसे एक गैर-निर्धारिती द्वारा तय किया जा सकता है $h(k)\cdot {|x|}^{O(1)}$-अपना समय सेट करें$O(f(k)\cdot \log n)$ पर गणना में nondeterministic विकल्प $(x,k)$ (के-प्रतिबंधित ट्यूरिंग मशीन)। Flum & Grohe (2006)

यह ज्ञात है कि एफपीटी डब्ल्यू [पी] में निहित है, और समावेशन को सख्त माना जाता है। हालाँकि, इस मुद्दे को हल करने से P बनाम NP समस्या का समाधान होगा।

अपैरामीटरीकृत कम्प्यूटेशनल जटिलता के अन्य कनेक्शन हैं कि एफपीटी डब्ल्यू [पी] के बराबर है अगर और केवल अगर सर्किट संतुष्टि समय पर तय की जा सकती है $\exp(o(n))m^{O(1)}$, या यदि और केवल अगर कोई संगणनीय, गैर-घटता हुआ, असीमित फ़ंक्शन f है, जैसे कि सभी भाषाओं को एक गैर-नियतात्मक बहुपद-समय ट्यूरिंग मशीन द्वारा मान्यता प्राप्त है $f(n)\log n$ गैर नियतात्मक विकल्प P में हैं।

डब्ल्यू [पी] को शिथिल रूप से समस्याओं के वर्ग के रूप में सोचा जा सकता है जहां हमारे पास एक सेट है S का n आइटम, और हम एक सबसेट खोजना चाहते हैं $T\subset S$ आकार का k जैसे कि एक निश्चित संपत्ति रखती है। हम एक सूची के रूप में एक विकल्प को एन्कोड कर सकते हैं k पूर्णांक, बाइनरी में संग्रहीत। चूँकि इनमें से उच्चतम कोई भी संख्या हो सकती है n, $\lceil \log _{2}n\rceil$ बिट्स प्रत्येक संख्या के लिए आवश्यक हैं। इसलिए $k\cdot \lceil \log _{2}n\rceil$ किसी विकल्प को एन्कोड करने के लिए कुल बिट्स की आवश्यकता होती है। इसलिए हम एक उपसमुच्चय का चयन कर सकते हैं $T\subset S$ साथ $O(k\cdot \log n)$ गैर-नियतात्मक विकल्प।

एक्सपी

XP पैरामिट्रीकृत समस्याओं का वर्ग है जिसे समय पर हल किया जा सकता है $n^{f(k)}$ कुछ गणना योग्य समारोह के लिए f. इन समस्याओं को टुकड़ा बहुपद कहा जाता है, इस अर्थ में कि निश्चित k के प्रत्येक स्लाइस में एक बहुपद एल्गोरिथम होता है, हालांकि संभवतः प्रत्येक k के लिए एक अलग घातांक के साथ। इसकी तुलना FPT से करें, जो केवल k के प्रत्येक मान के लिए एक अलग निरंतर प्रीफैक्टर की अनुमति देता है। XP में FPT होता है, और यह ज्ञात है कि यह नियंत्रण विकर्णकरण द्वारा सख्त है।

पैरा-एनपी

पैरा-एनपी पैरामीटरयुक्त समस्याओं का वर्ग है जिसे समय पर एक गैर-नियतात्मक एल्गोरिदम द्वारा हल किया जा सकता है $f(k)\cdot |x|^{O(1)}$ कुछ गणना योग्य समारोह के लिए f. ह ज्ञात है कि ${\textsf {FPT}}={\textsf {para-NP}}$ अगर और केवल अगर ${\textsf {P}}={\textsf {NP}}$.

एक समस्या पैरा-एनपी-हार्ड है यदि यह है ${\textsf {NP}}$-पैरामीटर के निरंतर मान के लिए पहले से ही कठिन है। यानी फिक्स का एक टुकड़ा है k वह है ${\textsf {NP}}$-मुश्किल। एक पैरामिट्रीकृत समस्या जो है ${\textsf {para-NP}}$-हार्ड वर्ग से संबंधित नहीं हो सकता ${\textsf {XP}}$, जब तक ${\textsf {P}}={\textsf {NP}}$. ए. का एक उत्कृष्ट उदाहरण है ${\textsf {para-NP}}$-हार्ड पैरामिट्रीकृत समस्या ग्राफ कलरिंग है, जो संख्या द्वारा परिचालित है k रंग, जो पहले से ही है ${\textsf {NP}}$-के लिए कठिन $k=3$ (ग्राफ़ कलरिंग # कम्प्यूटेशनल जटिलता देखें)।

एक पदानुक्रम

A पदानुक्रम W पदानुक्रम के समान कम्प्यूटेशनल जटिलता वर्गों का एक संग्रह है। हालाँकि, जबकि W पदानुक्रम NP में निहित एक पदानुक्रम है, A पदानुक्रम शास्त्रीय जटिलता से बहुपद-समय पदानुक्रम की अधिक बारीकी से नकल करता है। यह ज्ञात है कि A[1] = W[1] धारण करता है।

यह भी देखें

• पैरामीटरयुक्त सन्निकटन एल्गोरिथ्म, अनुकूलन समस्या के लिए FPT समय में चलने वाला एक एल्गोरिथ्म समाधान सन्निकटन एल्गोरिथम हो सकता है।

संदर्भ

• Chen, Jianer; Kanj, Iyad A.; Xia, Ge (2006). Improved Parameterized Upper Bounds for Vertex Cover. pp. 238–249. CiteSeerX 10.1.1.432.831. doi:10.1007/11821069_21. ISBN 978-3-540-37791-7. {{cite book}}: |journal= ignored (help)
• Cygan, Marek; Fomin, Fedor V.; Kowalik, Lukasz; Lokshtanov, Daniel; Marx, Daniel; Pilipczuk, Marcin; Pilipczuk, Michal; Saurabh, Saket (2015). Parameterized Algorithms. Springer. p. 555. ISBN 978-3-319-21274-6.
• Downey, Rod G.; Fellows, Michael R. (1999). Parameterized Complexity. Springer. ISBN 978-0-387-94883-6.
• Flum, Jörg; Grohe, Martin (2006). Parameterized Complexity Theory. Springer. ISBN 978-3-540-29952-3.
• Fomin, Fedor V.; Lokshtanov, Daniel; Saurabh, Saket; Zehavi, Meirav (2019). Kernelization: Theory of Parameterized Preprocessing. Cambridge University Press. p. 528. doi:10.1017/9781107415157. ISBN 978-1107057760.
• Niedermeier, Rolf (2006). Invitation to Fixed-Parameter Algorithms. Oxford University Press. ISBN 978-0-19-856607-6. Archived from the original on 2008-09-24.
• Grohe, Martin (1999). "Descriptive and Parameterized Complexity". Computer Science Logic. Lecture Notes in Computer Science. Vol. 1683. Springer Berlin Heidelberg. pp. 14–31. CiteSeerX 10.1.1.25.9250. doi:10.1007/3-540-48168-0_3. ISBN 978-3-540-66536-6.
• The Computer Journal. Volume 51, Numbers 1 and 3 (2008). The Computer Journal. Special Double Issue on Parameterized Complexity with 15 survey articles, book review, and a Foreword by Guest Editors R. Downey, M. Fellows and M. Langston.

बाहरी संबंध

• Wiki on parameterized complexity
• Compendium of Parameterized Problems