पैरामिट्रीकृत सम्मिश्रता: Difference between revisions

Latest revision as of 16:31, 12 October 2023

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

इस धारणा के अनुसार कि P के प्रति NP समस्या P, NP, ऐसी कई प्राकृतिक समस्याएं उपस्थित हैं जिनके लिए सुपरपोलिनोमियल कार्यकारी समय की आवश्यकता होती है जब सम्मिश्रता को केवल इनपुट आकार के संदर्भ में मापा जाता है किन्तु यह इनपुट आकार एवं घातांक में बहुपद वाले समय में गणना योग्य है, पैरामीटर घातीय के है $k$ . इसलिए, यदि $k$ छोटे से मान पर निर्धारित होता है एवं प्रोग्राम का विकास समाप्त हो जाता हैI अपेक्षाकृत $k$ छोटा है तो इस प्रकार की समस्याओं को उनके पारंपरिक वर्गीकरण के पश्चात अभी भी सुगम माना जा सकता है।

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

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

कई समस्याओं का निम्न रूप होता है, दी गई वस्तु $x$ एवं गैर-नकारात्मक पूर्णांक $k$ , है $x$ के निकट कुछ संपत्ति है जो $k$ पर निर्भर करती हैI उदाहरण के लिए, वर्टेक्स कवर समस्या के लिए, पैरामीटर कवर में वर्टिकल की संख्या हो सकती है। कई अनुप्रयोगों में, उदाहरण के लिए जब मॉडलिंग त्रुटि सुधार होता है, तो कुल इनपुट आकार की तुलना में पैरामीटर को अल्प माना जा सकता है। तथापि एल्गोरिदम का प्रतिशोधन प्रचारणा है जो केवल घातीय है एवं $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})$ समय,^[1] जहां $n$ शीर्षों की संख्या है एवं $k$ वर्टेक्स कवर का आकार है। इसका अर्थ यह है कि वर्टेक्स कवर फिक्स्ड-पैरामीटर ट्रैक्टेबल है जो समाधान के आकार के पैरामीटर के रूप में है।

सम्मिश्रता वर्ग

एफपीटी

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

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

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

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

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

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

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

'डब्ल्यू पदानुक्रम' कम्प्यूटेशनल सम्मिश्रता वर्गों का संग्रह है। वर्ग डब्ल्यू [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]-पूर्ण समस्याओं के उदाहरणों में सम्मिलित हैंI

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

डब्ल्यू [2]

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

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

डब्ल्यू [T]

$W[t]$ को वेटेड वेट-टी-डेप्थ-डी एसएटी समस्याओं के परिवार का उपयोग करके परिभाषित किया जा सकता है $W[t,d]$ पैरामिट्रीकृत समस्याओं का वर्ग है जो इस समस्या को एफपीटी अर्घ्य करता है, एवं $W[t]=\bigcup _{d\geq t}W[t,d]$ होता हैI

यहाँ, वेटेड वेट-d-डेप्थ-d एसएटी निम्नलिखित समस्या हैI

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

यह दर्शाया जा सकता है कि $t\geq 2$ के लिए भारित समस्या $t$ -सामान्यीकृत एसएटी (SAT) के लिए पूर्ण है $W[t]$ एफपीटी क्षरण के अनुसार ^[3]यहाँ, भारित $t$ -सामान्यीकृत एसएटी निम्नलिखित समस्या हैI

इनपुट शीर्ष पर एंड (AND) गेट एवं के साथ $t$ क्षरण का लियन सूत्र $k$ हैI
प्रश्न: क्या सूत्र में स्थिर रूप से हैमिंग बल का संतोषजनक कार्य $k$ है?

डब्ल्यू [P]

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

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

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

डब्ल्यू [P] को शिथिल रूप से समस्याओं के वर्ग के रूप में विचार किया जा सकता है जहां हमारे पास $n$ वस्तुओं का समूह $S$ का आइटम, एवं हम उपसमुच्चय का शोध चाहते हैं $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)$ गैर-नियतात्मक विकल्प होते है।

एक्सपी

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

पैरा-एनपी

पैरा-एनपी पैरामीटरयुक्त समस्याओं का वर्ग है जिसे समय पर गैर-नियतात्मक एल्गोरिदम द्वारा समाधान किया जा सकता है $f(k)\cdot |x|^{O(1)}$ कुछ गणना योग्य समारोह $f$ के लिए ज्ञात है कि ${\textsf {FPT}}={\textsf {para-NP}}$ यदि एवं यदि ${\textsf {P}}={\textsf {NP}}$ होते है।^[4] समस्या पैरा-एनपी-हार्ड है यदि ${\textsf {NP}}$ - पैरामीटर के निरंतर मान के लिए पूर्व से ही कठिन है। अर्थात फिक्स $k$ का अंश है अर्थात ${\textsf {NP}}$ - हार्ड पैरामिट्रीकृत समस्या जो है ${\textsf {para-NP}}$ हार्ड वर्ग से संबंधित नहीं हो सकता ${\textsf {XP}}$ , जब तक ${\textsf {P}}={\textsf {NP}}$ . a. का उत्कृष्ट उदाहरण है ${\textsf {para-NP}}$ - हार्ड पैरामिट्रीकृत समस्या ग्राफ कलरिंग है, जिसे रंगों की संख्या $k$ द्वारा परिचालित किया गया है, जो पूर्व से ही है ${\textsf {NP}}$ के लिए कठिन $k=3$ ) है।

पदानुक्रम

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

यह भी देखें

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

संदर्भ

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.

बाहरी संबंध

[1] Chen, Kanj & Xia 2006

[2] Grohe (1999)

[3] Buss, Jonathan F; Islam, Tarique (2006). "बाने के पदानुक्रम को सरल बनाना". Theoretical Computer Science. 351 (3): 303–313. doi:10.1016/j.tcs.2005.10.002.

[FOOTNOTEFlumGrohe200639-4] Flum & Grohe (2006), p. 39.

[1]

[2]

[3]

[4]

@@ Line 1: / Line 1: @@
 {{Short description|Branch of computational complexity theory}}
-[[कंप्यूटर विज्ञान]] में, पैरामीटरयुक्त जटिलता [[कम्प्यूटेशनल जटिलता सिद्धांत]] की शाखा है जो इनपुट या आउटपुट के 'एकाधिक' पैरामीटर के संबंध में उनकी अंतर्निहित कठिनाई के अनुसार कम्प्यूटेशनल समस्याओं को वर्गीकृत करने पर केंद्रित है। किसी समस्या की जटिलता को तब उन पैरामीटरों के फलन (गणित) के रूप में मापा जाता है। यह शास्त्रीय सेटिंग की तुलना में [[ एनपी कठिन ]]समस्याओं के उत्तम स्तर पर वर्गीकरण की अनुमति देता है, जहां किसी समस्या की जटिलता को केवल इनपुट में बिट्स की संख्या के कार्य के रूप में मापा जाता है। पैरामिट्रीकृत जटिलता पर प्रथम व्यवस्थित कार्य किसके द्वारा किया गया था? .
+कंप्यूटर विज्ञान में, '''पैरामीटरयुक्त सम्मिश्रता''' [[कम्प्यूटेशनल जटिलता सिद्धांत|कम्प्यूटेशनल सम्मिश्रता सिद्धांत]] की शाखा है जो इनपुट या आउटपुट के 'एकाधिक' पैरामीटर के संबंध में उनकी अंतर्निहित कठिनाई के अनुसार कम्प्यूटेशनल समस्याओं को वर्गीकृत करने पर केंद्रित है। किसी समस्या की सम्मिश्रता को तब उन पैरामीटरों के फलन (गणित) के रूप में मापा जाता है। यह शास्त्रीय सेटिंग की तुलना में [[ एनपी कठिन ]]समस्याओं के उत्तम स्तर पर वर्गीकरण की अनुमति देता है, जहां किसी समस्या की सम्मिश्रता को केवल इनपुट में बिट्स की संख्या के कार्य के रूप में मापा जाता है। पैरामिट्रीकृत सम्मिश्रता पर प्रथम व्यवस्थित कार्य किसके द्वारा किया गया था? .
-इस धारणा के अनुसार कि पी बनाम एनपी समस्या | पी ≠ एनपी, ऐसी कई प्राकृतिक समस्याएं मौजूद हैं जिनके लिए सुपरपोलिनोमियल [[ कार्यकारी समय ]] की आवश्यकता होती है जब जटिलता को केवल इनपुट आकार के संदर्भ में मापा जाता है लेकिन यह इनपुट आकार और घातांक में बहुपद वाले समय में गणना योग्य है या एक पैरामीटर में बदतर {{mvar|k}}. इसलिए, अगर {{mvar|k}} एक छोटे से मान पर तय होता है और फ़ंक्शन का विकास खत्म हो जाता है {{mvar|k}} अपेक्षाकृत छोटा है तो इस तरह की समस्याओं को उनके पारंपरिक वर्गीकरण के बावजूद अभी भी सुगम माना जा सकता है।
+इस धारणा के अनुसार कि P के प्रति NP समस्या P, NP, ऐसी कई प्राकृतिक समस्याएं उपस्थित हैं जिनके लिए सुपरपोलिनोमियल [[ कार्यकारी समय |कार्यकारी समय]] की आवश्यकता होती है जब सम्मिश्रता को केवल इनपुट आकार के संदर्भ में मापा जाता है किन्तु यह इनपुट आकार एवं घातांक में बहुपद वाले समय में गणना योग्य है, पैरामीटर घातीय के है {{mvar|k}}. इसलिए, यदि {{mvar|k}} छोटे से मान पर निर्धारित होता है एवं प्रोग्राम का विकास समाप्त हो जाता हैI अपेक्षाकृत {{mvar|k}} छोटा है तो इस प्रकार की समस्याओं को उनके पारंपरिक वर्गीकरण के पश्चात अभी भी सुगम माना जा सकता है।
-एनपी-पूर्ण, या अन्यथा एनपी-हार्ड, समस्याओं के लिए कुशल, सटीक, और नियतात्मक हल करने वाले एल्गोरिदम के अस्तित्व को असंभाव्य माना जाता है, यदि इनपुट पैरामीटर तय नहीं हैं; इन समस्याओं के लिए सभी ज्ञात हल करने वाले एल्गोरिदम को समय की आवश्यकता होती है जो कि इनपुट के कुल आकार में [[घातीय समय]] (इसलिए विशेष रूप से सुपरपोलिनोमियल) है। हालाँकि, कुछ समस्याओं को एल्गोरिदम द्वारा हल किया जा सकता है जो केवल एक निश्चित पैरामीटर के आकार में घातीय होते हैं जबकि इनपुट के आकार में बहुपद होते हैं। इस तरह के एक एल्गोरिथ्म को [[फिक्स्ड-पैरामीटर ट्रैक्टेबल]] (एफपीटी-) एल्गोरिदम कहा जाता है, क्योंकि निश्चित पैरामीटर के छोटे मूल्यों के लिए समस्या को कुशलतापूर्वक हल किया जा सकता है।
+एनपी-पूर्ण, अन्यथा एनपी-हार्ड, समस्याओं के लिए कुशल, स्थिर एवं नियतात्मक समाधान करने वाले एल्गोरिदम के अस्तित्व को असंभाव्य माना जाता है, यदि इनपुट पैरामीटर निर्धारित नहीं हैं, इन समस्याओं के लिए सभी ज्ञात समाधान करने वाले एल्गोरिदम को समय की आवश्यकता होती है जो कि इनपुट के कुल आकार में [[घातीय समय]] (इसलिए विशेष रूप से सुपरपोलिनोमियल) है। चूँकि कुछ समस्याओं का एल्गोरिदम द्वारा समाधान किया जा सकता है जो केवल निश्चित पैरामीटर के आकार में घातीय होते हैं जबकि इनपुट के आकार में बहुपद होते हैं। इस प्रकार के एल्गोरिथ्म को [[फिक्स्ड-पैरामीटर ट्रैक्टेबल]] (FPT) एल्गोरिदम कहा जाता है, क्योंकि निश्चित पैरामीटर के अल्प मूल्यों के लिए समस्या का कुशलतापूर्वक समाधान किया जा सकता है।
-समस्याएं जिनमें कुछ पैरामीटर {{mvar|k}} निश्चित है जिसे पैरामिट्रीकृत समस्याएं कहा जाता है। एक पैरामिट्रीकृत समस्या जो इस तरह के एक fpt-एल्गोरिदम की अनुमति देती है, एक निश्चित-पैरामीटर ट्रैक्टेबल समस्या कहलाती है और वर्ग से संबंधित होती है {{sans-serif|FPT}}, और पैरामिट्रीकृत जटिलता के सिद्धांत का प्रारंभिक नाम फिक्स्ड-पैरामीटर ट्रैक्टेबिलिटी था।
+समस्याएं जिनमें {{mvar|k}} के कुछ पैरामीटर निश्चित है जिसे पैरामिट्रीकृत समस्याएं कहा जाता है।पैरामिट्रीकृत समस्या जो इस प्रकार के एफपीटी (FPT) एल्गोरिदम की अनुमति देती है, निश्चित-पैरामीटर ट्रैक्टेबल समस्या कहलाती है एवं वर्ग से संबंधित होती है {{sans-serif|एफपीटी}}, एवं  पैरामिट्रीकृत सम्मिश्रता के सिद्धांत का प्रारंभिक नाम फिक्स्ड-पैरामीटर ट्रैक्टेबिलिटी था।
-कई समस्याओं का निम्न रूप होता है: एक वस्तु दी गई {{mvar|x}} और एक गैर-नकारात्मक पूर्णांक {{mvar|k}}, करता है {{mvar|x}} के पास कुछ संपत्ति है जो निर्भर करती है {{mvar|k}}? उदाहरण के लिए, [[वर्टेक्स कवर समस्या]] के लिए, पैरामीटर कवर में वर्टिकल की संख्या हो सकती है। कई अनुप्रयोगों में, उदाहरण के लिए जब मॉडलिंग त्रुटि सुधार होता है, तो कुल इनपुट आकार की तुलना में पैरामीटर को छोटा माना जा सकता है। फिर एक एल्गोरिदम खोजना चुनौतीपूर्ण है जो केवल घातीय है {{mvar|k}}, और इनपुट आकार में नहीं।
+कई समस्याओं का निम्न रूप होता है, दी गई वस्तु {{mvar|x}} एवं गैर-नकारात्मक पूर्णांक {{mvar|k}}, है {{mvar|x}} के निकट कुछ संपत्ति है जो {{mvar|k}} पर निर्भर करती हैI उदाहरण के लिए, [[वर्टेक्स कवर समस्या]] के लिए, पैरामीटर कवर में वर्टिकल की संख्या हो सकती है। कई अनुप्रयोगों में, उदाहरण के लिए जब मॉडलिंग त्रुटि सुधार होता है, तो कुल इनपुट आकार की तुलना में पैरामीटर को अल्प माना जा सकता है। तथापि एल्गोरिदम का प्रतिशोधन प्रचारणा है जो केवल घातीय है एवं {{mvar|k}}, इनपुट आकार में नहीं होते है।
-इस तरह, पैरामिट्रीकृत जटिलता को द्वि-आयामी जटिलता सिद्धांत के रूप में देखा जा सकता है। इस अवधारणा को निम्नानुसार औपचारिक रूप दिया गया है:
+इस प्रकार, पैरामिट्रीकृत सम्मिश्रता को द्वि-आयामी सम्मिश्रता सिद्धांत के रूप में दर्शाया जा सकता है। इस अवधारणा को निम्नानुसार औपचारिक रूप दिया गया है:
-: एक पैरामिट्रीकृत समस्या एक भाषा है <math>L \subseteq \Sigma^* \times \N</math>, कहाँ <math>\Sigma</math> परिमित वर्णमाला है। दूसरे घटक को समस्या का पैरामीटर कहा जाता है।
+: पैरामिट्रीकृत समस्या भाषा है <math>L \subseteq \Sigma^* \times \N</math>, जहां <math>\Sigma</math> परिमित वर्णमाला है। दूसरे घटक को समस्या का पैरामीटर कहा जाता है। पैरामिट्रीकृत समस्या {{mvar|L}} निश्चित-पैरामीटर ट्रैक्टेबल है यदि प्रश्न <math>(x, k) \in L</math>? समय में निर्धारित  किया जा सकता है <math>f(k) \cdot |x|^{O(1)}</math>, जहां {{mvar|f}}  इच्छानुसार कार्य करता है जो केवल {{mvar|k}} पर निर्भर करता है, इसी सम्मिश्रता वर्ग को FPT कहा जाता है।
-: एक पैरामिट्रीकृत समस्या {{mvar|L}} निश्चित-पैरामीटर ट्रैक्टेबल है यदि प्रश्न<math>(x, k) \in L</math>? समय में तय किया जा सकता है <math>f(k) \cdot |x|^{O(1)}</math>, कहाँ {{mvar|f}} एक मनमाना कार्य है जो केवल पर निर्भर करता है {{mvar|k}}. इसी जटिलता वर्ग को FPT कहा जाता है।
+उदाहरण के लिए, एल्गोरिदम जो वर्टेक्स कवर समस्या का समाधान करता है <math>O(kn + 1.274^k)</math> समय,<ref>{{harvnb|Chen|Kanj|Xia|2006}}</ref> जहां {{mvar|n}} शीर्षों की संख्या है एवं {{mvar|k}} वर्टेक्स कवर का आकार है। इसका अर्थ यह है कि वर्टेक्स कवर फिक्स्ड-पैरामीटर ट्रैक्टेबल है जो समाधान के आकार के पैरामीटर के रूप में है।
-उदाहरण के लिए, एक एल्गोरिदम है जो वर्टेक्स कवर समस्या को हल करता है <math>O(kn + 1.274^k)</math> समय,<ref>{{harvnb|Chen|Kanj|Xia|2006}}</ref> कहाँ {{mvar|n}} शीर्षों की संख्या है और {{mvar|k}} वर्टेक्स कवर का आकार है। इसका मतलब यह है कि वर्टेक्स कवर फिक्स्ड-पैरामीटर ट्रैक्टेबल है जो समाधान के आकार के पैरामीटर के रूप में है।
+== सम्मिश्रता वर्ग ==
-== जटिलता वर्ग ==
 === एफपीटी ===
-FPT में निश्चित पैरामीटर ट्रैक्टेबल समस्याएं होती हैं, जो कि समय पर हल की जा सकती हैं <math>f(k) \cdot {|x|}^{O(1)}</math> कुछ गणना योग्य समारोह के लिए {{mvar|f}}. आमतौर पर, इस फ़ंक्शन को एकल घातांक के रूप में माना जाता है, जैसे <math>2^{O(k)}</math>, लेकिन परिभाषा ऐसे कार्यों को स्वीकार करती है जो और भी तेज़ी से बढ़ते हैं। यह इस वर्ग के प्रारंभिक इतिहास के एक बड़े हिस्से के लिए आवश्यक है। परिभाषा का महत्वपूर्ण हिस्सा फॉर्म के कार्यों को बाहर करना है <math>f(n,k)</math>, जैसे कि <math>k^n</math>.
+एफपीटी में निश्चित पैरामीटर ट्रैक्टेबल समस्याएं होती हैं, जो कि समय पर निवारण की जा सकती हैं <math>f(k) \cdot {|x|}^{O(1)}</math> कुछ गणना योग्य फंक्शन के लिए हैं, सामान्यतः इस प्रोग्राम को एकल घातांक के रूप में माना जाता है, जैसे <math>2^{O(k)}</math>, किन्तु  परिभाषा ऐसे कार्यों को स्वीकार करती है जो तीव्र गति से बढ़ते हैं। यह इस वर्ग के प्रारंभिक इतिहास के बड़े भाग के लिए आवश्यक है। परिभाषा का महत्वपूर्ण भाग फॉर्म के कार्यों को बाहर करना है <math>f(n,k)</math>, जैसे कि <math>k^n</math> है।
-क्लास एफपीएल (फिक्स्ड पैरामीटर लीनियर) समय में हल करने योग्य समस्याओं का वर्ग है <math>f(k) \cdot |x|</math> कुछ गणना योग्य समारोह के लिए {{mvar|f}}.<ref>{{harvtxt|Grohe|1999}}</ref> FPL इस प्रकार FPT का एक उपवर्ग है। एक उदाहरण [[बूलियन संतुष्टि]] समस्या है, जो कि चरों की संख्या द्वारा परिचालित है। आकार का एक दिया गया सूत्र {{mvar|m}} साथ {{mvar|k}} समय में क्रूर बल द्वारा चरों की जाँच की जा सकती है <math>O(2^km)</math>. आकार का एक शीर्ष आवरण {{mvar|k}} क्रम के एक ग्राफ में {{mvar|n}} समय पर मिल सकता है <math>O(2^kn)</math>, इसलिए वर्टेक्स कवर की समस्या भी FPL में है।
+क्लास एफपीएल (फिक्स्ड पैरामीटर लीनियर) समय में समाधान करने योग्य समस्याओं का वर्ग <math>f(k) \cdot |x|</math>है, कुछ गणना योग्य फंक्शन {{mvar|f}}  के लिए है। <ref>{{harvtxt|Grohe|1999}}</ref> एफपीएल (FPL) इस प्रकार एफपीटी (FPT) का उपवर्ग है। उदाहरण [[बूलियन संतुष्टि]] समस्या है, जो कि चरों की संख्या द्वारा परिचालित है। {{mvar|k}} चर के साथ आकार {{mvar|m}} के दिए गए सूत्र को समय में क्रूर बल द्वारा <math>O(2^km)</math> चरों का प्रतिशोधन किया जा सकता हैI क्रम {{mvar|n}} के ग्राफ में आकार {{mvar|k}} क्रम के ग्राफ में  समय पाया जा सकता है <math>O(2^kn)</math>, इसलिए वर्टेक्स कवर की समस्या भी एफपीटी में है।
-एक समस्या का एक उदाहरण जो माना जाता है कि एफपीटी में नहीं है, रंगों की संख्या के आधार पर [[ग्राफ रंग]] का पैरामीटर है। यह ज्ञात है कि 3-रंग एनपी-हार्ड है, और ग्राफ के लिए एक एल्गोरिदम है {{mvar|k}}-समय पर रंग भरना <math>f(k)n^{O(1)}</math> के लिए <math>k=3</math> इनपुट के आकार में बहुपद समय में चलेगा। इस प्रकार, यदि रंगों की संख्या द्वारा पैरामीटर किए गए ग्राफ़ रंग एफपीटी में थे, तो पी बनाम एनपी समस्या | पी = एनपी।
+समस्या का उदाहरण जो माना जाता है कि एफपीटी में नहीं है, रंगों की संख्या के आधार पर [[ग्राफ रंग]] का पैरामीटर है। यह ज्ञात है कि 3-रंग एनपी-हार्ड है, एवं ग्राफ के लिए एल्गोरिदम हैI <math>f(k)n^{O(1)}</math> के लिए <math>k=3</math> इनपुट के आकार में बहुपद समय में होगा। इस प्रकार, यदि रंगों की संख्या द्वारा पैरामीटर किए गए ग्राफ़ रंग एफपीटी में थे, तो P के प्रति NP समस्या है P = NP होता है।
-FPT की कई वैकल्पिक परिभाषाएँ हैं। उदाहरण के लिए, रनिंग-टाइम आवश्यकता को इसके द्वारा प्रतिस्थापित किया जा सकता है <math>f(k) + |x|^{O(1)}</math>. साथ ही, एक पैरामिट्रीकृत समस्या FPT में है यदि इसमें एक तथाकथित कर्नेल है। [[ गुठली बनाना ]] एक प्रीप्रोसेसिंग तकनीक है जो मूल उदाहरण को उसके हार्ड कर्नेल में कम कर देता है, संभवतः बहुत छोटा उदाहरण जो मूल उदाहरण के बराबर है लेकिन एक आकार है जो पैरामीटर में एक फ़ंक्शन से घिरा हुआ है।
+एफपीटी की कई वैकल्पिक परिभाषाएँ हैं। उदाहरण के लिए, वर्तमान समय में आवश्यकता को <math>f(k) + |x|^{O(1)}</math>इसके द्वारा प्रतिस्थापित किया जा सकता हैI साथ ही पैरामिट्रीकृत समस्या एफपीटी में है यदि इसमें तथाकथित कर्नेल है। [[ गुठली बनाना | कर्नेलाइजेशन]] प्रीप्रोसेसिंग प्रविधी है जो मूल उदाहरण को उसके हार्ड कर्नेल में अर्घ्य कर देता है, संभवतः अत्यधिक अल्प उदाहरण जो मूल उदाहरण के सामान है किन्तु आकार है जो पैरामीटर में प्रोग्राम से घिरा हुआ है।
-FPT को 'fpt-reductions' नामक रिडक्शन (जटिलता) की एक पैरामीटरयुक्त धारणा के तहत बंद कर दिया गया है। इस तरह की कटौती एक उदाहरण को बदल देती है <math>(x,k)</math> समतुल्य उदाहरण में कुछ समस्या का <math>(x',k')</math> किसी अन्य समस्या का (के साथ <math>k' \leq g(k)</math>) और समय में गणना की जा सकती है <math>f(k)\cdot p(|x|)</math> कहाँ <math>p</math> एक बहुपद है।
+एफपीटी को <nowiki>''</nowiki>एफटीटी-क्षरण' नामक रिडक्शन (सम्मिश्रता) की पैरामीटरयुक्त धारणा के अनुसार समाप्त कर दिया गया है। इस प्रकार क्षरण उदाहरण को परिवर्तित कर देती है <math>(x,k)</math> कुछ समस्या का समतुल्य उदाहरण में <math>(x',k')</math>  अन्य समस्या का (के साथ <math>k' \leq g(k)</math>) एवं समय में गणना की जा सकती है <math>f(k)\cdot p(|x|)</math> जहां  <math>p</math>  बहुपद है।
-जाहिर है, FPT में सभी बहुपद-समय की गणना योग्य समस्याएं हैं। इसके अलावा, इसमें एनपी में सभी अनुकूलन समस्याएं शामिल हैं जो एक [[कुशल बहुपद-समय सन्निकटन योजना]] | कुशल बहुपद-समय सन्निकटन योजना (ईपीटीएएस) की अनुमति देती हैं।
+स्पष्ट है, एफपीटी में सभी बहुपद-समय की गणना योग्य समस्याएं हैं। इसके अतिरिक्त, इसमें एनपी में सभी अनुकूलन समस्याएं सम्मिलित हैं जो [[कुशल बहुपद-समय सन्निकटन योजना]]  (ईपीटीएएस) की अनुमति देती हैं।
 === डब्ल्यू पदानुक्रम ===
-'डब्ल्यू पदानुक्रम' कम्प्यूटेशनल जटिलता वर्गों का एक संग्रह है। वर्ग डब्ल्यू [i] में एक पैरामिट्रीकृत समस्या है, यदि हर उदाहरण <math>(x, k)</math> (एफटीटी-समय में) एक संयोजी परिपथ में परिवर्तित किया जा सकता है जिसमें अधिक से अधिक i पर [[बाना (सर्किट)]] हो, जैसे कि <math>(x, k)\in L</math> अगर और केवल अगर इनपुट के लिए एक संतोषजनक असाइनमेंट है जो 1 को बिल्कुल k इनपुट प्रदान करता है। वेट एक इनपुट से आउटपुट तक किसी भी पथ पर फैन-इन दो से अधिक के साथ तार्किक इकाइयों की सबसे बड़ी संख्या है। रास्तों पर तार्किक इकाइयों की कुल संख्या (गहराई के रूप में जाना जाता है) को एक स्थिरांक द्वारा सीमित किया जाना चाहिए जो समस्या के सभी उदाहरणों के लिए होल्ड करता है।
+'डब्ल्यू पदानुक्रम' कम्प्यूटेशनल सम्मिश्रता वर्गों का संग्रह है। वर्ग डब्ल्यू [i] में पैरामिट्रीकृत समस्या है, यदि प्रत्येक उदाहरण <math>(x, k)</math> (एफटीटी-समय में) संयोजी परिपथ में परिवर्तित किया जा सकता है जिसमें अधिक से अधिक i पर [[बाना (सर्किट)|भार (परिपथ)]] हो, जैसे कि <math>(x, k)\in L</math> यदि इनपुट के लिए संतोषजनक कार्यभार है जो 1 को कदापि k इनपुट प्रदान करता है। वेट इनपुट से आउटपुट तक किसी भी पथ पर फैन-इन दो से अधिक के साथ तार्किक इकाइयों की सबसे बड़ी संख्या है। परिपथो पर तार्किक इकाइयों की कुल संख्या (सघन के रूप में जाना जाता है) को स्थिरांक द्वारा सीमित किया जाना चाहिए जो समस्या के सभी उदाहरणों के लिए स्थिर करता है।
-ध्यान दें कि <math>\mathsf{FPT} = W[0]</math> और <math>W[i] \subseteq W[j]</math> सभी के लिए <math>i\le j</math>. एफपीटी-कमी के तहत डब्ल्यू पदानुक्रम में कक्षाएं भी बंद हैं।
+ध्यान दें कि <math>\mathsf{FPT} = W[0]</math> एवं  <math>W[i] \subseteq W[j]</math> सभी के लिए <math>i\le j</math>. एफपीटी-कमी के अनुसार डब्ल्यू पदानुक्रम में वर्ग भी बंद हैं।
-कई प्राकृतिक कम्प्यूटेशनल समस्याएं निचले स्तरों, डब्ल्यू [1] और डब्ल्यू [2] पर कब्जा कर लेती हैं।
+कई प्राकृतिक कम्प्यूटेशनल समस्याएं निचले स्तरों, डब्ल्यू [1] एवं डब्ल्यू [2] पर प्रभुत्व कर लेती हैं।
 ==== डब्ल्यू [1] ====
-W[1]-पूर्ण समस्याओं के उदाहरणों में शामिल हैं
+W[1]-पूर्ण समस्याओं के उदाहरणों में सम्मिलित हैंI
-* यह तय करना कि दिए गए ग्राफ़ में k आकार का एक क्लिक (ग्राफ़ सिद्धांत) है या नहीं
+* यह निर्धारित करना कि दिए गए ग्राफ़ में k आकार का समूह है या नहीं हैं।
-* यह तय करना कि दिए गए ग्राफ़ में आकार k का एक स्वतंत्र सेट (ग्राफ़ सिद्धांत) है या नहीं
+* यह निर्धारित करना कि दिए गए ग्राफ़ में k आकार का स्वतंत्र समूह है या नहीं हैंI
-* यह तय करना कि क्या दी गई गैर-नियतात्मक एकल-टेप ट्यूरिंग मशीन k चरणों (लघु ट्यूरिंग मशीन स्वीकृति समस्या) के भीतर स्वीकार करती है। यह f(k) टेप और यहां तक कि f(k)-डायमेंशनल टेप के f(k) के साथ गैर-नियतात्मक ट्यूरिंग मशीनों पर भी लागू होता है, लेकिन इस विस्तार के साथ भी, f(k) टेप वर्णमाला के आकार का प्रतिबंध निश्चित-पैरामीटर ट्रैक्टेबल है। महत्वपूर्ण रूप से, प्रत्येक चरण पर ट्यूरिंग मशीन की ब्रांचिंग को n, इनपुट के आकार पर निर्भर करने की अनुमति है। इस तरह, ट्यूरिंग मशीन एन का पता लगा सकती है<sup>O(k)</sup> संगणना पथ।
+* यह निर्धारित करना कि क्या दी गई गैर-नियतात्मक एकल-टेप ट्यूरिंग मशीन k चरणों (लघु ट्यूरिंग मशीन स्वीकृति समस्या) के अंदर स्वीकार करती है। यह f(k) टेप एवं यहां तक कि f(k)-डायमेंशनल टेप के f(k) के साथ गैर-नियतात्मक ट्यूरिंग मशीनों पर भी प्रारम्भ होता है, किन्तु  इस विस्तार के साथ भी, f(k) टेप वर्णमाला के आकार का प्रतिबंध निश्चित-पैरामीटर ट्रैक्टेबल है। महत्वपूर्ण रूप से, प्रत्येक चरण पर ट्यूरिंग मशीन की ब्रांचिंग को n, इनपुट के आकार पर निर्भर करने की अनुमति है। इस प्रकार, ट्यूरिंग मशीन N<sup>O(k)</sup> की जानकारी प्राप्त कर सकती है।
 ==== डब्ल्यू [2] ====
-W[2]-पूर्ण समस्याओं के उदाहरणों में शामिल हैं
+W[2]-पूर्ण समस्याओं के उदाहरणों में सम्मिलित हैंI
-* यह तय करना कि दिए गए ग्राफ़ में आकार k का एक प्रभावशाली सेट है या नहीं
+* यह निर्धारित करना कि दिए गए ग्राफ़ में k आकार का प्रभावशाली समूह है या नहीं हैंI
-* यह तय करना कि क्या दी गई गैर-नियतात्मक ट्यूरिंग मशीन समकक्ष # मल्टी-टेप ट्यूरिंग मशीन | मल्टी-टेप ट्यूरिंग मशीन k चरणों के भीतर स्वीकार करती है (लघु मल्टी-टेप ट्यूरिंग मशीन स्वीकृति समस्या)। महत्वपूर्ण रूप से, ब्रांचिंग को n (जैसे W[1] प्रकार) पर निर्भर रहने की अनुमति है, जैसा कि टेपों की संख्या है। एक वैकल्पिक W[2]-पूर्ण सूत्रीकरण केवल एकल-टेप ट्यूरिंग मशीनों की अनुमति देता है, लेकिन वर्णमाला का आकार n पर निर्भर हो सकता है।
+* यह निर्धारित करना कि क्या दी गई गैर-नियतात्मक ट्यूरिंग मशीन k चरणों (लघु मल्टी-टेप ट्यूरिंग मशीन स्वीकृति समस्या) के अंदर स्वीकार करती है। महत्वपूर्ण रूप से, ब्रांचिंग को n (जैसे W[1] प्रकार) पर निर्भर रहने की अनुमति है, जैसा कि टेपों की संख्या है। वैकल्पिक W[2]-पूर्ण सूत्रीकरण केवल एकल-टेप ट्यूरिंग मशीनों की अनुमति देता है, किन्तु  वर्णमाला का आकार n पर निर्भर हो सकता है।
-==== डब्ल्यू [टी] ====
+==== डब्ल्यू [T] ====
-<math>W[t]</math> भारित बाने के परिवार का उपयोग करके परिभाषित किया जा सकता है-{{mvar|t}}-गहराई-{{mvar|d}} सैट समस्याओं के लिए <math>d\geq t</math>:
+<math>W[t]</math> को वेटेड वेट-टी-डेप्थ-डी एसएटी समस्याओं के परिवार का उपयोग करके परिभाषित किया जा सकता है <math>W[t,d]</math>पैरामिट्रीकृत समस्याओं का वर्ग है जो इस समस्या को एफपीटी अर्घ्य  करता है, एवं  <math>W[t] = \bigcup_{d\geq t} W[t,d]</math> होता हैI
-<math>W[t,d]</math> पैरामिट्रीकृत समस्याओं का वर्ग है जो इस समस्या को fpt-reduce करता है, और <math>W[t] = \bigcup_{d\geq t} W[t,d]</math>.
-यहाँ, भारित बाना-{{mvar|t}}-गहराई-{{mvar|d}} SAT निम्न समस्या है:
+यहाँ, वेटेड वेट-d-डेप्थ-d एसएटी निम्नलिखित समस्या हैI
-* इनपुट: अधिक से अधिक गहराई का एक बूलियन सूत्र {{mvar|d}} और अधिक से अधिक बाना {{mvar|t}}, और एक संख्या {{mvar|k}}. गहराई रूट से पत्ते तक किसी भी पथ पर फाटकों की अधिकतम संख्या है, और बाना जड़ से पत्ती तक किसी भी पथ पर कम से कम तीन फाटकों की अधिकतम संख्या है।
+* इनपुट अधिक से अधिक {{mvar|d}} पर घनीभूत का बूलियन सूत्र एवं अधिक से अधिक {{mvar|t}}, पर बल एवं संख्या {{mvar|k}} हैI ठोस रूट से पत्ते तक किसी भी पथ पर फाटकों की अधिकतम संख्या है, एवं जड़ से पत्ती तक किसी भी पथ पर अर्घ्य से अर्घ्य तीन फाटकों की अधिकतम संख्या है।
-* प्रश्न: क्या सूत्र में सटीक रूप से हैमिंग भार का संतोषजनक कार्य है {{mvar|k}}?
+* प्रश्न: क्या सूत्र में स्थिर रूप से हैमिंग बल का संतोषजनक कार्य {{mvar|k}} है?
-यह दिखाया जा सकता है कि के लिए <math>t\geq2</math> समस्या भारित {{mvar|t}}-Normalize SAT के लिए पूरा हो गया है <math>W[t]</math> एफपीटी-कटौती के तहत।<ref>{{cite journal |last1=Buss |first1=Jonathan F |last2=Islam |first2=Tarique |title=बाने के पदानुक्रम को सरल बनाना|journal=[[Theoretical Computer Science (journal)|Theoretical Computer Science]] |year=2006 |volume=351 |number=3 |pages=303–313 |doi=10.1016/j.tcs.2005.10.002|doi-access=free }}</ref>
+यह दर्शाया जा सकता है कि <math>t\geq2</math> के लिए भारित समस्या {{mvar|t}}-सामान्यीकृत एसएटी (SAT) के लिए पूर्ण है <math>W[t]</math> एफपीटी क्षरण के अनुसार <ref>{{cite journal |last1=Buss |first1=Jonathan F |last2=Islam |first2=Tarique |title=बाने के पदानुक्रम को सरल बनाना|journal=[[Theoretical Computer Science (journal)|Theoretical Computer Science]] |year=2006 |volume=351 |number=3 |pages=303–313 |doi=10.1016/j.tcs.2005.10.002|doi-access=free }}</ref>यहाँ, भारित {{mvar|t}}-सामान्यीकृत एसएटी निम्नलिखित समस्या हैI
-यहाँ, भारित {{mvar|t}}-सामान्य करें SAT निम्न समस्या है:
-* इनपुट: अधिक से अधिक गहराई का एक बूलियन सूत्र {{mvar|t}} शीर्ष पर एक AND-गेट और एक संख्या के साथ {{mvar|k}}.
+* इनपुट शीर्ष पर एंड (AND) गेट एवं के साथ {{mvar|t}} क्षरण का लियन सूत्र  {{mvar|k}} हैI
-* प्रश्न: क्या सूत्र में सटीक रूप से हैमिंग भार का संतोषजनक कार्य है {{mvar|k}}?
+* प्रश्न: क्या सूत्र में स्थिर रूप से हैमिंग बल का संतोषजनक कार्य {{mvar|k}} है?
-==== डब्ल्यू [पी] ====
+==== डब्ल्यू [P] ====
-डब्ल्यू [पी] समस्याओं का वर्ग है जिसे एक गैर-निर्धारिती द्वारा तय किया जा सकता है <math>h(k) \cdot {|x|}^{O(1)}</math>-अपना समय सेट करें<math>O(f(k)\cdot \log n)</math> पर गणना में nondeterministic विकल्प <math>(x,k)</math> (के-प्रतिबंधित ट्यूरिंग मशीन)। {{harvtxt|Flum|Grohe|2006}}
+डब्ल्यू [P] समस्याओं का वर्ग है जिसे गैर-निर्धारिती द्वारा निर्धारित  किया जा सकता है <math>h(k) \cdot {|x|}^{O(1)}</math>-स्वयं का समय निर्धारित करें <math>O(f(k)\cdot \log n)</math> पर गणना में गैर नियतात्मक विकल्प <math>(x,k)</math> (के-प्रतिबंधित ट्यूरिंग मशीन) है।
-यह ज्ञात है कि एफपीटी डब्ल्यू [पी] में निहित है, और समावेशन को सख्त माना जाता है। हालाँकि, इस मुद्दे को हल करने से P बनाम NP समस्या का समाधान होगा।
+यह ज्ञात है कि एफपीटी डब्ल्यू [P] में निहित है, एवं समावेशन को कठोर माना जाता है। चूँकि, इस विषय का समाधान करने से P के प्रति NP समस्या का समाधान होगा।
-अपैरामीटरीकृत कम्प्यूटेशनल जटिलता के अन्य कनेक्शन हैं कि एफपीटी डब्ल्यू [पी] के बराबर है अगर और केवल अगर [[सर्किट संतुष्टि]] समय पर तय की जा सकती है <math>\exp(o(n))m^{O(1)}</math>, या यदि और केवल अगर कोई संगणनीय, गैर-घटता हुआ, असीमित फ़ंक्शन f है, जैसे कि सभी भाषाओं को एक गैर-नियतात्मक बहुपद-समय ट्यूरिंग मशीन द्वारा मान्यता प्राप्त है {{tmath|f(n)\log n}} गैर नियतात्मक विकल्प P में हैं।
+अपैरामीटरीकृत कम्प्यूटेशनल सम्मिश्रता के अन्य कनेक्शन हैं कि एफपीटी डब्ल्यू [P] के समान है, यदि [[सर्किट संतुष्टि|परिपथ संतुष्टि]] समय पर निर्धारित की जा सकती है <math>\exp(o(n))m^{O(1)}</math>, या कोई संगणनीय, अन्य-घटता हुआ, असीमित प्रोग्राम f है, जैसे कि सभी भाषाओं को गैर-नियतात्मक बहुपद-समय ट्यूरिंग मशीन द्वारा मान्यता प्राप्त है {{tmath|f(n)\log n}} अन्य नियतात्मक विकल्प P में हैं।
-डब्ल्यू [पी] को शिथिल रूप से समस्याओं के वर्ग के रूप में सोचा जा सकता है जहां हमारे पास एक सेट है {{mvar|S}} का {{mvar|n}} आइटम, और हम एक सबसेट खोजना चाहते हैं <math>T \subset S</math> आकार का {{mvar|k}} जैसे कि एक निश्चित संपत्ति रखती है। हम एक सूची के रूप में एक विकल्प को एन्कोड कर सकते हैं {{mvar|k}} पूर्णांक, बाइनरी में संग्रहीत। चूँकि इनमें से उच्चतम कोई भी संख्या हो सकती है {{mvar|n}}, <math>\lceil\log_2 n\rceil</math> बिट्स प्रत्येक संख्या के लिए आवश्यक हैं। इसलिए <math>k \cdot \lceil\log_2 n\rceil </math> किसी विकल्प को एन्कोड करने के लिए कुल बिट्स की आवश्यकता होती है। इसलिए हम एक उपसमुच्चय का चयन कर सकते हैं <math>T\subset S</math> साथ <math>O(k\cdot \log n)</math> गैर-नियतात्मक विकल्प।
+डब्ल्यू [P] को शिथिल रूप से समस्याओं के वर्ग के रूप में विचार किया जा सकता है जहां हमारे पास {{mvar|n}} वस्तुओं का समूह {{mvar|S}} का आइटम, एवं हम उपसमुच्चय का शोध चाहते हैं <math>T \subset S</math> आकार {{mvar|k}} का जैसे कि निश्चित वित्त रखती है। हम बाइनरी में संग्रहीत k पूर्णांकों की सूची के रूप में विकल्प को एन्कोड कर सकते हैं। चूँकि इनमें से कोई भी उच्चतम संख्या n हो सकती है, प्रत्येक संख्या के लिए <math>\lceil\log_2 n\rceil</math>बिट्स की आवश्यकता होती है। इसलिए <math>k \cdot \lceil\log_2 n\rceil </math> किसी विकल्प को एन्कोड करने के लिए कुल बिट्स की आवश्यकता होती है। इसलिए हम उपसमुच्चय का चयन कर सकते हैं <math>T\subset S</math> के साथ <math>O(k\cdot \log n)</math> गैर-नियतात्मक विकल्प होते है।
 === एक्सपी ===
-XP पैरामिट्रीकृत समस्याओं का वर्ग है जिसे समय पर हल किया जा सकता है <math>n^{f(k)}</math> कुछ गणना योग्य समारोह के लिए {{mvar|f}}. इन समस्याओं को [[टुकड़ा]] बहुपद कहा जाता है, इस अर्थ में कि निश्चित k के प्रत्येक स्लाइस में एक बहुपद एल्गोरिथम होता है, हालांकि संभवतः प्रत्येक k के लिए एक अलग घातांक के साथ। इसकी तुलना FPT से करें, जो केवल k के प्रत्येक मान के लिए एक अलग निरंतर प्रीफैक्टर की अनुमति देता है। XP में FPT होता है, और यह ज्ञात है कि यह नियंत्रण विकर्णकरण द्वारा सख्त है।
+एक्सपी पैरामिट्रीकृत समस्याओं का वर्ग है जिसका समय पर समाधान किया जा सकता है <math>n^{f(k)}</math> कुछ गणना योग्य फंक्शन {{mvar|f}}  के लिए इन समस्याओं को [[टुकड़ा|अंश]] बहुपद कहा जाता है, इस अर्थ में कि निश्चित k के प्रत्येक अंश में बहुपद एल्गोरिथम होता है, चूँकि संभवतः प्रत्येक k के लिए भिन्न घातांक के साथ इसकी तुलना एफपीटी से करें, जो केवल k के प्रत्येक मान के लिए निरंतर प्रीफैक्टर की अनुमति देता है। एक्सपी में एफपीटी होता है, एवं यह ज्ञात है कि यह नियंत्रण विकर्णकरण द्वारा कठोर होते है।
-{{Expand section|date=April 2019}}
 === पैरा-एनपी ===
-पैरा-एनपी पैरामीटरयुक्त समस्याओं का वर्ग है जिसे समय पर एक गैर-नियतात्मक एल्गोरिदम द्वारा हल किया जा सकता है <math>f(k) \cdot |x|^{O(1)}</math> कुछ गणना योग्य समारोह के लिए {{mvar|f}}. ह ज्ञात है कि <math>\textsf{FPT}=\textsf{para-NP}</math> अगर और केवल अगर <math>\textsf{P}=\textsf{NP}</math>.{{sfnp|Flum|Grohe|2006|page=39}}
+पैरा-एनपी पैरामीटरयुक्त समस्याओं का वर्ग है जिसे समय पर गैर-नियतात्मक एल्गोरिदम द्वारा समाधान किया जा सकता है <math>f(k) \cdot |x|^{O(1)}</math> कुछ गणना योग्य समारोह {{mvar|f}}  के लिए ज्ञात है कि <math>\textsf{FPT}=\textsf{para-NP}</math> यदि एवं यदि  <math>\textsf{P}=\textsf{NP}</math> होते है।{{sfnp|Flum|Grohe|2006|page=39}} समस्या पैरा-एनपी-हार्ड है यदि <math>\textsf{NP}</math>- पैरामीटर के निरंतर मान के लिए पूर्व से ही कठिन है। अर्थात फिक्स {{mvar|k}} का अंश है अर्थात <math>\textsf{NP}</math>- हार्ड पैरामिट्रीकृत समस्या जो है <math>\textsf{para-NP}</math> हार्ड वर्ग से संबंधित नहीं हो सकता <math>\textsf{XP}</math>, जब तक <math>\textsf{P}=\textsf{NP}</math>. a. का उत्कृष्ट उदाहरण है <math>\textsf{para-NP}</math>- हार्ड पैरामिट्रीकृत समस्या ग्राफ कलरिंग है, जिसे रंगों की संख्या {{mvar|k}} द्वारा परिचालित किया गया है, जो पूर्व से ही है <math>\textsf{NP}</math> के लिए कठिन <math>k=3</math>) है।
-एक समस्या पैरा-एनपी-हार्ड है यदि यह है <math>\textsf{NP}</math>-पैरामीटर के निरंतर मान के लिए पहले से ही कठिन है। यानी फिक्स का एक टुकड़ा है {{mvar|k}} वह है <math>\textsf{NP}</math>-मुश्किल। एक पैरामिट्रीकृत समस्या जो है <math>\textsf{para-NP}</math>-हार्ड वर्ग से संबंधित नहीं हो सकता <math>\textsf{XP}</math>, जब तक <math>\textsf{P}=\textsf{NP}</math>. ए. का एक उत्कृष्ट उदाहरण है <math>\textsf{para-NP}</math>-हार्ड पैरामिट्रीकृत समस्या ग्राफ कलरिंग है, जो संख्या द्वारा परिचालित है {{mvar|k}} रंग, जो पहले से ही है <math>\textsf{NP}</math>-के लिए कठिन <math>k=3</math> (ग्राफ़ कलरिंग # कम्प्यूटेशनल जटिलता देखें)।
+=== पदानुक्रम ===
+A पदानुक्रम W पदानुक्रम के समान कम्प्यूटेशनल सम्मिश्रता वर्गों का संग्रह है, जबकि W पदानुक्रम एनपी में निहित पदानुक्रम है, A पदानुक्रम शास्त्रीय सम्मिश्रता से [[बहुपद-समय पदानुक्रम]] की अधिक सरलता से अनुकृति करता है। यह ज्ञात है कि A[1] = W[1] धारण करता है।
-=== एक पदानुक्रम ===
-A पदानुक्रम W पदानुक्रम के समान कम्प्यूटेशनल जटिलता वर्गों का एक संग्रह है। हालाँकि, जबकि W पदानुक्रम NP में निहित एक पदानुक्रम है, A पदानुक्रम शास्त्रीय जटिलता से [[बहुपद-समय पदानुक्रम]] की अधिक बारीकी से नकल करता है। यह ज्ञात है कि A[1] = W[1] धारण करता है।
 == यह भी देखें ==
-* पैरामीटरयुक्त [[सन्निकटन एल्गोरिथ्म]], [[अनुकूलन समस्या]] के लिए FPT समय में चलने वाला एक एल्गोरिथ्म समाधान सन्निकटन एल्गोरिथम हो सकता है।
+* पैरामीटरयुक्त सन्निकटन एल्गोरिथ्म, अनुकूलन समस्या के लिए एफपीटी समय में चलने वाला एल्गोरिथ्म समाधान सन्निकटन एल्गोरिथम हो सकता है।
 == टिप्पणियाँ ==
@@ Line 200: / Line 192: @@
 * [http://fpt.wikidot.com/ Wiki on parameterized complexity]
 * [http://www.sprg.uniroma2.it/home/cesati/research/compendium/ Compendium of Parameterized Problems]
-[[Category: पैरामीटरयुक्त जटिलता | पैरामीटरयुक्त जटिलता ]] [[Category: कम्प्यूटेशनल जटिलता सिद्धांत]]
-[[Category: Machine Translated Page]]
 [[Category:Created On 28/02/2023]]
+[[Category:Lua-based templates]]
+[[Category:Machine Translated Page]]
+[[Category:Pages with script errors]]
+[[Category:Short description with empty Wikidata description]]
+[[Category:Templates Vigyan Ready]]
+[[Category:Templates that add a tracking category]]
+[[Category:Templates that generate short descriptions]]
+[[Category:Templates using TemplateData]]
+[[Category:कम्प्यूटेशनल जटिलता सिद्धांत]]
+[[Category:पैरामीटरयुक्त जटिलता| पैरामीटरयुक्त जटिलता ]]

Anonymous

Search

पैरामिट्रीकृत सम्मिश्रता: Difference between revisions

Namespaces

More

Page actions

Latest revision as of 16:31, 12 October 2023

Contents