घातीय समय परिकल्पना: Difference between revisions

Revision as of 00:29, 4 July 2023

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

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

परिभाषा

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

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

जहाँ

n

दिए गए चरों की संख्या है

k

-SAT instance.^[2] प्रत्येक के लिए 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.^[1] है।

कुछ स्रोत घातीय समय परिकल्पना को थोड़ा कमजोर कथन के रूप में परिभाषित करते हैं, जिसमें 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] नहीं चल रहा हो। जिसके कारण किसी घातीय समय परिकल्पना का संबंधित संस्करण गैर-समान घातीय समय परिकल्पना है, जो बताता है कि कलन विधि का कोई परिवार नहीं है, इस प्रकार इनपुट की प्रत्येक लंबाई के लिए, जटिलता की भावना उत्पन्न होती हैं जिसके 3- को हल कर सकता है, जिसके आधार पर time $2^{o(n)}$ .^[4] मान प्राप्त किया जा सकता हैं।

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

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

इसकी सबसे शक्तिशाली घातांकीय समय परिकल्पना (SETH) है जिसका अनुमानतः मान that

s_{\infty }=1

.^[5] है।

निहितार्थ

संतुष्टि

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

इस क्षेत्र में महत्वपूर्ण उपकरण स्पार्सिफिकेशन लेम्मा है, जो इम्पाग्लिआज़ो, पाटुरी & जेन (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.^[7]^[6] होगी।

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

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

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

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

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

मजबूत घातीय समय परिकल्पना बंधे हुए वृक्ष चौड़ाई के ग्राफ़ पर कई ग्राफ़ समस्याओं की पैरामीटरयुक्त जटिलता पर कड़ी सीमाएं लगाती है। विशेष रूप से, यदि मजबूत घातीय समय परिकल्पना सत्य है, तो ग्राफ़ पर स्वतंत्र समुच्चय खोजने के लिए इष्टतम समय सीमा 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)}}$ .^[12] हैं। इस कारण समान्य रूप से चल रहे इस समय के आधार पर इसमें कोई भी सुधार मजबूत घातीय समय को hypothesis.^[13] गलत साबित करेगा। जिसके कारण घातीय समय परिकल्पना का यह भी तात्पर्य है कि इंटरसेक्शन संख्या (ग्राफ सिद्धांत) के लिए किसी भी निश्चित-पैरामीटर ट्रैक्टेबल कलन विधि में डबल घातीय फ़ंक्शन निर्भरता parameter.^[14] होनी चाहिए।

संचार जटिलता

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

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

यदि घातीय समय परिकल्पना सत्य है, तो 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.^[10] यह इस क्षेत्र में महत्वपूर्ण खुली समस्या है कि क्या इस निहितार्थ को व्युत्क्रम किया जा सकता है: इस प्रकार 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.^[3] हैं।

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

यह भी देखें

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

↑ ^1.0 ^1.1 Impagliazzo, Russell; Paturi, Ramamohan (1999), "The Complexity of k-SAT", Proc. 14th IEEE Conf. on Computational Complexity, pp. 237–240, doi:10.1109/CCC.1999.766282, ISBN 978-0-7695-0075-1
↑ Schöning, Uwe (1999), "A probabilistic algorithm for $k$ -SAT and constraint satisfaction problems", 40th Annual Symposium on Foundations of Computer Science, FOCS '99, 17-18 October, 1999, New York, NY, USA, IEEE Computer Society, pp. 410–414, doi:10.1109/SFFCS.1999.814612
↑ ^3.0 ^3.1 Flum, Jörg; Grohe, Martin (2006), "16. Subexponential Fixed-Parameter Tractability", Parameterized Complexity Theory, EATCS Texts in Theoretical Computer Science, Springer-Verlag, pp. 417–451, ISBN 978-3-540-29952-3
↑ Chen, Yijia; Eickmeyer, Kord; Flum, Jörg (2012), "The exponential time hypothesis and the parameterized clique problem", in Thilikos, Dimitrios M.; Woeginger, Gerhard J. (eds.), Parameterized and Exact Computation – 7th International Symposium, IPEC 2012, Ljubljana, Slovenia, September 12–14, 2012, Proceedings, Lecture टिप्पणियाँ in Computer Science, vol. 7535, Springer, pp. 13–24, doi:10.1007/978-3-642-33293-7_4
↑ Calabro, Chris; Impagliazzo, Russel; Paturi, Ramamohan (2009), "The Complexity of Satisfiability of Small Depth Circuits", Parameterized and Exact Computation, 4th International Workshop, IWPEC 2009, Copenhagen, Denmark, September 10-11, 2009, Revised Selected Papers, Lecture टिप्पणियाँ in Computer Science, vol. 5917, pp. 75–85, doi:10.1007/978-3-642-11269-0_6
↑ ^6.0 ^6.1 ^6.2 Impagliazzo, Russell; Paturi, Ramamohan; Zane, Francis (2001), "Which problems have strongly exponential complexity?", Journal of Computer and System Sciences, 63 (4): 512–530, CiteSeerX 10.1.1.66.3717, doi:10.1006/jcss.2001.1774
↑ ^7.0 ^7.1 ^7.2 Woeginger, Gerhard (2003), "Exact algorithms for NP-hard problems: A survey", Combinatorial Optimization — Eureka, You Shrink! (PDF), Lecture टिप्पणियाँ in Computer Science, vol. 2570, Springer-Verlag, pp. 185–207, CiteSeerX 10.1.1.168.5383, doi:10.1007/3-540-36478-1_17, ISBN 978-3-540-00580-3
↑ ^8.0 ^8.1 ^8.2 Pătraşcu, Mihai; Williams, Ryan (2010), "On the possibility of faster SAT algorithms", Proc. 21st ACM/SIAM Symposium on Discrete Algorithms (SODA 2010) (PDF), pp. 1065–1075
↑ Feige, Uriel; Kilian, Joe (1997), "On limited versus polynomial nondeterminism", Chicago Journal of Theoretical Computer Science, 1: 1–20, doi:10.4086/cjtcs.1997.001
↑ ^10.0 ^10.1 Chen, Jianer; Huang, Xiuzhen; Kanj, Iyad A.; Xia, Ge (2006), "Strong computational lower bounds via parameterized complexity", Journal of Computer and System Sciences, 72 (8): 1346–1367, doi:10.1016/j.jcss.2006.04.007
↑ Karpinski, Marek; Schudy, Warren (2010), "Faster Algorithms for Feedback Arc Set Tournament, Kemeny Rank Aggregation and Betweenness Tournament", Proc. ISAAC 2010, Part I, Lecture टिप्पणियाँ in Computer Science, 6506: 3–14, arXiv:1006.4396, doi:10.1007/978-3-642-17517-6_3, ISBN 978-3-642-17516-9
↑ 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
↑ Lokshtanov, Daniel; Marx, Dániel; Saurabh, Saket (2011), "Known algorithms on graphs of bounded treewidth are probably optimal", Proc. 22nd ACM/SIAM Symposium on Discrete Algorithms (SODA 2011), pp. 777–789, arXiv:1007.5450, doi:10.1137/1.9781611973082.61
↑ Cygan, Marek; Pilipczuk, Marcin; Pilipczuk, Michał (2016), "Known algorithms for edge clique cover are probably optimal", SIAM Journal on Computing, 45 (1): 67–83, arXiv:1203.1754, doi:10.1137/130947076, MR 3448348
↑ Williams, Ryan (2010), "Improving exhaustive search implies superpolynomial lower bounds", Proc. 42nd ACM Symposium on Theory of Computing (STOC 2010), New York, NY, USA: ACM, pp. 231–240, CiteSeerX 10.1.1.216.1299, doi:10.1145/1806689.1806723, ISBN 9781450300506

अग्रिम पठन

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

[ip99-1] 1.0 ^1.1 Impagliazzo, Russell; Paturi, Ramamohan (1999), "The Complexity of k-SAT", Proc. 14th IEEE Conf. on Computational Complexity, pp. 237–240, doi:10.1109/CCC.1999.766282, ISBN 978-0-7695-0075-1

[s99-2] Schöning, Uwe (1999), "A probabilistic algorithm for $k$ -SAT and constraint satisfaction problems", 40th Annual Symposium on Foundations of Computer Science, FOCS '99, 17-18 October, 1999, New York, NY, USA, IEEE Computer Society, pp. 410–414, doi:10.1109/SFFCS.1999.814612

[fg-3] 3.0 ^3.1 Flum, Jörg; Grohe, Martin (2006), "16. Subexponential Fixed-Parameter Tractability", Parameterized Complexity Theory, EATCS Texts in Theoretical Computer Science, Springer-Verlag, pp. 417–451, ISBN 978-3-540-29952-3

[cef-4] Chen, Yijia; Eickmeyer, Kord; Flum, Jörg (2012), "The exponential time hypothesis and the parameterized clique problem", in Thilikos, Dimitrios M.; Woeginger, Gerhard J. (eds.), Parameterized and Exact Computation – 7th International Symposium, IPEC 2012, Ljubljana, Slovenia, September 12–14, 2012, Proceedings, Lecture टिप्पणियाँ in Computer Science, vol. 7535, Springer, pp. 13–24, doi:10.1007/978-3-642-33293-7_4

[cip-5] Calabro, Chris; Impagliazzo, Russel; Paturi, Ramamohan (2009), "The Complexity of Satisfiability of Small Depth Circuits", Parameterized and Exact Computation, 4th International Workshop, IWPEC 2009, Copenhagen, Denmark, September 10-11, 2009, Revised Selected Papers, Lecture टिप्पणियाँ in Computer Science, vol. 5917, pp. 75–85, doi:10.1007/978-3-642-11269-0_6

[ipz01-6] 6.0 ^6.1 ^6.2 Impagliazzo, Russell; Paturi, Ramamohan; Zane, Francis (2001), "Which problems have strongly exponential complexity?", Journal of Computer and System Sciences, 63 (4): 512–530, CiteSeerX 10.1.1.66.3717, doi:10.1006/jcss.2001.1774

[w03-7] 7.0 ^7.1 ^7.2 Woeginger, Gerhard (2003), "Exact algorithms for NP-hard problems: A survey", Combinatorial Optimization — Eureka, You Shrink! (PDF), Lecture टिप्पणियाँ in Computer Science, vol. 2570, Springer-Verlag, pp. 185–207, CiteSeerX 10.1.1.168.5383, doi:10.1007/3-540-36478-1_17, ISBN 978-3-540-00580-3

[pw10-8] 8.0 ^8.1 ^8.2 Pătraşcu, Mihai; Williams, Ryan (2010), "On the possibility of faster SAT algorithms", Proc. 21st ACM/SIAM Symposium on Discrete Algorithms (SODA 2010) (PDF), pp. 1065–1075

[fk-9] Feige, Uriel; Kilian, Joe (1997), "On limited versus polynomial nondeterminism", Chicago Journal of Theoretical Computer Science, 1: 1–20, doi:10.4086/cjtcs.1997.001

[chkx-10] 10.0 ^10.1 Chen, Jianer; Huang, Xiuzhen; Kanj, Iyad A.; Xia, Ge (2006), "Strong computational lower bounds via parameterized complexity", Journal of Computer and System Sciences, 72 (8): 1346–1367, doi:10.1016/j.jcss.2006.04.007

[ks-11] Karpinski, Marek; Schudy, Warren (2010), "Faster Algorithms for Feedback Arc Set Tournament, Kemeny Rank Aggregation and Betweenness Tournament", Proc. ISAAC 2010, Part I, Lecture टिप्पणियाँ in Computer Science, 6506: 3–14, arXiv:1006.4396, doi:10.1007/978-3-642-17517-6_3, ISBN 978-3-642-17516-9

[cfk-12] 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

[lms-13] Lokshtanov, Daniel; Marx, Dániel; Saurabh, Saket (2011), "Known algorithms on graphs of bounded treewidth are probably optimal", Proc. 22nd ACM/SIAM Symposium on Discrete Algorithms (SODA 2011), pp. 777–789, arXiv:1007.5450, doi:10.1137/1.9781611973082.61

[cpp-14] Cygan, Marek; Pilipczuk, Marcin; Pilipczuk, Michał (2016), "Known algorithms for edge clique cover are probably optimal", SIAM Journal on Computing, 45 (1): 67–83, arXiv:1203.1754, doi:10.1137/130947076, MR 3448348

[w10-15] Williams, Ryan (2010), "Improving exhaustive search implies superpolynomial lower bounds", Proc. 42nd ACM Symposium on Theory of Computing (STOC 2010), New York, NY, USA: ACM, pp. 231–240, CiteSeerX 10.1.1.216.1299, doi:10.1145/1806689.1806723, ISBN 9781450300506

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

@@ Line 1: / Line 1: @@
 {{short description|Unproven computational hardness assumption}}
-[[कम्प्यूटेशनल जटिलता सिद्धांत]] में, घातीय समय परिकल्पना अप्रमाणित [[कम्प्यूटेशनल कठोरता धारणा]] है जिसे तैयार किया गया था {{harvtxt|Impagliazzo|Paturi|1999}}. इसमें कहा गया है कि [[3-SAT]]|3-CNF बूलियन फ़ार्मुलों की संतुष्टि को उप-घातांकीय समय में हल नहीं किया जा सकता है, अर्थात, <math>2^{(1-\epsilon) n}</math> सभी स्थिरांक के लिए <math>\epsilon > 0</math>, जहां n सूत्र में चरों की संख्या है।
+[[कम्प्यूटेशनल जटिलता सिद्धांत|कम्प्यूटरीकृत जटिलता सिद्धांत]] में, '''घातीय समय परिकल्पना''' अप्रमाणित [[कम्प्यूटेशनल कठोरता धारणा|कम्प्यूटरीकृत कठोरता की धारणा]] है, जिसे {{harvtxt|इम्पाग्लिआज़ो|पाटुरी|1999}} द्वारा तैयार किया गया था, इसमें कहा गया है कि [[3-SAT]] या 3-CNF बूलियन फ़ार्मुलों की संतुष्टि को उप-घातांकीय समय में हल नहीं किया जा सकता है, अर्थात, <math>2^{(1-\epsilon) n}</math> सभी स्थिरांक के लिए <math>\epsilon > 0</math>, जहां n सूत्र में चरों की संख्या को प्रदर्शित करता है।
-घातीय समय परिकल्पना, यदि सत्य है, तो इसका अर्थ यह होगा कि पी बनाम एनपी समस्या|पी ≠ एनपी, लेकिन यह मजबूत कथन है। इसका तात्पर्य यह है कि कई कम्प्यूटेशनल समस्याएं जटिलता में समतुल्य हैं, इस अर्थ में कि यदि उनमें से के पास उप-घातीय समय एल्गोरिदम है तो वे सभी करते हैं, और इन समस्याओं के लिए कई ज्ञात एल्गोरिदम में इष्टतम या निकट-इष्टतम समय होता है {{nowrap|complexity.{{r|ip99}}}}
-==परिभाषा== {{nowrap|<math>k</math>-SAT}एटी}} समस्या [[बूलियन संतुष्टि समस्या]] का संस्करण है जिसमें समस्या का इनपुट [[संयोजक सामान्य रूप]] में [[बूलियन अभिव्यक्ति]] है (यानी, चर और उनके निषेधों का और अन्य) अधिकतम के साथ <math>k</math> प्रति खंड चर. लक्ष्य यह निर्धारित करना है कि क्या इस अभिव्यक्ति को इसके चरों के लिए बूलियन मानों के कुछ असाइनमेंट द्वारा सत्य बनाया जा सकता है। [[2-संतोषजनकता]]|2-SAT में [[रैखिक समय]] एल्गोरिदम है, लेकिन सभी ज्ञात एल्गोरिदम बड़े हैं <math>k</math> घातीय फलन के आधार पर निर्भर करते हुए, घातांकीय समय लें <math>k</math>. उदाहरण के लिए, [[वॉकसैट]] संभाव्य एल्गोरिदम हल कर सकता है {{nowrap|<math>k</math>-SAT}} औसत समय में <math display=block>\left(2-\frac2k\right)^n n^{O(1)},</math> कहाँ <math>n</math> दिए गए चरों की संख्या है {{nowrap|<math>k</math>-SAT}} {{nowrap|instance.{{r|s99}}}} प्रत्येक के लिए {{nowrap|integer <math>k\ge 3</math>,}} परिभाषित करना <math>s_k</math> ऐसी सबसे छोटी संख्या होना {{nowrap|<math>k</math>-SAT}}में हल किया जा सकता है {{nowrap|time <math>2^{s_k n+o(n)}</math>.}} यह न्यूनतम अस्तित्व में नहीं हो सकता है, यदि बेहतर और बेहतर एल्गोरिदम के अनुक्रम में उनकी समय सीमा में तदनुसार छोटी घातीय वृद्धि होती है; उस स्थिति में, परिभाषित करें <math>s_k</math> वास्तविक संख्याओं का न्यूनतम होना <math>\delta</math> जिसके लिए {{nowrap|<math>k</math>-SAT}}में हल किया जा सकता है {{nowrap|time <math>O(2^{\delta n})</math>.}} क्योंकि बड़ी समस्याओं के साथ <math>k</math> इससे आसान नहीं हो सकता, इन नंबरों को इस प्रकार क्रमबद्ध किया गया है {{nowrap|<math>s_3\le s_4\le \cdots</math>,}} और वॉकसैट के कारण वे अधिकतम हैं <math display=block>s_k\le \log_2 \left(2-\frac2k\right)<1.</math> घातीय समय परिकल्पना यह [[अनुमान]] है कि वे सभी गैर-शून्य हैं, या समकक्ष रूप से, उनमें से सबसे छोटा, {{nowrap|<math>s_3</math>,}} है {{nowrap|nonzero.{{r|ip99}}}}
+घातीय समय परिकल्पना, यदि सत्य है, तो इसका अर्थ यह होगा कि P तथा NP के बीच का अन्तर इसकी समस्या या P ≠ NP को प्रदर्शित करता हैं, अपितु यह मुख्य रूप से मजबूत कथन है। इसका तात्पर्य यह है कि कई कम्प्यूटरीकृत समस्याएं जटिलता में समतुल्य हैं, इस अर्थ में कि यदि उनमें से के पास उप-घातीय समय कलन विधि है तो वे सभी करते हैं, और इन समस्याओं के लिए कई ज्ञात कलन विधि में इष्टतम या निकट-इष्टतम समय {{nowrap|complexity.{{r|ip99}}}} होता है।
-कुछ स्रोत घातीय समय परिकल्पना को थोड़ा कमजोर कथन के रूप में परिभाषित करते हैं जिसमें 3-SAT को हल नहीं किया जा सकता है {{nowrap|time <math>2^{o(n)}</math>.}} यदि 3-SAT को हल करने के लिए कोई एल्गोरिदम मौजूद है {{nowrap|time <math>2^{o(n)}</math>,}} तब <math>s_3</math> शून्य के बराबर होगा. हालाँकि, यह वर्तमान ज्ञान के अनुरूप है कि 3-SAT एल्गोरिदम का क्रम हो सकता है, प्रत्येक का चलने का समय <math>O(2^{\delta_i n})</math> संख्याओं के अनुक्रम के लिए <math>\delta_i</math> शून्य की ओर रुझान, लेकिन जहां इन एल्गोरिदम का विवरण इतनी तेज़ी से बढ़ रहा है कि भी एल्गोरिदम स्वचालित रूप से सबसे उपयुक्त का चयन और चला नहीं सकता है। अगर ऐसा ही होता तो <math>s_3</math> शून्य के बराबर होगा, भले ही कोई एकल एल्गोरिदम नहीं चल रहा हो {{nowrap|time <math>2^{o(n)}</math>.{{r|fg}}}} घातीय समय परिकल्पना का संबंधित संस्करण गैर-समान घातीय समय परिकल्पना है, जो बताता है कि एल्गोरिदम का कोई परिवार नहीं है (इनपुट की प्रत्येक लंबाई के लिए, [[सलाह (जटिलता)]] की भावना में) जो 3- को हल कर सकता है में बैठ गया {{nowrap|time <math>2^{o(n)}</math>.{{r|cef}}}}
+== परिभाषा ==
-क्योंकि संख्याएँ <math>s_3,s_4,\dots</math> एकरसता का निर्माण करें जो ऊपर से बंधी हो, उन्हें सीमा तक अभिसरण करना होगा <math display=block>s_\infty=\lim_{k\to\infty} s_k.</math> मजबूत घातांकीय समय परिकल्पना (SETH) अनुमान है {{nowrap|that <math>s_\infty=1</math>.{{r|cip}}}}
+{{nowrap|<math>k</math>-SAT}एटी}} समस्या [[बूलियन संतुष्टि समस्या]] का ऐसा संस्करण है जिसमें समस्या का इनपुट [[संयोजक सामान्य रूप]] में [[बूलियन अभिव्यक्ति]] को प्रदर्शित करता है, अर्ताथ चर और उनके निषेधों का और अन्य अधिकतम के साथ <math>k</math> प्रति खंड चर. लक्ष्य यह निर्धारित करता है, यह इस प्रकार हैं कि क्या इस अभिव्यक्ति को इसके चरों के लिए बूलियन मानों के कुछ असाइनमेंट द्वारा सत्य बनाया जा सकता है। इसके आधार पर [[2-संतोषजनकता]] या 2-SAT में [[रैखिक समय]] कलन विधि को प्रदर्शित करता है, अपितु सभी ज्ञात कलन विधि बड़े हैं, जिसके कारण <math>k</math> घातीय फलन के आधार पर निर्भर करते हुए, घातांकीय समय लें <math>k</math>. उदाहरण के लिए, [[वॉकसैट]] संभाव्य कलन विधि हल कर सकता है, इस प्रकार {{nowrap|<math>k</math>-SAT}} के औसत समय में<math display="block">\left(2-\frac2k\right)^n n^{O(1)},</math>जहाँ <math>n</math> दिए गए चरों की संख्या है {{nowrap|<math>k</math>-SAT}} {{nowrap|instance.{{r|s99}}}} प्रत्येक के लिए {{nowrap|integer <math>k\ge 3</math>,}} के लिए <math>s_k</math> को परिभाषित करता हैं। इस प्रकार ऐसी सबसे छोटी संख्या को {{nowrap|<math>k</math>-SAT}} द्वारा हल किया जा सकता है, इसके आधारा पर {{nowrap|time <math>2^{s_k n+o(n)}</math>.}} जो न्यूनतम समय में नहीं हो सकता है, यदि इसके लिए उपयुक्त उत्तम कलन विधि के अनुक्रम में उनकी समय सीमा में तदनुसार छोटी घातीय वृद्धि होती है, इस स्थिति में, परिभाषित करें <math>s_k</math> वास्तविक संख्याओं का न्यूनतम रहता हैं। जिसके कारण <math>\delta</math> हैं, जिसके लिए {{nowrap|<math>k</math>-SAT}}में हल किया जा सकता है, इस प्रकार {{nowrap|time <math>O(2^{\delta n})</math>.}} क्योंकि बड़ी समस्याओं के साथ <math>k</math> इससे सरल नहीं हो सकता हैं, इस प्रकार उपयुक्त संख्या को इस प्रकार क्रमबद्ध किया गया है कि {{nowrap|<math>s_3\le s_4\le \cdots</math>,}} और वॉकसैट के कारण इसका मान अधिकतम हैं जो इस प्रकार हैं-
+<math display="block">s_k\le \log_2 \left(2-\frac2k\right)<1.</math>घातीय समय परिकल्पना यह [[अनुमान]] है कि वे सभी गैर-शून्य हैं, या समकक्ष रूप से, उनमें से सबसे छोटा, {{nowrap|<math>s_3</math>,}} {{nowrap|nonzero.{{r|ip99}}}} है।
+कुछ स्रोत घातीय समय परिकल्पना को थोड़ा कमजोर कथन के रूप में परिभाषित करते हैं, जिसमें 3-SAT को {{nowrap|time <math>2^{o(n)}</math>.}} के लिए हल नहीं किया जा सकता है, इस कारण यदि 3-SAT को हल करने के लिए कोई कलन विधि उपस्थित है, जिसके कारण {{nowrap|time <math>2^{o(n)}</math>,}} तब <math>s_3</math> शून्य के बराबर होगा, चूंकि, यह वर्तमान मान के लिए इस प्रकार अनुरूप है कि 3-SAT कलन विधि का क्रम हो सकता है, प्रत्येक का चलने का समय <math>O(2^{\delta_i n})</math> संख्याओं के अनुक्रम के लिए <math>\delta_i</math> शून्य की ओर यह मान प्रदर्शित करता हैं। अपितु जहां इन कलन विधि का विवरण इतनी तेज़ी से बढ़ रहा है कि भी कलन विधि स्वचालित रूप से सबसे उपयुक्त का चयन और चला नहीं सकता है। अगर ऐसा ही होता तो <math>s_3</math> शून्य के बराबर होगा, भले ही कोई एकल कलन विधि {{nowrap|time <math>2^{o(n)}</math>.{{r|fg}}}} नहीं चल रहा हो। जिसके कारण किसी घातीय समय परिकल्पना का संबंधित संस्करण गैर-समान घातीय समय परिकल्पना है, जो बताता है कि कलन विधि का कोई परिवार नहीं है, इस प्रकार इनपुट की प्रत्येक लंबाई के लिए, [[सलाह (जटिलता)|जटिलता]] की भावना उत्पन्न होती हैं जिसके 3- को हल कर सकता है, जिसके आधार पर {{nowrap|time <math>2^{o(n)}</math>.{{r|cef}}}} मान प्राप्त किया जा सकता हैं।
+क्योंकि संख्याएँ <math>s_3,s_4,\dots</math> एकरसता का निर्माण करें जो ऊपर से बंधी रहती हैं, उन्हें सीमा तक अभिसरण करना होगा।<math display="block">s_\infty=\lim_{k\to\infty} s_k.</math>इसकी सबसे शक्तिशाली घातांकीय समय परिकल्पना (SETH) है जिसका अनुमानतः मान  {{nowrap|that <math>s_\infty=1</math>.{{r|cip}}}} है।
 ==निहितार्थ==
 ===संतुष्टि===
-के लिए यह संभव नहीं है <math>s_k</math> बराबर करने के लिए <math>s_\infty</math> किसी के लिए {{nowrap|finite <math>k</math>:}} जैसा {{harvtxt|Impagliazzo|Paturi|Zane|2001}}दिखाया, स्थिरांक मौजूद है <math>\alpha</math> ऐसा {{nowrap|that <math>s_k\le s_\infty(1-\alpha/k)</math>.}} इसलिए, यदि घातांकीय समय परिकल्पना सत्य है, तो इसके अनंत रूप से कई मान होने चाहिए <math>k</math> जिसके लिए <math>s_k</math> अलग है {{nowrap|from <math>s_{k+1}</math>.{{r|ipz01}}}}
+इसके लिए यह संभव नहीं है <math>s_k</math> बराबर करने के लिए <math>s_\infty</math> को किसी {{nowrap|finite <math>k</math>:}} के लिए जैसे {{harvtxt|इम्पाग्लिआज़ो|पाटुरी|जेन|2001}} द्वारा दिखाया गया हैं कि इसके लिए <math>\alpha</math> स्थिरांक उपस्थित है, जो इस प्रकार हैं कि {{nowrap|that <math>s_k\le s_\infty(1-\alpha/k)</math>.}} मान प्राप्त होता हैं। इसलिए, यदि घातांकीय समय परिकल्पना सत्य है, तो इसके अनंत रूप से कई मान होने चाहिए <math>k</math> जिसके लिए <math>s_k</math> अलग होगी जिसका मान {{nowrap|from <math>s_{k+1}</math>.{{r|ipz01}}}} प्राप्त होता है।
-इस क्षेत्र में महत्वपूर्ण उपकरण स्पार्सिफिकेशन लेम्मा है {{harvtxt|Impagliazzo|Paturi|Zane|2001}}, जो दर्शाता है कि, के लिए {{nowrap|every <math>\varepsilon>0</math>,}} कोई {{nowrap|<math>k</math>-CNF}} सूत्र द्वारा प्रतिस्थापित किया जा सकता है <math>O(2^{\varepsilon n})</math> सरल {{nowrap|<math>k</math>-CNF}} ऐसे सूत्र जिनमें प्रत्येक चर केवल स्थिर संख्या में ही प्रकट होता है, और इसलिए जिसमें उपवाक्यों की संख्या रैखिक होती है। स्पार्सिफिकेशन लेम्मा को किसी दिए गए सूत्र में गैर-रिक्त सामान्य प्रतिच्छेदन वाले खंडों के बड़े सेटों को बार-बार ढूंढकर और सूत्र को दो सरल सूत्रों द्वारा प्रतिस्थापित करके सिद्ध किया जाता है, जिनमें से प्रत्येक खंड को उनके सामान्य प्रतिच्छेदन द्वारा प्रतिस्थापित किया जाता है और दूसरे में प्रत्येक खंड से प्रतिच्छेदन हटा दिया गया है। स्पार्सिफिकेशन लेम्मा को लागू करके और फिर खंडों को विभाजित करने के लिए नए चर का उपयोग करके, कोई व्यक्ति सेट प्राप्त कर सकता है <math>O(2^{\varepsilon n})</math> 3-सीएनएफ सूत्र, प्रत्येक में चर की रैखिक संख्या होती है, जैसे कि मूल {{nowrap|<math>k</math>-CNF}} सूत्र तभी संतोषजनक है जब इन 3-सीएनएफ सूत्रों में से कम से कम संतोषजनक हो। इसलिए, यदि 3-SAT को उप-घातीय समय में हल किया जा सकता है, तो कोई इस कमी का उपयोग हल करने के लिए कर सकता है {{nowrap|<math>k</math>-SAT}} उपघातीय समय में भी। समान रूप से, {{nowrap|if <math>s_k>0</math>}} के लिए {{nowrap|any <math>k>0</math>,}} तब <math>s_3>0</math> साथ ही, और घातीय समय परिकल्पना होगी {{nowrap|true.{{r|w03|ipz01}}}}
+इस क्षेत्र में महत्वपूर्ण उपकरण स्पार्सिफिकेशन लेम्मा है, जो {{harvtxt|इम्पाग्लिआज़ो|पाटुरी|जेन|2001}} के संदर्भ को दर्शाता है कि इसके लिए {{nowrap|every <math>\varepsilon>0</math>,}} कोई {{nowrap|<math>k</math>-CNF}} सूत्र द्वारा प्रतिस्थापित किया जा सकता है, इस प्रकार <math>O(2^{\varepsilon n})</math> सरल {{nowrap|<math>k</math>-CNF}} ऐसे सूत्र जिनमें प्रत्येक चर केवल स्थिर संख्या में ही प्रकट होता है, और इसलिए जिसमें उपवाक्यों की संख्या रैखिक होती है। स्पार्सिफिकेशन लेम्मा को किसी दिए गए सूत्र में गैर-रिक्त सामान्य प्रतिच्छेदन वाले खंडों के बड़े समुच्चयों को बार-बार ढूंढकर और सूत्र को दो सरल सूत्रों द्वारा प्रतिस्थापित करके सिद्ध किया जाता है, जिनमें से प्रत्येक खंड को उनके सामान्य प्रतिच्छेदन द्वारा प्रतिस्थापित किया जाता है और दूसरे में प्रत्येक खंड से प्रतिच्छेदन हटा दिया गया है। स्पार्सिफिकेशन लेम्मा को लागू करके और फिर खंडों को विभाजित करने के लिए नए चर का उपयोग करके, किसी मान के लिए उक्त समुच्चय <math>O(2^{\varepsilon n})</math> प्राप्त कर सकता है, जिसके आधार पर  3-सीएनएफ सूत्र, प्रत्येक में चर की रैखिक संख्या होती है, जैसे कि मूल {{nowrap|<math>k</math>-CNF}} सूत्र तभी संतोषजनक है जब इन 3-सीएनएफ सूत्रों में से कम से कम संतोषजनक हो। इसलिए, यदि 3-SAT को उप-घातीय समय में हल किया जा सकता है, तो {{nowrap|<math>k</math>-SAT}} उपघातीय समय में भी कोई इस कमी का उपयोग हल करने के लिए कर सकता है। समान रूप से, {{nowrap|if <math>s_k>0</math>}} के लिए {{nowrap|any <math>k>0</math>,}} तब <math>s_3>0</math> साथ ही, और घातीय समय परिकल्पना {{nowrap|true.{{r|w03|ipz01}}}} होगी।
-सीमित मूल्य <math>s_\infty</math> संख्याओं के क्रम का <math>s_k</math> अधिकतम बराबर है {{nowrap|to <math>s_{\operatorname{CNF}}</math>,}} कहाँ <math>s_{\operatorname{CNF}}</math> संख्याओं का न्यूनतम है <math>\delta</math> जैसे कि खंड लंबाई सीमा के बिना संयोजक सामान्य रूप सूत्रों की संतुष्टि को हल किया जा सकता है {{nowrap|time <math>O(2^{\delta n})</math>.}} इसलिए, यदि मजबूत घातीय समय परिकल्पना सत्य है, तो सामान्य सीएनएफ संतुष्टि के लिए कोई एल्गोरिदम नहीं होगा जो सभी संभावित [[सत्य असाइनमेंट]] पर क्रूर-बल खोज से काफी तेज है। हालाँकि, यदि मजबूत घातीय समय परिकल्पना विफल हो जाती है, तब भी यह संभव होगा <math>s_{\operatorname{CNF}}</math> बराबर करने के लिए {{nowrap|one.{{r|pw10}}}}
+इसके आधार पर सीमित मूल्य <math>s_\infty</math> संख्याओं के क्रम का <math>s_k</math> अधिकतम बराबर है, जिसका मान {{nowrap|to <math>s_{\operatorname{CNF}}</math>,}} प्राप्त होता हैं जहाँ <math>s_{\operatorname{CNF}}</math> संख्याओं का न्यूनतम मान <math>\delta</math> है। इस प्रकार जैसे कि खंड लंबाई सीमा के बिना संयोजक सामान्य रूप सूत्रों की संतुष्टि को {{nowrap|time <math>O(2^{\delta n})</math>.}} द्वारा हल किया जा सकता है, इसलिए, यदि मजबूत घातीय समय परिकल्पना सत्य है, तो सामान्य सीएनएफ संतुष्टि के लिए कोई कलन विधि नहीं होगा जो सभी संभावित [[सत्य असाइनमेंट]] पर क्रूर-बल खोज से अधिक तेज है। चूंकि, यदि मजबूत घातीय समय परिकल्पना विफल हो जाती है, तब भी यह संभव होगा <math>s_{\operatorname{CNF}}</math> बराबर करने के लिए {{nowrap|one.{{r|pw10}}}} मान प्राप्त होता हैं।
-===अन्य खोज समस्याएँ===
+===अन्य परिकल्पित समस्याएँ===
-घातीय समय परिकल्पना का तात्पर्य है कि जटिलता वर्ग [[एसएनपी (जटिलता)]] में कई अन्य समस्याओं में एल्गोरिदम नहीं हैं जिनका चलने का समय इससे तेज है <math>c^n</math> कुछ के लिए {{nowrap|constant <math>c</math>.}} इन समस्याओं में ग्राफ़ कलरिंग|ग्राफ़ शामिल है {{mvar|k}}-रंग योग्यता, [[हैमिल्टनियन चक्र]], अधिकतम क्लिक्स, [[अधिकतम स्वतंत्र सेट]] और [[ शीर्ष आवरण |शीर्ष आवरण]] का पता लगाना {{nowrap|<math>n</math>-vertex}} रेखांकन. इसके विपरीत, यदि इनमें से किसी भी समस्या में उप-घातांकीय एल्गोरिदम है, तो घातांकीय समय परिकल्पना को दिखाया जा सकता है {{nowrap|false.{{r|w03|ipz01}}}}
+घातीय समय परिकल्पना का तात्पर्य है कि जटिलता वर्ग [[एसएनपी (जटिलता)|एसNP (जटिलता)]] में कई अन्य समस्याओं में कलन विधि नहीं हैं जिनका चलने का समय इससे तेज है, इस प्रकार <math>c^n</math> के लिए {{nowrap|constant <math>c</math>.}} द्वारा इन समस्याओं में ग्राफ़ कलरिंग|ग्राफ़ सम्मिलित है {{mvar|k}}-रंग योग्यता, [[हैमिल्टनियन चक्र]], अधिकतम क्लिक्स, [[अधिकतम स्वतंत्र सेट|अधिकतम स्वतंत्र समुच्चय]] और [[ शीर्ष आवरण |शीर्ष आवरण]] का पता लगाकर {{nowrap|<math>n</math>-vertex}} रेखांकन के लिए इसके विपरीत, यदि इनमें से किसी भी समस्या में उप-घातांकीय कलन विधि है, तो घातांकीय समय परिकल्पना को {{nowrap|false.{{r|w03|ipz01}}}} मान द्वारा दिखाया जा सकता है।
-यदि बहुपद समय में समूह या लघुगणकीय आकार के स्वतंत्र सेट पाए जा सकते हैं, तो घातीय समय परिकल्पना झूठी होगी। इसलिए, भले ही ऐसे छोटे आकार के समूह या स्वतंत्र सेट ढूंढना एनपी-पूर्ण होने की संभावना नहीं है, घातीय समय परिकल्पना का तात्पर्य है कि ये समस्याएं हैं {{nowrap|non-polynomial.{{r|w03|fk}}}} अधिक आम तौर पर, घातीय समय परिकल्पना का तात्पर्य है कि क्लिक्स या आकार के स्वतंत्र सेट ढूंढना संभव नहीं है <math>k</math> में {{nowrap|time <math>n^{o(k)}</math>.{{r|chkx}}}}घातांकीय समय परिकल्पना का यह भी तात्पर्य है कि 3SUM| को हल करना संभव नहीं है{{mvar|k}}-SUM समस्या (दिया गया है <math>n</math> वास्तविक संख्याएँ, खोजें <math>k</math> उनमें से जो शून्य में जोड़ते हैं) में {{nowrap|time <math>n^{o(k)}</math>.}}
+यदि बहुपद समय में समूह या लघुगणकीय आकार के स्वतंत्र समुच्चय पाए जा सकते हैं, तो घातीय समय परिकल्पना असत्य होगी। इसलिए भले ही ऐसे छोटे आकार के समूह या स्वतंत्र समुच्चय ढूंढना NP-पूर्ण होने की संभावना नहीं है, घातीय समय परिकल्पना का तात्पर्य है कि ये समस्याएं {{nowrap|non-polynomial.{{r|w03|fk}}}} हैं, इस प्रकार इससे अधिक मान को सामान्यतः घातीय समय परिकल्पना का तात्पर्य है कि क्लिक्स या आकार के स्वतंत्र समुच्चय ढूंढना संभव नहीं है <math>k</math> में {{nowrap|time <math>n^{o(k)}</math>.{{r|chkx}}}} को घातांकीय समय परिकल्पना के रूप में प्रदर्शित करते हैं, जिसका यह भी तात्पर्य है कि 3SUM को हल करना संभव नहीं है, जिसके कारण {{mvar|k}}-SUM समस्या इस प्रकार है कि <math>n</math> वास्तविक संख्याएँ हैं जहाँ पर <math>k</math> उनमें से जो शून्य में जोड़ते हैं, जिसमें {{nowrap|time <math>n^{o(k)}</math>.}}मान प्राप्त होता हैं। इस प्रकार मजबूत घातीय समय परिकल्पना का तात्पर्य है कि इसे खोजना संभव नहीं है {{nowrap|<math>k</math>-vertex}} अंदर की तुलना में समुच्चय पर अधिक तेजी से {{nowrap|time <math>n^{k-o(1)}</math>.{{r|pw10}}}} का प्रभावी होना यहाँ पर मुख्य हैं।
-मजबूत घातीय समय परिकल्पना का तात्पर्य है कि इसे खोजना संभव नहीं है {{nowrap|<math>k</math>-vertex}} अंदर की तुलना में सेट पर अधिक तेजी से हावी होना {{nowrap|time <math>n^{k-o(1)}</math>.{{r|pw10}}}}
-घातीय समय परिकल्पना का तात्पर्य यह भी है कि [[टूर्नामेंट (ग्राफ सिद्धांत)]] पर भारित [[फीडबैक आर्क सेट]] समस्या में चलने के साथ पैरामीट्रिज्ड एल्गोरिदम नहीं है {{nowrap|time <math display=inline>O(2^{o(\sqrt{\operatorname{OPT}})}n^{O(1)})</math>.}} हालाँकि इसमें चलने के साथ पैरामीटरयुक्त एल्गोरिदम है {{nowrap|time <math display=inline>O(2^{O(\sqrt{\operatorname{OPT}})}n^{O(1)})</math>.{{r|ks}}}}
+घातीय समय परिकल्पना का तात्पर्य यह भी है कि [[टूर्नामेंट (ग्राफ सिद्धांत)]] पर भारित [[फीडबैक आर्क सेट|फीडबैक आर्क समुच्चय]] समस्या में चलने के साथ पैरामीट्रिज्ड कलन विधि नहीं है, इस प्रकार {{nowrap|time <math display=inline>O(2^{o(\sqrt{\operatorname{OPT}})}n^{O(1)})</math>.}} चूंकि इसमें चलने के साथ पैरामीटरयुक्त कलन विधि {{nowrap|time <math display=inline>O(2^{O(\sqrt{\operatorname{OPT}})}n^{O(1)})</math>.{{r|ks}}}} है।
-मजबूत घातीय समय परिकल्पना बंधे हुए [[वृक्ष चौड़ाई]] के ग्राफ़ पर कई ग्राफ़ समस्याओं की [[पैरामीटरयुक्त जटिलता]] पर कड़ी सीमाएं लगाती है। विशेष रूप से, यदि मजबूत घातीय समय परिकल्पना सत्य है, तो ग्राफ़ पर स्वतंत्र सेट खोजने के लिए इष्टतम समय सीमा है {{nowrap|treewidth <math>w</math>}} {{nowrap|is <math display=inline>\bigl(2-o(1)\bigr)^w n^{O(1)}</math>,}} [[हावी सेट]] समस्या के लिए इष्टतम समय {{nowrap|is <math display=inline>\bigl(3-o(1)\bigr)^w n^{O(1)}</math>,}} [[अधिकतम कटौती]] के लिए इष्टतम समय {{nowrap|is <math display=inline>\bigl(2-o(1)\bigr)^w n^{O(1)}</math>,}} और इसके लिए इष्टतम समय {{nowrap|<math>k</math>-coloring}} {{nowrap|is <math display=inline>\bigl(k-o(1)\bigr)^w n^{O(1)}</math>.{{r|cfk}}}} समान रूप से, इन चल रहे समयों में कोई भी सुधार मजबूत घातीय समय को गलत साबित करेगा {{nowrap|hypothesis.{{r|lms}}}} घातीय समय परिकल्पना का यह भी तात्पर्य है कि इंटरसेक्शन संख्या (ग्राफ सिद्धांत) के लिए किसी भी निश्चित-पैरामीटर ट्रैक्टेबल एल्गोरिदम में डबल घातीय फ़ंक्शन निर्भरता होनी चाहिए {{nowrap|parameter.{{r|cpp}}}}
+मजबूत घातीय समय परिकल्पना बंधे हुए [[वृक्ष चौड़ाई]] के ग्राफ़ पर कई ग्राफ़ समस्याओं की [[पैरामीटरयुक्त जटिलता]] पर कड़ी सीमाएं लगाती है। विशेष रूप से, यदि मजबूत घातीय समय परिकल्पना सत्य है, तो ग्राफ़ पर स्वतंत्र समुच्चय खोजने के लिए इष्टतम समय सीमा {{nowrap|treewidth <math>w</math>}} {{nowrap|is <math display=inline>\bigl(2-o(1)\bigr)^w n^{O(1)}</math>,}} है। [[हावी सेट|प्रभावी समुच्चय]] से जुड़ी समस्या के लिए इसका इष्टतम समय {{nowrap|is <math display=inline>\bigl(3-o(1)\bigr)^w n^{O(1)}</math>,}} हैं, इस प्रकार [[अधिकतम कटौती]] के लिए इष्टतम समय {{nowrap|is <math display=inline>\bigl(2-o(1)\bigr)^w n^{O(1)}</math>,}} हैं और इसके लिए इष्टतम समय {{nowrap|<math>k</math>-coloring}} {{nowrap|is <math display=inline>\bigl(k-o(1)\bigr)^w n^{O(1)}</math>.{{r|cfk}}}} हैं। इस कारण समान्य रूप से चल रहे इस समय के आधार पर इसमें कोई भी सुधार मजबूत घातीय समय को {{nowrap|hypothesis.{{r|lms}}}} गलत साबित करेगा। जिसके कारण  घातीय समय परिकल्पना का यह भी तात्पर्य है कि इंटरसेक्शन संख्या (ग्राफ सिद्धांत) के लिए किसी भी निश्चित-पैरामीटर ट्रैक्टेबल कलन विधि में डबल घातीय फ़ंक्शन निर्भरता {{nowrap|parameter.{{r|cpp}}}} होनी चाहिए।
 ===[[संचार जटिलता]]===
-संचार जटिलता में तीन-पक्षीय सेट असंबद्धता समस्या में, कुछ में पूर्णांक के तीन उपसमूह {{nowrap|range <math>[1,m]</math>}} निर्दिष्ट हैं, और तीन संचार पक्ष प्रत्येक तीन उपसमूहों में से दो को जानते हैं। लक्ष्य पार्टियों के लिए साझा संचार चैनल पर एक-दूसरे को कम से कम बिट्स संचारित करना है ताकि पक्ष यह निर्धारित कर सके कि तीन सेटों का प्रतिच्छेदन खाली है या गैर-रिक्त है। तुच्छ {{nowrap|<math>m</math>-bit}} संचार प्रोटोकॉल तीन पार्टियों में से के लिए उस पार्टी को ज्ञात दो सेटों के प्रतिच्छेदन का वर्णन करने वाला [[बिटवेक्टर]] संचारित करने के लिए होगा, जिसके बाद शेष दोनों पक्षों में से कोई भी प्रतिच्छेदन की रिक्तता निर्धारित कर सकता है। हालाँकि, यदि कोई प्रोटोकॉल मौजूद है जो समस्या का समाधान करता है {{nowrap|<math>o(m)</math> communication}} और {{nowrap|<math>2^{o(m)}</math> computation,}} इसे हल करने के लिए एल्गोरिदम में बदला जा सकता है {{nowrap|<math>k</math>-SAT}} में {{nowrap|time <math>O(1.74^n)</math>}}किसी भी निश्चित के लिए {{nowrap|constant <math>k</math>,}} मजबूत घातीय समय परिकल्पना का उल्लंघन। इसलिए, मजबूत घातीय समय परिकल्पना का तात्पर्य या तो यह है कि तीन-पक्षीय सेट असंबद्धता के लिए तुच्छ प्रोटोकॉल इष्टतम है, या किसी भी बेहतर प्रोटोकॉल के लिए घातीय मात्रा की आवश्यकता होती है {{nowrap|computation.{{r|pw10}}}}
+'''संचार जटिलता''' में तीन-पक्षीय समुच्चय असंबद्धता समस्या में, कुछ में पूर्णांक के तीन उपसमूह {{nowrap|range <math>[1,m]</math>}} निर्दिष्ट हैं, और तीन संचार पक्ष प्रत्येक तीन उपसमूहों में से दो को जानते हैं। इस प्रकार के लक्षित समहों के लिए साझा संचार चैनल पर एक-दूसरे को कम से कम बिट्स संचारित करना है ताकि पक्ष यह निर्धारित कर सके कि तीन समुच्चयों का प्रतिच्छेदन रिक्त है या गैर-रिक्त है। इस प्रकार कम से कम {{nowrap|<math>m</math>-bit}} संचार प्रोटोकॉल तीन पार्टियों में से के लिए उस पार्टी को ज्ञात दो समुच्चयों के प्रतिच्छेदन का वर्णन करने वाला [[बिटवेक्टर]] संचारित करने के लिए होगा, जिसके बाद शेष दोनों पक्षों में से कोई भी प्रतिच्छेदन की रिक्तता निर्धारित कर सकता है। चूंकि, यदि कोई प्रोटोकॉल उपस्थित है जो समस्या का समाधान करता है {{nowrap|<math>o(m)</math> communication}} और {{nowrap|<math>2^{o(m)}</math> computation,}} इसे हल करने के लिए कलन विधि में परिवर्तित किया जा सकता है, जिसके आधार पर {{nowrap|<math>k</math>-SAT}} में {{nowrap|time <math>O(1.74^n)</math>}}किसी भी निश्चित के लिए {{nowrap|constant <math>k</math>,}} मजबूत घातीय समय परिकल्पना का उल्लंघन हैं। इसलिए यहाँ पर मजबूत घातीय समय परिकल्पना का तात्पर्य या तो यह है कि तीन-पक्षीय समुच्चय असंबद्धता के लिए तुच्छ प्रोटोकॉल इष्टतम है, या किसी भी उत्तम प्रोटोकॉल के लिए घातीय मात्रा {{nowrap|computation.{{r|pw10}}}} की आवश्यकता होती है।
 ===संरचनात्मक जटिलता===
-यदि घातीय समय परिकल्पना सत्य है, तो 3-SAT में बहुपद समय एल्गोरिथ्म नहीं होगा, और इसलिए यह P बनाम NP समस्या का अनुसरण करेगा|P ≠ NP। अधिक मजबूती से, इस मामले में, 3-SAT में [[अर्ध-बहुपद समय]] एल्गोरिथ्म भी नहीं हो सकता है, इसलिए NP, QP का सबसेट नहीं हो सकता है। हालाँकि, यदि घातीय समय परिकल्पना विफल हो जाती है, तो इसका पी बनाम एनपी समस्या पर कोई प्रभाव नहीं पड़ेगा। [[पैडिंग तर्क]] एनपी-पूर्ण समस्याओं के अस्तित्व को साबित करता है जिसके लिए सबसे प्रसिद्ध रनिंग टाइम का रूप होता है <math display=inline>O(2^{n^c})</math> {{nowrap|for <math>c<1</math>,}} और यदि 3-SAT के लिए सर्वोत्तम संभव चलने का समय इस रूप में होता, तो P, NP के बराबर नहीं होता (क्योंकि 3-SAT NP-पूर्ण है और यह समय सीमा बहुपद नहीं है) लेकिन घातीय समय परिकल्पना झूठी होगी।
+यदि घातीय समय परिकल्पना सत्य है, तो 3-SAT में बहुपद समय कलन नहीं होगा, और इसलिए यह P व NP के बीच का अन्तर के लिए P ≠ NP इस समस्या का अनुसरण करेगा। इस प्रकार इसकी अधिक मजबूती से, इस स्थिति में, 3-SAT में [[अर्ध-बहुपद समय]] कलन भी नहीं हो सकता है, इसलिए NP, QP का सबसमुच्चय नहीं हो सकता है। चूंकि, यदि घातीय समय परिकल्पना विफल हो जाती है, तो इसका पी बनाम NP समस्या पर कोई प्रभाव नहीं पड़ेगा। इस प्रकार [[पैडिंग तर्क]] NP-पूर्ण समस्याओं के समय इसको प्रमाणित किया जाता है, जिसके लिए सबसे प्रसिद्ध रनिंग टाइम <math display="inline">O(2^{n^c})</math> {{nowrap|for <math>c<1</math>,}} का रूप होता है, और यदि 3-SAT के लिए सर्वोत्तम संभव चलने का समय इस रूप में होता, तो P, NP के बराबर नहीं होता, क्योंकि 3-SAT NP-पूर्ण है और यह समय सीमा बहुपद नहीं है, अपितु घातीय समय परिकल्पना असत्य होगी।
-पैरामीटरयुक्त जटिलता सिद्धांत में, क्योंकि घातीय समय परिकल्पना का तात्पर्य है कि अधिकतम क्लिक के लिए निश्चित-पैरामीटर-ट्रैक्टेबल एल्गोरिदम मौजूद नहीं है, इसका यह भी तात्पर्य है कि {{nowrap|[[Parameterized complexity|W[1] ≠ FPT]].{{r|chkx}}}}यह इस क्षेत्र में महत्वपूर्ण खुली समस्या है कि क्या इस निहितार्थ को उलटा किया जा सकता है: करता है {{nowrap|W[1] ≠ FPT}}घातांकीय समय परिकल्पना का तात्पर्य? मानकीकृत जटिलता वर्गों का पदानुक्रम है जिसे एम-पदानुक्रम कहा जाता है जो डब्ल्यू-पदानुक्रम को इस अर्थ में जोड़ता है कि, {{nowrap|all <math>i</math>,}} {{nowrap|<math>\mathsf{M}[i]\subseteq\mathsf{W}[i]\subseteq\mathsf{M}[i+1]</math>;}} उदाहरण के लिए, आकार का शीर्ष कवर ढूंढने की समस्या <math>k\log n</math> में {{nowrap|<math>n</math>-vertex}} ग्राफ़ के साथ {{nowrap|parameter <math>k</math>}} तैयार है {{nowrap|for M[1].}}घातांकीय समय परिकल्पना उस कथन के समतुल्य है {{nowrap|M[1] ≠ FPT}}, और क्या का प्रश्न <math>\mathsf{M}[i]\subseteq\mathsf{W}[i]</math> के लिए <math>i>1</math> ई आल्सो {{nowrap|open.{{r|fg}}}}
+पैरामीटरयुक्त जटिलता सिद्धांत में, क्योंकि घातीय समय परिकल्पना का तात्पर्य है कि अधिकतम क्लिक के लिए निश्चित-पैरामीटर-ट्रैक्टेबल कलन विधि उपस्थित नहीं है, इसका यह भी तात्पर्य है कि {{nowrap|[[Parameterized complexity|W[1] ≠ FPT]].{{r|chkx}}}} यह इस क्षेत्र में महत्वपूर्ण खुली समस्या है कि क्या इस निहितार्थ को व्युत्क्रम किया जा सकता है: इस प्रकार {{nowrap|W[1] ≠ FPT}}घातांकीय समय परिकल्पना का तात्पर्य हैं कि इसके लिए मानकीकृत जटिलता वर्गों का पदानुक्रम है जिसे एम-पदानुक्रम कहा जाता है जो डब्ल्यू-पदानुक्रम को इस अर्थ में जोड़ता है कि, {{nowrap|all <math>i</math>,}} {{nowrap|<math>\mathsf{M}[i]\subseteq\mathsf{W}[i]\subseteq\mathsf{M}[i+1]</math>;}} इस प्रकार उदाहरण के लिए, आकार का शीर्ष कवर ढूंढने की समस्या <math>k\log n</math> में {{nowrap|<math>n</math>-vertex}} ग्राफ़ के साथ {{nowrap|parameter <math>k</math>}} तैयार है, जिसके आधार पर {{nowrap|for M[1].}}घातांकीय समय परिकल्पना उस कथन के समतुल्य है, जिसका मान {{nowrap|M[1] ≠ FPT}}, और क्या का प्रश्न <math>\mathsf{M}[i]\subseteq\mathsf{W}[i]</math> के लिए <math>i>1</math> E also {{nowrap|open.{{r|fg}}}} हैं।
-मजबूत घातीय समय परिकल्पना की भिन्नता की विफलता से लेकर जटिलता वर्गों के पृथक्करण तक, दूसरी दिशा में निहितार्थ साबित करना भी संभव है।
+मजबूत घातीय समय परिकल्पना की भिन्नता की विफलता से लेकर जटिलता वर्गों के पृथक्करण तक, दूसरी दिशा में निहितार्थ साबित करना भी संभव है। जैसा यहां पर {{harvtxt|विलियम्स|2010}} प्रदर्शित करते हैं कि क्या कोई कलन विधि उपस्थित है, जो <math>A</math> समय में बूलियन परिपथ संतुष्टि <math>2^n/f(n)</math> को हल करता है, इस प्रकार यहाँ पर कुछ सुपरबहुपद वृद्धि के लिए {{nowrap|function <math>f</math>,}} तो [[NEXPTIME|नेक्स्प समय]] P/poly का उपसमुच्चय नहीं है। इस प्रकार विलियम्स दिखाता है कि, यदि कलन विधि <math>A</math> उपस्थित है, और P/Poly में नेक्स्प समय का अनुकरण करने वाले परिपथ का समूह भी उपस्थित है, फिर कलन विधि <math>A</math> [[समय पदानुक्रम प्रमेय]] का उल्लंघन करते हुए, कम समय में NEXPTIME समस्याओं को अनैतिक रूप से अनुकरण करने के लिए परिपथ के साथ बनाया जा सकता है। इसलिए, कलन विधि का अस्तित्व <math>A</math> परिपथ के परिवार की गैर-उपस्थितगी और इन दोनों जटिलताओं के अलग होने को {{nowrap|classes.{{r|w10}}}} द्वारा प्रमाणित करता है।
-जैसा {{harvtxt|Williams|2010}} दिखाता है, कि क्या कोई एल्गोरिदम मौजूद है <math>A</math> जो समय में बूलियन सर्किट संतुष्टि को हल करता है <math>2^n/f(n)</math> कुछ सुपरबहुपद वृद्धि के लिए {{nowrap|function <math>f</math>,}} तो [[NEXPTIME]] P/poly का उपसमुच्चय नहीं है। विलियम्स दिखाता है कि, यदि एल्गोरिदम <math>A</math> मौजूद है, और पी/पॉली में NEXPTIME का अनुकरण करने वाले सर्किट का परिवार भी मौजूद है, फिर एल्गोरिदम <math>A</math> [[समय पदानुक्रम प्रमेय]] का उल्लंघन करते हुए, कम समय में NEXPTIME समस्याओं को गैर-नियतात्मक रूप से अनुकरण करने के लिए सर्किट के साथ बनाया जा सकता है। इसलिए, एल्गोरिदम का अस्तित्व <math>A</math> सर्किट के परिवार की गैर-मौजूदगी और इन दोनों जटिलताओं के अलग होने को साबित करता है {{nowrap|classes.{{r|w10}}}}
 ==यह भी देखें==
-*सैविच का प्रमेय, दर्शाता है कि समान घातीय अंतर [[अंतरिक्ष जटिलता]] के लिए नहीं टिक सकता
+*सैविच का प्रमेय, दर्शाता है कि समान घातीय अंतर [[अंतरिक्ष जटिलता]] के लिए नहीं टिक सकता हैं।
 ==टिप्पणियाँ==

v t e कम्प्यूटेशनल कठोरता धारणाएं
संख्या सिद्धांत	पूर्णांक कारक फी-छिपा आरएसए समस्या मजबूत आरएसए द्विघात अवशेष निर्णायक समग्र अवशेष उच्च अवशेष
समूह सिद्धांत	असतत लॉगरिथम डिफी-हेलमैन निर्णायक डिफी -हेलमैन कम्प्यूटेशनल डिफी -हेलमैन
जोड़ियां	बाहरी diffie -hellman उप-समूह छिपा हुआ निर्णय रैखिक
जाली	सबसे छोटा वेक्टर समस्या निकटतम वेक्टर समस्या ( GAP त्रुटियों के साथ सीखना त्रुटियों के साथ रिंग सीखना लघु पूर्णांक समाधान
गैर-क्रिप्टोग्राफ़िक	घातीय समय परिकल्पना अद्वितीय खेल अनुमान लगाए गए क्लिक कॉनजेक्चर

Anonymous

Search

घातीय समय परिकल्पना: Difference between revisions

Namespaces

More

Page actions

Revision as of 00:29, 4 July 2023

Contents

परिभाषा