घातीय समय परिकल्पना

कम्प्यूटरीकृत जटिलता सिद्धांत में, घातीय समय परिकल्पना अप्रमाणित कम्प्यूटरीकृत कठोरता की धारणा है, जिसे इम्पाग्लिआज़ो & पाटुरी (1999) द्वारा तैयार किया गया था, इसमें कहा गया है कि 3-SAT या 3-CNF बूलियन फ़ार्मुलों की संतुष्टि को उप-घातांकीय समय में हल नहीं किया जा सकता है, अर्थात, $2^{(1-\epsilon )n}$ सभी स्थिरांक के लिए $\epsilon >0$, जहां n सूत्र में चरों की संख्या को प्रदर्शित करता है।

घातीय समय परिकल्पना, यदि सत्य है, तो इसका अर्थ यह होगा कि P तथा NP के बीच का अन्तर इसकी समस्या या P ≠ NP को प्रदर्शित करता हैं, अपितु यह मुख्य रूप से मजबूत कथन है। इसका तात्पर्य यह है कि कई कम्प्यूटरीकृत समस्याएं जटिलता में समतुल्य हैं, इस अर्थ में कि यदि उनमें से के पास उप-घातीय समय कलन विधि है तो वे सभी करते हैं, और इन समस्याओं के लिए कई ज्ञात कलन विधि में इष्टतम या निकट-इष्टतम समय complexity. होता है।

परिभाषा

$k$-SAT}एटी समस्या बूलियन संतुष्टि समस्या का ऐसा संस्करण है जिसमें समस्या का इनपुट संयोजक सामान्य रूप में बूलियन अभिव्यक्ति को प्रदर्शित करता है, अर्ताथ चर और उनके निषेधों का और अन्य अधिकतम के साथ $k$ प्रति खंड चर. लक्ष्य यह निर्धारित करता है, यह इस प्रकार हैं कि क्या इस अभिव्यक्ति को इसके चरों के लिए बूलियन मानों के कुछ असाइनमेंट द्वारा सत्य बनाया जा सकता है। इसके आधार पर 2-संतोषजनकता या 2-SAT में रैखिक समय कलन विधि को प्रदर्शित करता है, अपितु सभी ज्ञात कलन विधि बड़े हैं, जिसके कारण $k$ घातीय फलन के आधार पर निर्भर करते हुए, घातांकीय समय लें $k$. उदाहरण के लिए, वॉकसैट संभाव्य कलन विधि हल कर सकता है, इस प्रकार $k$-SAT के औसत समय में

$$\left(2-{\frac {2}{k}}\right)^{n}n^{O(1)},$$

जहाँ $n$ दिए गए चरों की संख्या है $k$-SAT instance. प्रत्येक के लिए integer $k\geq 3$, के लिए $s_{k}$ को परिभाषित करता हैं। इस प्रकार ऐसी सबसे छोटी संख्या को $k$-SAT द्वारा हल किया जा सकता है, इसके आधारा पर time $2^{s_{k}n+o(n)}$. जो न्यूनतम समय में नहीं हो सकता है, यदि इसके लिए उपयुक्त उत्तम कलन विधि के अनुक्रम में उनकी समय सीमा में तदनुसार छोटी घातीय वृद्धि होती है, इस स्थिति में, परिभाषित करें $s_{k}$ वास्तविक संख्याओं का न्यूनतम रहता हैं। जिसके कारण $\delta$ हैं, जिसके लिए $k$-SATमें हल किया जा सकता है, इस प्रकार time $O(2^{\delta n})$. क्योंकि बड़ी समस्याओं के साथ $k$ इससे सरल नहीं हो सकता हैं, इस प्रकार उपयुक्त संख्या को इस प्रकार क्रमबद्ध किया गया है कि $s_{3}\leq s_{4}\leq \cdots$, और वॉकसैट के कारण इसका मान अधिकतम हैं जो इस प्रकार हैं-

$$s_{k}\leq \log _{2}\left(2-{\frac {2}{k}}\right)<1.$$

घातीय समय परिकल्पना यह अनुमान है कि वे सभी गैर-शून्य हैं, या समकक्ष रूप से, उनमें से सबसे छोटा, $s_{3}$, nonzero. है।

कुछ स्रोत घातीय समय परिकल्पना को थोड़ा कमजोर कथन के रूप में परिभाषित करते हैं, जिसमें 3-SAT को time $2^{o(n)}$. के लिए हल नहीं किया जा सकता है, इस कारण यदि 3-SAT को हल करने के लिए कोई कलन विधि उपस्थित है, जिसके कारण time $2^{o(n)}$, तब $s_{3}$ शून्य के बराबर होगा, चूंकि, यह वर्तमान मान के लिए इस प्रकार अनुरूप है कि 3-SAT कलन विधि का क्रम हो सकता है, प्रत्येक का चलने का समय $O(2^{\delta _{i}n})$ संख्याओं के अनुक्रम के लिए $\delta _{i}$ शून्य की ओर यह मान प्रदर्शित करता हैं। अपितु जहां इन कलन विधि का विवरण इतनी तेज़ी से बढ़ रहा है कि भी कलन विधि स्वचालित रूप से सबसे उपयुक्त का चयन और चला नहीं सकता है। अगर ऐसा ही होता तो $s_{3}$ शून्य के बराबर होगा, भले ही कोई एकल कलन विधि time $2^{o(n)}$. नहीं चल रहा हो। जिसके कारण किसी घातीय समय परिकल्पना का संबंधित संस्करण गैर-समान घातीय समय परिकल्पना है, जो बताता है कि कलन विधि का कोई परिवार नहीं है, इस प्रकार इनपुट की प्रत्येक लंबाई के लिए, जटिलता की भावना उत्पन्न होती हैं जिसके 3- को हल कर सकता है, जिसके आधार पर time $2^{o(n)}$. मान प्राप्त किया जा सकता हैं।

क्योंकि संख्याएँ $s_{3},s_{4},\dots$ एकरसता का निर्माण करें जो ऊपर से बंधी रहती हैं, उन्हें सीमा तक अभिसरण करना होगा।

$$s_{\infty }=\lim _{k\to \infty }s_{k}.$$

इसकी सबसे शक्तिशाली घातांकीय समय परिकल्पना (SETH) है जिसका अनुमानतः मान that $s_{\infty }=1$. है।

निहितार्थ

संतुष्टि

इसके लिए यह संभव नहीं है $s_{k}$ बराबर करने के लिए $s_{\infty }$ को किसी finite $k$: के लिए जैसे इम्पाग्लिआज़ो, पाटुरी & जेन (2001) द्वारा दिखाया गया हैं कि इसके लिए $\alpha$ स्थिरांक उपस्थित है, जो इस प्रकार हैं कि that $s_{k}\leq s_{\infty }(1-\alpha /k)$. मान प्राप्त होता हैं। इसलिए, यदि घातांकीय समय परिकल्पना सत्य है, तो इसके अनंत रूप से कई मान होने चाहिए $k$ जिसके लिए $s_{k}$ अलग होगी जिसका मान from $s_{k+1}$. प्राप्त होता है।

इस क्षेत्र में महत्वपूर्ण उपकरण स्पार्सिफिकेशन लेम्मा है, जो इम्पाग्लिआज़ो, पाटुरी & जेन (2001) के संदर्भ को दर्शाता है कि इसके लिए every $\varepsilon >0$, कोई $k$-CNF सूत्र द्वारा प्रतिस्थापित किया जा सकता है, इस प्रकार $O(2^{\varepsilon n})$ सरल $k$-CNF ऐसे सूत्र जिनमें प्रत्येक चर केवल स्थिर संख्या में ही प्रकट होता है, और इसलिए जिसमें उपवाक्यों की संख्या रैखिक होती है। स्पार्सिफिकेशन लेम्मा को किसी दिए गए सूत्र में गैर-रिक्त सामान्य प्रतिच्छेदन वाले खंडों के बड़े समुच्चयों को बार-बार ढूंढकर और सूत्र को दो सरल सूत्रों द्वारा प्रतिस्थापित करके सिद्ध किया जाता है, जिनमें से प्रत्येक खंड को उनके सामान्य प्रतिच्छेदन द्वारा प्रतिस्थापित किया जाता है और दूसरे में प्रत्येक खंड से प्रतिच्छेदन हटा दिया गया है। स्पार्सिफिकेशन लेम्मा को लागू करके और फिर खंडों को विभाजित करने के लिए नए चर का उपयोग करके, किसी मान के लिए उक्त समुच्चय $O(2^{\varepsilon n})$ प्राप्त कर सकता है, जिसके आधार पर 3-सीएनएफ सूत्र, प्रत्येक में चर की रैखिक संख्या होती है, जैसे कि मूल $k$-CNF सूत्र तभी संतोषजनक है जब इन 3-सीएनएफ सूत्रों में से कम से कम संतोषजनक हो। इसलिए, यदि 3-SAT को उप-घातीय समय में हल किया जा सकता है, तो $k$-SAT उपघातीय समय में भी कोई इस कमी का उपयोग हल करने के लिए कर सकता है। समान रूप से, if $s_{k}>0$ के लिए any $k>0$, तब $s_{3}>0$ साथ ही, और घातीय समय परिकल्पना true. होगी।

इसके आधार पर सीमित मूल्य $s_{\infty }$ संख्याओं के क्रम का $s_{k}$ अधिकतम बराबर है, जिसका मान to $s_{\operatorname {CNF} }$, प्राप्त होता हैं जहाँ $s_{\operatorname {CNF} }$ संख्याओं का न्यूनतम मान $\delta$ है। इस प्रकार जैसे कि खंड लंबाई सीमा के बिना संयोजक सामान्य रूप सूत्रों की संतुष्टि को time $O(2^{\delta n})$. द्वारा हल किया जा सकता है, इसलिए, यदि मजबूत घातीय समय परिकल्पना सत्य है, तो सामान्य सीएनएफ संतुष्टि के लिए कोई कलन विधि नहीं होगा जो सभी संभावित सत्य असाइनमेंट पर क्रूर-बल खोज से अधिक तेज है। चूंकि, यदि मजबूत घातीय समय परिकल्पना विफल हो जाती है, तब भी यह संभव होगा $s_{\operatorname {CNF} }$ बराबर करने के लिए one. मान प्राप्त होता हैं।

अन्य परिकल्पित समस्याएँ

घातीय समय परिकल्पना का तात्पर्य है कि जटिलता वर्ग एसNP (जटिलता) में कई अन्य समस्याओं में कलन विधि नहीं हैं जिनका चलने का समय इससे तेज है, इस प्रकार $c^{n}$ के लिए constant $c$. द्वारा इन समस्याओं में ग्राफ़ कलरिंग|ग्राफ़ सम्मिलित है k-रंग योग्यता, हैमिल्टनियन चक्र, अधिकतम क्लिक्स, अधिकतम स्वतंत्र समुच्चय और शीर्ष आवरण का पता लगाकर $n$-vertex रेखांकन के लिए इसके विपरीत, यदि इनमें से किसी भी समस्या में उप-घातांकीय कलन विधि है, तो घातांकीय समय परिकल्पना को false. मान द्वारा दिखाया जा सकता है।

यदि बहुपद समय में समूह या लघुगणकीय आकार के स्वतंत्र समुच्चय पाए जा सकते हैं, तो घातीय समय परिकल्पना असत्य होगी। इसलिए भले ही ऐसे छोटे आकार के समूह या स्वतंत्र समुच्चय ढूंढना NP-पूर्ण होने की संभावना नहीं है, घातीय समय परिकल्पना का तात्पर्य है कि ये समस्याएं non-polynomial. हैं, इस प्रकार इससे अधिक मान को सामान्यतः घातीय समय परिकल्पना का तात्पर्य है कि क्लिक्स या आकार के स्वतंत्र समुच्चय ढूंढना संभव नहीं है $k$ में time $n^{o(k)}$. को घातांकीय समय परिकल्पना के रूप में प्रदर्शित करते हैं, जिसका यह भी तात्पर्य है कि 3SUM को हल करना संभव नहीं है, जिसके कारण k-SUM समस्या इस प्रकार है कि $n$ वास्तविक संख्याएँ हैं जहाँ पर $k$ उनमें से जो शून्य में जोड़ते हैं, जिसमें time $n^{o(k)}$.मान प्राप्त होता हैं। इस प्रकार मजबूत घातीय समय परिकल्पना का तात्पर्य है कि इसे खोजना संभव नहीं है $k$-vertex अंदर की तुलना में समुच्चय पर अधिक तेजी से time $n^{k-o(1)}$. का प्रभावी होना यहाँ पर मुख्य हैं।

घातीय समय परिकल्पना का तात्पर्य यह भी है कि टूर्नामेंट (ग्राफ सिद्धांत) पर भारित फीडबैक आर्क समुच्चय समस्या में चलने के साथ पैरामीट्रिज्ड कलन विधि नहीं है, इस प्रकार time ${\textstyle O(2^{o({\sqrt {\operatorname {OPT} }})}n^{O(1)})}$. चूंकि इसमें चलने के साथ पैरामीटरयुक्त कलन विधि time ${\textstyle O(2^{O({\sqrt {\operatorname {OPT} }})}n^{O(1)})}$. है।

मजबूत घातीय समय परिकल्पना बंधे हुए वृक्ष चौड़ाई के ग्राफ़ पर कई ग्राफ़ समस्याओं की पैरामीटरयुक्त जटिलता पर कड़ी सीमाएं लगाती है। विशेष रूप से, यदि मजबूत घातीय समय परिकल्पना सत्य है, तो ग्राफ़ पर स्वतंत्र समुच्चय खोजने के लिए इष्टतम समय सीमा treewidth $w$ is ${\textstyle {\bigl (}2-o(1){\bigr )}^{w}n^{O(1)}}$, है। प्रभावी समुच्चय से जुड़ी समस्या के लिए इसका इष्टतम समय is ${\textstyle {\bigl (}3-o(1){\bigr )}^{w}n^{O(1)}}$, हैं, इस प्रकार अधिकतम कटौती के लिए इष्टतम समय is ${\textstyle {\bigl (}2-o(1){\bigr )}^{w}n^{O(1)}}$, हैं और इसके लिए इष्टतम समय $k$-coloring is ${\textstyle {\bigl (}k-o(1){\bigr )}^{w}n^{O(1)}}$. हैं। इस कारण समान्य रूप से चल रहे इस समय के आधार पर इसमें कोई भी सुधार मजबूत घातीय समय को hypothesis. गलत साबित करेगा। जिसके कारण घातीय समय परिकल्पना का यह भी तात्पर्य है कि इंटरसेक्शन संख्या (ग्राफ सिद्धांत) के लिए किसी भी निश्चित-पैरामीटर ट्रैक्टेबल कलन विधि में डबल घातीय फ़ंक्शन निर्भरता parameter. होनी चाहिए।

संचार जटिलता

संचार जटिलता में तीन-पक्षीय समुच्चय असंबद्धता समस्या में, कुछ में पूर्णांक के तीन उपसमूह range $[1,m]$ निर्दिष्ट हैं, और तीन संचार पक्ष प्रत्येक तीन उपसमूहों में से दो को जानते हैं। इस प्रकार के लक्षित समहों के लिए साझा संचार चैनल पर एक-दूसरे को कम से कम बिट्स संचारित करना है ताकि पक्ष यह निर्धारित कर सके कि तीन समुच्चयों का प्रतिच्छेदन रिक्त है या गैर-रिक्त है। इस प्रकार कम से कम $m$-bit संचार प्रोटोकॉल तीन पार्टियों में से के लिए उस पार्टी को ज्ञात दो समुच्चयों के प्रतिच्छेदन का वर्णन करने वाला बिटवेक्टर संचारित करने के लिए होगा, जिसके बाद शेष दोनों पक्षों में से कोई भी प्रतिच्छेदन की रिक्तता निर्धारित कर सकता है। चूंकि, यदि कोई प्रोटोकॉल उपस्थित है जो समस्या का समाधान करता है $o(m)$ communication और $2^{o(m)}$ computation, इसे हल करने के लिए कलन विधि में परिवर्तित किया जा सकता है, जिसके आधार पर $k$-SAT में time $O(1.74^{n})$किसी भी निश्चित के लिए constant $k$, मजबूत घातीय समय परिकल्पना का उल्लंघन हैं। इसलिए यहाँ पर मजबूत घातीय समय परिकल्पना का तात्पर्य या तो यह है कि तीन-पक्षीय समुच्चय असंबद्धता के लिए तुच्छ प्रोटोकॉल इष्टतम है, या किसी भी उत्तम प्रोटोकॉल के लिए घातीय मात्रा computation. की आवश्यकता होती है।

संरचनात्मक जटिलता

यदि घातीय समय परिकल्पना सत्य है, तो 3-SAT में बहुपद समय कलन नहीं होगा, और इसलिए यह P व NP के बीच का अन्तर के लिए P ≠ NP इस समस्या का अनुसरण करेगा। इस प्रकार इसकी अधिक मजबूती से, इस स्थिति में, 3-SAT में अर्ध-बहुपद समय कलन भी नहीं हो सकता है, इसलिए NP, QP का सबसमुच्चय नहीं हो सकता है। चूंकि, यदि घातीय समय परिकल्पना विफल हो जाती है, तो इसका पी बनाम NP समस्या पर कोई प्रभाव नहीं पड़ेगा। इस प्रकार पैडिंग तर्क NP-पूर्ण समस्याओं के समय इसको प्रमाणित किया जाता है, जिसके लिए सबसे प्रसिद्ध रनिंग टाइम ${\textstyle O(2^{n^{c}})}$ for $c<1$, का रूप होता है, और यदि 3-SAT के लिए सर्वोत्तम संभव चलने का समय इस रूप में होता, तो P, NP के बराबर नहीं होता, क्योंकि 3-SAT NP-पूर्ण है और यह समय सीमा बहुपद नहीं है, अपितु घातीय समय परिकल्पना असत्य होगी।

पैरामीटरयुक्त जटिलता सिद्धांत में, क्योंकि घातीय समय परिकल्पना का तात्पर्य है कि अधिकतम क्लिक के लिए निश्चित-पैरामीटर-ट्रैक्टेबल कलन विधि उपस्थित नहीं है, इसका यह भी तात्पर्य है कि W[1] ≠ FPT. यह इस क्षेत्र में महत्वपूर्ण खुली समस्या है कि क्या इस निहितार्थ को व्युत्क्रम किया जा सकता है: इस प्रकार W[1] ≠ FPTघातांकीय समय परिकल्पना का तात्पर्य हैं कि इसके लिए मानकीकृत जटिलता वर्गों का पदानुक्रम है जिसे एम-पदानुक्रम कहा जाता है जो डब्ल्यू-पदानुक्रम को इस अर्थ में जोड़ता है कि, all $i$, ${\mathsf {M}}[i]\subseteq {\mathsf {W}}[i]\subseteq {\mathsf {M}}[i+1]$; इस प्रकार उदाहरण के लिए, आकार का शीर्ष कवर ढूंढने की समस्या $k\log n$ में $n$-vertex ग्राफ़ के साथ parameter $k$ तैयार है, जिसके आधार पर for M[1].घातांकीय समय परिकल्पना उस कथन के समतुल्य है, जिसका मान M[1] ≠ FPT, और क्या का प्रश्न ${\mathsf {M}}[i]\subseteq {\mathsf {W}}[i]$ के लिए $i>1$ E also open. हैं।

मजबूत घातीय समय परिकल्पना की भिन्नता की विफलता से लेकर जटिलता वर्गों के पृथक्करण तक, दूसरी दिशा में निहितार्थ साबित करना भी संभव है। जैसा यहां पर विलियम्स (2010) प्रदर्शित करते हैं कि क्या कोई कलन विधि उपस्थित है, जो $A$ समय में बूलियन परिपथ संतुष्टि $2^{n}/f(n)$ को हल करता है, इस प्रकार यहाँ पर कुछ सुपरबहुपद वृद्धि के लिए function $f$, तो नेक्स्प समय P/poly का उपसमुच्चय नहीं है। इस प्रकार विलियम्स दिखाता है कि, यदि कलन विधि $A$ उपस्थित है, और P/Poly में नेक्स्प समय का अनुकरण करने वाले परिपथ का समूह भी उपस्थित है, फिर कलन विधि $A$ समय पदानुक्रम प्रमेय का उल्लंघन करते हुए, कम समय में NEXPTIME समस्याओं को अनैतिक रूप से अनुकरण करने के लिए परिपथ के साथ बनाया जा सकता है। इसलिए, कलन विधि का अस्तित्व $A$ परिपथ के परिवार की गैर-उपस्थितगी और इन दोनों जटिलताओं के अलग होने को classes. द्वारा प्रमाणित करता है।

यह भी देखें

• सैविच का प्रमेय, दर्शाता है कि समान घातीय अंतर अंतरिक्ष जटिलता के लिए नहीं टिक सकता हैं।

अग्रिम पठन

• Dantsin, Evgeny; Wolpert, Alexander (2010), "On moderately exponential time for SAT", Theory and Applications of Satisfiability Testing–SAT 2010, Lecture Notes in Computer Science, vol. 6175, Springer-Verlag, pp. 313–325, doi:10.1007/978-3-642-14186-7_27, ISBN 978-3-642-14185-0