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

कम्प्यूटेशनल जटिलता सिद्धांत में, घातीय समय परिकल्पना अप्रमाणित कम्प्यूटेशनल कठोरता धारणा है जिसे तैयार किया गया था Impagliazzo & Paturi (1999). इसमें कहा गया है कि 3-SAT|3-CNF बूलियन फ़ार्मुलों की संतुष्टि को उप-घातांकीय समय में हल नहीं किया जा सकता है, अर्थात, $2^{(1-\epsilon )n}$ सभी स्थिरांक के लिए $\epsilon >0$, जहां n सूत्र में चरों की संख्या है। घातीय समय परिकल्पना, यदि सत्य है, तो इसका अर्थ यह होगा कि पी बनाम एनपी समस्या|पी ≠ एनपी, लेकिन यह मजबूत कथन है। इसका तात्पर्य यह है कि कई कम्प्यूटेशनल समस्याएं जटिलता में समतुल्य हैं, इस अर्थ में कि यदि उनमें से के पास उप-घातीय समय एल्गोरिदम है तो वे सभी करते हैं, और इन समस्याओं के लिए कई ज्ञात एल्गोरिदम में इष्टतम या निकट-इष्टतम समय होता है 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$: जैसा Impagliazzo, Paturi & Zane (2001)दिखाया, स्थिरांक मौजूद है $\alpha$ ऐसा that $s_{k}\leq s_{\infty }(1-\alpha /k)$. इसलिए, यदि घातांकीय समय परिकल्पना सत्य है, तो इसके अनंत रूप से कई मान होने चाहिए $k$ जिसके लिए $s_{k}$ अलग है from $s_{k+1}$.

इस क्षेत्र में महत्वपूर्ण उपकरण स्पार्सिफिकेशन लेम्मा है Impagliazzo, Paturi & Zane (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.

अन्य खोज समस्याएँ

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

यदि बहुपद समय में समूह या लघुगणकीय आकार के स्वतंत्र सेट पाए जा सकते हैं, तो घातीय समय परिकल्पना झूठी होगी। इसलिए, भले ही ऐसे छोटे आकार के समूह या स्वतंत्र सेट ढूंढना एनपी-पूर्ण होने की संभावना नहीं है, घातीय समय परिकल्पना का तात्पर्य है कि ये समस्याएं हैं 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 का सबसेट नहीं हो सकता है। हालाँकि, यदि घातीय समय परिकल्पना विफल हो जाती है, तो इसका पी बनाम एनपी समस्या पर कोई प्रभाव नहीं पड़ेगा। पैडिंग तर्क एनपी-पूर्ण समस्याओं के अस्तित्व को साबित करता है जिसके लिए सबसे प्रसिद्ध रनिंग टाइम का रूप होता है ${\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$ ई आल्सो open.

मजबूत घातीय समय परिकल्पना की भिन्नता की विफलता से लेकर जटिलता वर्गों के पृथक्करण तक, दूसरी दिशा में निहितार्थ साबित करना भी संभव है। जैसा Williams (2010) दिखाता है, कि क्या कोई एल्गोरिदम मौजूद है $A$ जो समय में बूलियन सर्किट संतुष्टि को हल करता है $2^{n}/f(n)$ कुछ सुपरबहुपद वृद्धि के लिए function $f$, तो NEXPTIME P/poly का उपसमुच्चय नहीं है। विलियम्स दिखाता है कि, यदि एल्गोरिदम $A$ मौजूद है, और पी/पॉली में NEXPTIME का अनुकरण करने वाले सर्किट का परिवार भी मौजूद है, फिर एल्गोरिदम $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