समय जटिलता

एल्गोरिदम के विश्लेषण में आमतौर पर उपयोग किए जाने वाले कार्यों के ग्राफ़, प्रत्येक फ़ंक्शन के लिए इनपुट आकार n के परिणाम के रूप में संचालन N की संख्या दिखाते हैं

कंप्यूटर विज्ञान में, समय जटिलता कम्प्यूटेशनल जटिलता है जो एक एल्गोरिथ्म को चलाने के लिए कंप्यूटर समय की मात्रा का वर्णन करती है। एल्गोरिथ्म द्वारा निष्पादित प्राथमिक संचालन की संख्या की गणना करके समय की जटिलता का अनुमान आमतौर पर लगाया जाता है, यह मानते हुए कि प्रत्येक प्राथमिक ऑपरेशन को करने के लिए एक निश्चित समय लगता है। इस प्रकार, समय की मात्रा और एल्गोरिथम द्वारा किए गए प्राथमिक कार्यों की संख्या को एक स्थिर कारक से संबंधित माना जाता है।

चूंकि एक एल्गोरिथ्म का चलने का समय एक ही आकार के विभिन्न इनपुट के बीच भिन्न हो सकता है, इसलिए आमतौर पर वर्स्ट-केस जटिलता | वर्स्ट-केस टाइम जटिलता पर विचार किया जाता है, जो किसी दिए गए आकार के इनपुट के लिए आवश्यक अधिकतम समय है। कम आम, और आमतौर पर स्पष्ट रूप से निर्दिष्ट, औसत-केस जटिलता है, जो किसी दिए गए आकार के इनपुट पर लगने वाले समय का औसत है (यह समझ में आता है क्योंकि किसी दिए गए आकार के संभावित इनपुट की केवल एक सीमित संख्या होती है)। दोनों ही मामलों में, समय जटिलता आम तौर पर इनपुट के आकार के एक समारोह (गणित) के रूप में व्यक्त की जाती है।^[1]^: 226 चूंकि यह फ़ंक्शन आम तौर पर सटीक रूप से गणना करना मुश्किल होता है, और छोटे इनपुट के लिए चलने का समय आम तौर पर परिणामी नहीं होता है, आमतौर पर जटिलता के व्यवहार पर ध्यान केंद्रित होता है जब इनपुट आकार बढ़ता है-अर्थात्, जटिलता का स्पर्शोन्मुख विश्लेषण। इसलिए, समय जटिलता आमतौर पर बड़े ओ नोटेशन का उपयोग करके व्यक्त की जाती है $O(n)$ , $O(n\log n)$ , $O(n^{\alpha })$ , $O(2^{n})$ , आदि, कहाँ $n$ इनपुट का प्रतिनिधित्व करने के लिए आवश्यक बिट्स की इकाइयों में आकार है।

एल्गोरिथम जटिलताओं को बिग ओ नोटेशन में दिखाई देने वाले फ़ंक्शन के प्रकार के अनुसार वर्गीकृत किया गया है। उदाहरण के लिए, समय जटिलता के साथ एक एल्गोरिथ्म $O(n)$ एक रेखीय समय एल्गोरिथ्म और समय जटिलता के साथ एक एल्गोरिथ्म है $O(n^{\alpha })$ कुछ स्थिर के लिए $\alpha >1$ एक बहुपद समय एल्गोरिथ्म है।

सामान्य समय जटिलताओं की तालिका

निम्न तालिका सामान्य रूप से सामना की जाने वाली समय जटिलताओं के कुछ वर्गों को सारांशित करती है। मेज पर, poly(x) = x^O(1), यानी, x में बहुपद।

Name	Complexity class	Running time ( $T (n)$ )	Examples of running times	Example algorithms
constant time		$O(1)$	10	Finding the median value in a sorted array of numbers. Calculating $(-1) n$
inverse Ackermann time		$O{\bigl (}\alpha (n){\bigr )}$		Amortized time per operation using a disjoint set
iterated logarithmic time		$O(\log ^{*}n)$		Distributed coloring of cycles
log-logarithmic		$O(\log \log n)$		Amortized time per operation using a bounded priority queue^[2]
logarithmic time	DLOGTIME	$O(\log n)$	$\log n$ , $\log(n^{2})$	Binary search
polylogarithmic time		${\text{poly}}(\log n)$	$(\log n)^{2}$
fractional power		$O(n^{c})$ where $0<c<1$	$n^{\frac {1}{2}}$ , $n^{\frac {2}{3}}$	Searching in a kd-tree
linear time		$O(n)$	$n$ , $2n+5$	Finding the smallest or largest item in an unsorted array. Kadane's algorithm. Linear search
"n log-star n" time		$O(n\log ^{*}n)$		Seidel's polygon triangulation algorithm.
linearithmic time		$O(n\log n)$	$n\log n$ , $\log n!$	Fastest possible comparison sort Fast Fourier transform.
quasilinear time		$n{\text{poly}}(\log n)$	$n\log ^{2}n$	Multipoint polynomial evaluation
quadratic time		$O(n^{2})$	$n^{2}$	Bubble sort, Insertion sort, Direct convolution
cubic time		$O(n^{3})$	$n^{3}$	Naive multiplication of two $n\times n$ matrices Calculating partial correlation.
polynomial time	P	$2^{O(\log n)}={\text{poly}}(n)$	$n^{2}+n$ , $n^{10}$	Karmarkar's algorithm for linear programming AKS primality test^[3]^[4]
quasi-polynomial time	QP	$2^{{\text{poly}}(\log n)}$	$n^{\log \log n}$ , $n^{\log n}$	Best-known $O (log 2 n)$ -approximation algorithm for the directed Steiner tree problem.
sub-exponential time (first definition)	SUBEXP	$O(2^{n^{\epsilon }})$ for all $\epsilon >0$		Contains BPP unless EXPTIME (see below) equals MA.^[5]
sub-exponential time (second definition)		$2^{o(n)}$	${\sqrt[{3}]{2^{n}}}$	Best classical algorithm for integer factorization formerly-best algorithm for graph isomorphism
exponential time (with linear exponent)	E	$2^{O(n)}$	$1.1^{n}$ , $10^{n}$	Solving the traveling salesman problem using dynamic programming
exponential time	EXPTIME	$2^{{\text{poly}}(n)}$	$2^{n}$ , $2^{n^{2}}$	Solving matrix chain multiplication via brute-force search
factorial time		$O(n!)$	$n!$	Solving the traveling salesman problem via brute-force search
double exponential time	2-EXPTIME	$2^{2^{{\text{poly}}(n)}}$	$2^{2^{n}}$	Deciding the truth of a given statement in Presburger arithmetic

लगातार समय

एक एल्गोरिदम को निरंतर समय कहा जाता है (इसे भी लिखा जाता है ${\textstyle O(1)}$ समय) यदि का मान ${\textstyle T(n)}$ (एल्गोरिदम की जटिलता) एक मान से घिरा है जो इनपुट के आकार पर निर्भर नहीं करता है। उदाहरण के लिए, सरणी डेटा संरचना में किसी एक तत्व तक पहुँचने में निरंतर समय लगता है क्योंकि इसे खोजने के लिए केवल एक निर्देश (कंप्यूटर विज्ञान) का पालन करना पड़ता है। इसी तरह, आरोही क्रम में क्रमबद्ध सरणी में न्यूनतम मान ढूँढना; यह पहला तत्व है। हालाँकि, एक अनियंत्रित सरणी में न्यूनतम मान खोजना एक निरंतर समय संचालन नहीं है क्योंकि न्यूनतम मान निर्धारित करने के लिए सरणी में प्रत्येक तत्व (गणित) पर स्कैनिंग की आवश्यकता होती है। इसलिए यह एक रैखिक समय संचालन है, ले रहा है ${\textstyle O(n)}$ समय। यदि तत्वों की संख्या पहले से ज्ञात है और नहीं बदलती है, हालांकि, इस तरह के एल्गोरिदम को अभी भी निरंतर समय में चलने के लिए कहा जा सकता है।

निरंतर समय नाम के बावजूद, चलने का समय समस्या के आकार से स्वतंत्र नहीं होता है, लेकिन चलने वाले समय के लिए ऊपरी सीमा समस्या के आकार से स्वतंत्र होती है। उदाहरण के लिए, कार्य के मानों का आदान-प्रदान करता है $a$ और $b$ यदि आवश्यक हो तो ${\textstyle a\leq b}$ स्थिर समय कहा जाता है, भले ही समय इस बात पर निर्भर हो सकता है कि यह पहले से ही सत्य है या नहीं ${\textstyle a\leq b}$ . हालाँकि, कुछ स्थिर है $t$ ताकि आवश्यक समय हमेशा अधिक से अधिक हो $t$ .

यहां कोड फ़्रैगमेंट के कुछ उदाहरण दिए गए हैं जो निरंतर समय में चलते हैं:

इंट इंडेक्स = 5;
int आइटम = सूची [अनुक्रमणिका];
अगर (शर्त सही) तो
    कुछ ऑपरेशन करें जो निरंतर समय में चलते हैं
और कुछ
    कुछ अन्य ऑपरेशन करें जो निरंतर समय में चलते हैं
मैं = 1 से 100 के लिए
    जे = 1 से 200 के लिए
        कुछ ऑपरेशन करें जो निरंतर समय में चलते हैं

यदि $T(n)$ है $O(a)$ , कहां $a$ कोई भी स्थिर मान है, यह इसके बराबर है और मानक संकेतन में कहा गया है $T(n)$ प्राणी $O(1)$ .

लघुगणकीय समय

एक एल्गोरिदम को लघुगणकीय समय लेने के लिए कहा जाता है जब $T(n)=O(\log n)$ . तब से $\log _{a}n$ और $\log _{b}n$ एक लॉगरिदमिक पहचान से संबंधित हैं # आधार को बदलना, और इस तरह के एक बड़े ओ नोटेशन # निरंतर बड़े ओ वर्गीकरण से गुणा, लॉगरिदमिक-टाइम एल्गोरिदम के लिए मानक उपयोग है $O(\log n)$ की अभिव्यक्ति में दिखाई देने वाले लघुगणक के आधार की परवाह किए बिना $T$ .

लॉगरिदमिक समय लेने वाले एल्गोरिदम आमतौर पर बाइनरी ट्री के संचालन में या बाइनरी खोज का उपयोग करते समय पाए जाते हैं।

एक $O(\log n)$ एल्गोरिदम को अत्यधिक कुशल माना जाता है, क्योंकि इनपुट के आकार में संचालन की संख्या का अनुपात घटता है और जब शून्य हो जाता है $n$ बढ़ती है। एक एल्गोरिदम जिसे अपने इनपुट के सभी तत्वों तक पहुंचना चाहिए, लॉगरिदमिक समय नहीं ले सकता, क्योंकि आकार के इनपुट को पढ़ने में लगने वाला समय $n$ के क्रम का है $n$ .

लघुगणकीय समय का एक उदाहरण शब्दकोश खोज द्वारा दिया गया है। एक शब्दकोश पर विचार करें (डेटा संरचना) $D$ जिसमें है $n$ प्रविष्टियाँ, वर्णानुक्रम द्वारा क्रमबद्ध। हम मानते हैं कि, के लिए $1\leq k\leq n$ , कोई इसे एक्सेस कर सकता है $k$ एक स्थिर समय में शब्दकोश की वें प्रविष्टि। होने देना $D(k)$ इसे निरूपित करें $k$ फिर कोशिश करो। इन परिकल्पनाओं के तहत, एक शब्द देखने के लिए परीक्षण करें $w$ शब्दकोश में है लघुगणकीय समय में किया जा सकता है: विचार करें $D\left(\left\lfloor {\frac {n}{2}}\right\rfloor \right)$ , कहां $\lfloor \;\rfloor$ फर्श समारोह को दर्शाता है। यदि $w=D\left(\left\lfloor {\frac {n}{2}}\right\rfloor \right)$ , तो हम कर चुके हैं। वरना अगर $w<D\left(\left\lfloor {\frac {n}{2}}\right\rfloor \right)$ , शब्दकोश के बाएँ आधे हिस्से में इसी तरह खोज जारी रखें, अन्यथा इसी तरह शब्दकोश के दाहिने आधे हिस्से में भी जारी रखें। यह एल्गोरिथम उस विधि के समान है जिसका उपयोग अक्सर पेपर डिक्शनरी में प्रविष्टि खोजने के लिए किया जाता है।

बहुलघुगणकीय समय

कहा जाता है कि एक एल्गोरिदम पॉलीलॉगरिदमिक फ़ंक्शन समय में चलता है यदि इसका समय है $T(n)$ है $O{\bigl (}(\log n)^{k}{\bigr )}$ कुछ स्थिर के लिए $k$ . इसे लिखने का दूसरा तरीका है $O(\log ^{k}n)$ .

उदाहरण के लिए, एक समानांतर रैंडम-एक्सेस मशीन पर मैट्रिक्स श्रृंखला गुणन को पॉलीलॉगरिदमिक समय में हल किया जा सकता है,^[6] और ग्राफ़ (discrete_mathematics) में डायनेमिक कनेक्टिविटी तरीके से प्लैनारिटी परीक्षण हो सकता है $O(\log ^{3}n)$ समय प्रति सम्मिलित/हटाएं ऑपरेशन।^[7]

उप-रैखिक समय

कहा जाता है कि एक एल्गोरिदम उप-रैखिक समय (अक्सर वर्तनी उप-रेखीय समय) में चलता है $T(n)=o(n)$ . विशेष रूप से इसमें ऊपर परिभाषित समय जटिलताओं वाले एल्गोरिदम शामिल हैं।

विशिष्ट एल्गोरिदम जो सटीक हैं और फिर भी उप-रैखिक समय में चलते हैं समानांतर एल्गोरिदम का उपयोग करते हैं (एनसी (जटिलता) के रूप में¹ मैट्रिक्स निर्धारक गणना करता है), या वैकल्पिक रूप से इनपुट संरचना पर गारंटीकृत धारणा है (जैसा कि लॉगरिदमिक टाइम बाइनरी सर्च एल्गोरिदम और कई पेड़ रखरखाव एल्गोरिदम करते हैं)। हालाँकि, औपचारिक भाषाएँ जैसे कि सभी स्ट्रिंग्स का सेट जिसमें पहले द्वारा इंगित स्थिति में 1-बिट है $\log n$ स्ट्रिंग के बिट्स इनपुट के प्रत्येक बिट पर निर्भर हो सकते हैं और फिर भी उप-रैखिक समय में गणना योग्य हो सकते हैं।

विशिष्ट शब्द सबलाइनियर टाइम एल्गोरिथ्म आमतौर पर उन एल्गोरिदम के लिए आरक्षित होता है जो उपरोक्त के विपरीत होते हैं, जिसमें वे शास्त्रीय सीरियल मशीन मॉडल पर चलते हैं और इनपुट पर पूर्व धारणाओं की अनुमति नहीं होती है।^[8] हालांकि उन्हें यादृच्छिक एल्गोरिथम होने की अनुमति है, और वास्तव में सभी कार्यों के लिए यादृच्छिक होना चाहिए लेकिन सबसे तुच्छ कार्य।

चूंकि इस तरह के एल्गोरिदम को पूरे इनपुट को पढ़ने के बिना एक उत्तर प्रदान करना चाहिए, इसका विवरण इनपुट के लिए अनुमत पहुंच पर बहुत अधिक निर्भर करता है। आम तौर पर एक इनपुट के लिए जिसे बाइनरी स्ट्रिंग के रूप में दर्शाया जाता है $b_{1},...,b_{k}$ यह माना जाता है कि एल्गोरिथ्म समय में हो सकता है $O(1)$ अनुरोध करें और का मूल्य प्राप्त करें $b_{i}$ किसी के लिए $i$ .

उप-रैखिक समय एल्गोरिदम आमतौर पर यादृच्छिक होते हैं, और केवल सन्निकटन एल्गोरिदम समाधान प्रदान करते हैं। वास्तव में, केवल शून्य (और कोई नहीं) वाले बाइनरी स्ट्रिंग की संपत्ति को एक (गैर-अनुमानित) उप-रैखिक समय एल्गोरिदम द्वारा आसानी से निर्णायक साबित नहीं किया जा सकता है। संपत्ति परीक्षण की जांच में स्वाभाविक रूप से उप-रैखिक समय एल्गोरिदम उत्पन्न होते हैं।

रैखिक समय

एक एल्गोरिदम को रैखिक समय लेने के लिए कहा जाता है, या $O(n)$ समय, अगर इसकी समय जटिलता है $O(n)$ . अनौपचारिक रूप से, इसका मतलब है कि चलने का समय इनपुट के आकार के साथ सबसे अधिक रैखिक रूप से बढ़ता है। अधिक सटीक रूप से, इसका मतलब है कि एक स्थिरांक है $c$ ऐसा कि चलने का समय अधिकतम है $cn$ आकार के हर इनपुट के लिए $n$ . उदाहरण के लिए, एक प्रक्रिया जो किसी सूची के सभी तत्वों को जोड़ती है, सूची की लंबाई के अनुपात में समय की आवश्यकता होती है, यदि जोड़ने का समय स्थिर है, या कम से कम, स्थिर से घिरा हुआ है।

रैखिक समय उन स्थितियों में सर्वोत्तम संभव समय जटिलता है जहां एल्गोरिथ्म को अपने संपूर्ण इनपुट को क्रमिक रूप से पढ़ना पड़ता है। इसलिए, रैखिक समय या कम से कम, लगभग रैखिक समय प्रदर्शित करने वाले एल्गोरिदम की खोज में बहुत शोध किया गया है। इस शोध में सॉफ्टवेयर और हार्डवेयर दोनों तरीके शामिल हैं। ऐसी कई हार्डवेयर प्रौद्योगिकियां हैं जो इसे प्रदान करने के लिए समानांतर कंप्यूटिंग का फायदा उठाती हैं। एक उदाहरण सामग्री-पता योग्य मेमोरी है। रैखिक समय की यह अवधारणा स्ट्रिंग मिलान एल्गोरिदम में प्रयोग की जाती है जैसे बॉयर-मूर स्ट्रिंग सर्च एल्गोरिदम | बॉयर-मूर एल्गोरिदम और यूकेकोनेन एल्गोरिदम।

<विस्तार आईडी = रैखिक समय> समरेखीय समय

कहा जाता है कि एक एल्गोरिथम क्वैसिलिनियर टाइम में चलता है (जिसे लॉग-लीनियर टाइम भी कहा जाता है)। $T(n)=O(n\log ^{k}n)$ कुछ सकारात्मक स्थिरांक के लिए $k$ ;^[9] रैखिक समय का मामला है $k=1$ .^[10] सॉफ्ट ओ नोटेशन का उपयोग करते हुए ये एल्गोरिदम हैं ${\tilde {O}}(n)$ . क्वैसिलिनियर टाइम एल्गोरिदम भी हैं $O(n^{1+\epsilon })$ हर स्थिरांक के लिए $\epsilon >0$ और इस प्रकार किसी भी बहुपद समय एल्गोरिथम की तुलना में तेजी से चलता है जिसकी समयबद्धता में एक शब्द शामिल है $n^{c}$ किसी के लिए $c>1$ .

क्वासिलिनियर समय में चलने वाले एल्गोरिदम में शामिल हैं:

इन-प्लेस मर्ज सॉर्ट, $O(n\log ^{2}n)$
जल्दी से सुलझाएं, $O(n\log n)$ , इसके यादृच्छिक संस्करण में, चलने का समय होता है $O(n\log n)$ सबसे खराब स्थिति वाले इनपुट की अपेक्षा में। इसके गैर-यादृच्छिक संस्करण में एक है $O(n\log n)$ औसत केस जटिलता पर विचार करते समय केवल चलने का समय।
ढेर बनाएं और छांटें, $O(n\log n)$ , सबसे खराब स्थिति में मर्ज सॉर्ट, इंट्रोसॉर्ट, बाइनरी ट्री सॉर्ट, स्मूथसॉर्ट, धैर्य सॉर्टिंग आदि
फास्ट फूरियर बदल जाता है, $O(n\log n)$
मोंज सरणी गणना, $O(n\log n)$

कई मामलों में, $O(n\log n)$ चलने का समय केवल प्रदर्शन करने का परिणाम है $\Theta (\log n)$ संचालन $n$ टाइम्स (नोटेशन के लिए, देखें Big O notation § Family of Bachmann–Landau notations). उदाहरण के लिए, बाइनरी ट्री सॉर्ट प्रत्येक तत्व को सम्मिलित करके एक बाइनरी ट्री बनाता है $n$ एक-एक करके आकार की सरणी। चूंकि सेल्फ-बैलेंसिंग बाइनरी सर्च ट्री पर इन्सर्ट ऑपरेशन लगता है $O(\log n)$ समय, संपूर्ण एल्गोरिथ्म लेता है $O(n\log n)$ समय।

तुलना प्रकार के लिए कम से कम आवश्यकता होती है $\Omega (n\log n)$ सबसे खराब स्थिति में तुलना क्योंकि $\log(n!)=\Theta (n\log n)$ , स्टर्लिंग के सन्निकटन द्वारा। वे अक्सर पुनरावृत्ति संबंध से भी उत्पन्न होते हैं ${\textstyle T(n)=2T\left({\frac {n}{2}}\right)+O(n)}$ .

उप-द्विघात समय

एक एल्गोरिथम को सबक्वाड्रैटिक टाइम कहा जाता है यदि $T(n)=o(n^{2})$ .

उदाहरण के लिए, सरल, तुलना-आधारित सॉर्टिंग एल्गोरिदम द्विघात (जैसे सम्मिलन सॉर्ट) हैं, लेकिन अधिक उन्नत एल्गोरिदम पाए जा सकते हैं जो सबक्वाड्रैटिक (जैसे शेल सॉर्ट) हैं। कोई सामान्य-उद्देश्य प्रकार रैखिक समय में नहीं चलता है, लेकिन द्विघात से उप-द्विघात में परिवर्तन का बड़ा व्यावहारिक महत्व है।

बहुपद समय

एक एल्गोरिथ्म को बहुपद समय कहा जाता है यदि इसके चलने का समय एल्गोरिथम के लिए इनपुट के आकार में एक बहुपद अभिव्यक्ति से ऊपरी सीमा होती है, अर्थात, T(n) = O(n^k) कुछ धनात्मक नियतांक k के लिए।^[1]^[11] निर्णय समस्या जिसके लिए नियतात्मक बहुपद-समय एल्गोरिथ्म मौजूद है, जटिलता वर्ग P (जटिलता) से संबंधित है, जो कम्प्यूटेशनल जटिलता सिद्धांत के क्षेत्र में केंद्रीय है। कोभम की थीसिस बताती है कि बहुपद समय ट्रैक्टेबल, व्यवहार्य, कुशल या तेज का पर्याय है।^[12] बहुपद-समय एल्गोरिदम के कुछ उदाहरण:

n पूर्णांकों पर चयन छँटाई छँटाई एल्गोरिथ्म करता है $An^{2}$ कुछ निरंतर ए के लिए संचालन। इस प्रकार यह समय में चलता है $O(n^{2})$ और एक बहुपद-समय एल्गोरिथम है।
सभी बुनियादी अंकगणितीय ऑपरेशन (जोड़, घटाव, गुणा, भाग और तुलना) बहुपद समय में किए जा सकते हैं।
ग्राफ में अधिकतम मिलान (असतत गणित) बहुपद समय में पाया जा सकता है।

मजबूत और कमजोर बहुपद समय

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

अभिकलन के अंकगणितीय मॉडल में अत्यधिक बहुपद समय को परिभाषित किया गया है। गणना के इस मॉडल में बुनियादी अंकगणितीय संचालन (जोड़, घटाव, गुणा, भाग और तुलना) संचालन के आकार की परवाह किए बिना प्रदर्शन करने के लिए एक इकाई समय कदम उठाते हैं। एल्गोरिथ्म दृढ़ता से बहुपद समय में चलता है यदि:^[13]

संगणना के अंकगणितीय मॉडल में संचालन की संख्या इनपुट उदाहरण में पूर्णांकों की संख्या में एक बहुपद द्वारा सीमित है; और
एल्गोरिथम द्वारा उपयोग किया जाने वाला स्थान इनपुट के आकार में एक बहुपद से घिरा होता है।

ट्यूरिंग मशीन पर अंकगणितीय संचालन करने के लिए उपयुक्त एल्गोरिदम द्वारा अंकगणितीय संचालन को प्रतिस्थापित करके इन दो गुणों वाले किसी भी एल्गोरिदम को बहुपद समय एल्गोरिदम में परिवर्तित किया जा सकता है। दूसरी शर्त सख्ती से जरूरी है: पूर्णांक दिया गया है $2^{n}$ (जो ट्यूरिंग मशीन मॉडल में n के समानुपाती स्थान लेता है), गणना करना संभव है $2^{2^{n}}$ दोहराए गए वर्ग का उपयोग करते हुए n गुणन के साथ। हालांकि, अंतरिक्ष का प्रतिनिधित्व करने के लिए प्रयोग किया जाता है $2^{2^{n}}$ के लिए आनुपातिक है $2^{n}$ , और इस प्रकार इनपुट का प्रतिनिधित्व करने के लिए उपयोग किए जाने वाले स्थान में बहुपद के बजाय घातांक। इसलिए, ट्यूरिंग मशीन पर बहुपद समय में इस गणना को करना संभव नहीं है, लेकिन बहुपद रूप से कई अंकगणितीय संक्रियाओं द्वारा इसकी गणना करना संभव है।

हालाँकि, पहली स्थिति के लिए, ऐसे एल्गोरिदम हैं जो बाइनरी-एन्कोडेड इनपुट की लंबाई में एक बहुपद द्वारा बंधे ट्यूरिंग मशीन के कई चरणों में चलते हैं, लेकिन इनपुट की संख्या में बहुपद द्वारा बंधे कई अंकगणितीय संचालन नहीं करते हैं। नंबर। दो पूर्णांकों के महत्तम समापवर्तक की गणना के लिए यूक्लिडियन एल्गोरिथ्म एक उदाहरण है। दो पूर्णांक दिए गए हैं $a$ और $b$ , एल्गोरिथ्म करता है $O(\log a+\log b)$ के साथ संख्याओं पर अंकगणितीय संचालन अधिक से अधिक $O(\log a+\log b)$ बिट्स। साथ ही, अंकगणितीय परिचालनों की संख्या इनपुट में पूर्णांकों की संख्या से बंधी नहीं हो सकती है (जो इस मामले में स्थिर है, इनपुट में हमेशा केवल दो पूर्णांक होते हैं)। बाद के अवलोकन के कारण, एल्गोरिदम दृढ़ता से बहुपद समय में नहीं चलता है। इसका वास्तविक चलने का समय लघुगणकीय रूप से के परिमाण पर निर्भर करता है $a$ और $b$ (यानी बिट्स में उनकी लंबाई पर) और न केवल इनपुट में पूर्णांकों की संख्या पर।

एक एल्गोरिदम जो बहुपद समय में चलता है लेकिन यह दृढ़ता से बहुपद नहीं है, कमजोर बहुपद समय में चलने के लिए कहा जाता है।^[14] एक समस्या का एक प्रसिद्ध उदाहरण जिसके लिए एक कमजोर बहुपद-समय एल्गोरिदम ज्ञात है, लेकिन दृढ़ता से बहुपद-समय एल्गोरिदम को स्वीकार करने के लिए ज्ञात नहीं है, रैखिक प्रोग्रामिंग है। कमजोर बहुपद समय को छद्म बहुपद समय के साथ भ्रमित नहीं होना चाहिए, जो समस्या में मूल्यों के परिमाण पर रैखिक रूप से निर्भर करता है और वास्तव में बहुपद समय नहीं है।

जटिलता वर्ग

बहुपद समय की अवधारणा कम्प्यूटेशनल जटिलता सिद्धांत में कई जटिलता वर्गों की ओर ले जाती है। बहुपद समय का उपयोग करके परिभाषित कुछ महत्वपूर्ण वर्ग निम्नलिखित हैं।

पी (जटिलता): निर्णय समस्याओं की जटिलता वर्ग जिसे नियतात्मक ट्यूरिंग मशीन पर बहुपद समय में हल किया जा सकता है
एनपी (जटिलता): बहुपद समय में एक गैर-नियतात्मक ट्यूरिंग मशीन पर हल की जा सकने वाली निर्णय समस्याओं की जटिलता वर्ग
ZPP (जटिलता): निर्णय समस्याओं की जटिलता वर्ग जिसे बहुपद समय में एक संभाव्य ट्यूरिंग मशीन पर शून्य त्रुटि से हल किया जा सकता है
आरपी (जटिलता): निर्णय समस्याओं की जटिलता वर्ग जिसे बहुपद समय में संभाव्य ट्यूरिंग मशीन पर 1-पक्षीय त्रुटि से हल किया जा सकता है।
बीपीपी (जटिलता): निर्णय समस्याओं की जटिलता वर्ग जिसे बहुपद समय में संभाव्य ट्यूरिंग मशीन पर 2-पक्षीय त्रुटि से हल किया जा सकता है
बीक्यूपी: बहुपद समय में क्वांटम ट्यूरिंग मशीन पर 2-पक्षीय त्रुटि के साथ हल की जा सकने वाली निर्णय समस्याओं की जटिलता वर्ग

P नियतात्मक मशीन पर सबसे छोटा समय-जटिलता वर्ग है जो मशीन मॉडल परिवर्तनों के संदर्भ में रोबस्टनेस (कंप्यूटर विज्ञान) है। (उदाहरण के लिए, सिंगल-टेप ट्यूरिंग मशीन से मल्टी-टेप मशीन में बदलाव से द्विघात स्पीडअप हो सकता है, लेकिन कोई भी एल्गोरिथ्म जो एक मॉडल के तहत बहुपद समय में चलता है, दूसरे पर भी ऐसा करता है।) कोई भी सार मशीन उस मशीन पर बहुपद समय में हल की जा सकने वाली समस्याओं के अनुरूप एक जटिलता वर्ग है।

सुपरपोलिनोमियल समय

एक एल्गोरिदम को सुपरपोलिनोमियल समय लेने के लिए परिभाषित किया गया है यदि T(n) ऊपर किसी बहुपद से घिरा नहीं है। बिग ओ नोटेशन का उपयोग करना#बचमान-लैंडौ नोटेशन का परिवार, यह ω(n है^c) सभी स्थिरांकों के लिए समय c, जहाँ n इनपुट पैरामीटर है, आमतौर पर इनपुट में बिट्स की संख्या।

उदाहरण के लिए, एक एल्गोरिदम जो 2 के लिए चलता हैⁿ आकार n के इनपुट पर कदमों के लिए सुपरपोलिनोमियल समय (विशेष रूप से, घातीय समय) की आवश्यकता होती है।

एक एल्गोरिथम जो घातीय संसाधनों का उपयोग करता है, स्पष्ट रूप से सुपरपोलिनोमियल है, लेकिन कुछ एल्गोरिदम केवल बहुत कमजोर सुपरपोलिनोमियल हैं। उदाहरण के लिए, एडलमैन-पोमेरेंस-रूमली प्रिमलिटी टेस्ट के लिए चलता है n^{O(log log n)} एन-बिट इनपुट पर समय; यह काफी बड़े n के लिए किसी भी बहुपद की तुलना में तेजी से बढ़ता है, लेकिन इनपुट आकार को अव्यावहारिक रूप से बड़ा होना चाहिए, इससे पहले कि यह बहुपद पर छोटी डिग्री के साथ हावी न हो सके।

एक एल्गोरिदम जिसके लिए सुपरपोलिनोमियल समय की आवश्यकता होती है, वह जटिलता वर्ग 'पी (जटिलता)' के बाहर होता है। कोभम की थीसिस मानती है कि ये एल्गोरिदम अव्यावहारिक हैं, और कई मामलों में ये हैं। चूंकि पी बनाम एनपी समस्या अनसुलझी है, यह अज्ञात है कि एनपी-पूर्ण समस्याओं के लिए सुपरपोलिनोमियल समय की आवश्यकता है या नहीं।

अर्ध-बहुपद समय

अर्ध-बहुपद समय एल्गोरिदम ऐसे एल्गोरिदम हैं जो बहुपद समय से अधिक समय तक चलते हैं, फिर भी इतने लंबे समय तक घातीय समय नहीं होते हैं। अर्ध-बहुपद समय एल्गोरिदम का सबसे खराब स्थिति चलने का समय है $2^{O(\log ^{c}n)}$ कुछ निश्चित के लिए $c>0$ . के लिए $c=1$ हमें एक बहुपद समय एल्गोरिदम मिलता है, के लिए $c<1$ हमें एक उप-रैखिक समय एल्गोरिदम मिलता है।

अर्ध-बहुपद समय एल्गोरिदम आमतौर पर एक एनपी-हार्ड समस्या से दूसरी समस्या में कमी (जटिलता) में उत्पन्न होती है। उदाहरण के लिए, कोई एनपी कठिन समस्या का उदाहरण ले सकता है, बूलियन संतुष्टि समस्या कह सकता है, और इसे किसी अन्य समस्या बी के उदाहरण में परिवर्तित कर सकता है, लेकिन उदाहरण का आकार बन जाता है $2^{O(\log ^{c}n)}$ . उस स्थिति में, यह कमी यह साबित नहीं करती है कि समस्या बी एनपी-हार्ड है; यह कमी केवल यह दर्शाती है कि B के लिए कोई बहुपद समय एल्गोरिथ्म नहीं है जब तक कि 3SAT (और इस प्रकार सभी NP (जटिलता)) के लिए अर्ध-बहुपद समय एल्गोरिथ्म नहीं है। इसी तरह, कुछ समस्याएं हैं जिनके लिए हम अर्ध-बहुपद समय एल्गोरिदम जानते हैं, लेकिन कोई बहुपद समय एल्गोरिदम ज्ञात नहीं है। सन्निकटन एल्गोरिदम में ऐसी समस्याएं उत्पन्न होती हैं; एक प्रसिद्ध उदाहरण निर्देशित स्टाइनर ट्री समस्या है, जिसके लिए एक अर्ध-बहुपद समय सन्निकटन एल्गोरिथम है जो एक सन्निकटन कारक प्राप्त करता है $O(\log ^{3}n)$ (n शीर्षों की संख्या है), लेकिन इस तरह के बहुपद समय एल्गोरिदम का अस्तित्व दिखाना एक खुली समस्या है।

अर्ध-बहुपद समय समाधान के साथ अन्य कम्प्यूटेशनल समस्याएं लेकिन ज्ञात बहुपद समय समाधान में प्लांटेड क्लिक समस्या शामिल नहीं है जिसमें लक्ष्य एक क्लिक और एक यादृच्छिक ग्राफ के संघ में समस्या को क्लिक करना है। हालांकि अर्ध-बहुपद रूप से हल करने योग्य, यह अनुमान लगाया गया है कि प्लांटेड क्लिक समस्या का कोई बहुपद समय समाधान नहीं है; कम्प्यूटेशनल गेम थ्योरी, प्रॉपर्टी टेस्टिंग और मशीन लर्निंग में कई अन्य समस्याओं की कठिनाई को साबित करने के लिए इस प्लांटेड क्लिक अनुमान का उपयोग कम्प्यूटेशनल कठोरता धारणा के रूप में किया गया है।^[15] जटिलता वर्ग QP में अर्ध-बहुपद समय एल्गोरिदम वाली सभी समस्याएं शामिल हैं। इसे निम्नानुसार DTIME के रूप में परिभाषित किया जा सकता है।^[16]

{\mbox{QP}}=\bigcup _{c\in \mathbb {N} }{\mbox{DTIME}}\left(2^{\log ^{c}n}\right)

एनपी-पूर्ण समस्याओं से संबंध

जटिलता सिद्धांत में, अनसुलझी पी बनाम एनपी समस्या पूछती है कि क्या एनपी में सभी समस्याओं में बहुपद-समय एल्गोरिदम हैं। एनपी-पूर्ण समस्याओं जैसे 3SAT आदि के लिए सभी प्रसिद्ध एल्गोरिदम घातीय समय लेते हैं। दरअसल, यह कई प्राकृतिक एनपी-पूर्ण समस्याओं के लिए अनुमान लगाया गया है कि उनके पास उप-घातीय समय एल्गोरिदम नहीं हैं। यहां उप-घातीय समय का मतलब नीचे दी गई दूसरी परिभाषा से लिया गया है। (दूसरी ओर, आसन्न मैट्रिसेस द्वारा प्राकृतिक तरीके से दर्शाई गई कई ग्राफ़ समस्याएं उप-घातीय समय में केवल इसलिए हल करने योग्य हैं क्योंकि इनपुट का आकार शीर्षों की संख्या का वर्ग है।) यह अनुमान (के-एसएटी समस्या के लिए) है घातीय समय परिकल्पना के रूप में जाना जाता है।^[17] चूंकि यह अनुमान लगाया गया है कि एनपी-पूर्ण समस्याओं में अर्ध-बहुपद समय एल्गोरिदम नहीं हैं, सन्निकटन एल्गोरिदम के क्षेत्र में कुछ अनुपयुक्तता परिणाम यह धारणा बनाते हैं कि एनपी-पूर्ण समस्याओं में अर्ध-बहुपद समय एल्गोरिदम नहीं हैं। उदाहरण के लिए, सेट कवर समस्या के लिए ज्ञात अनुपयुक्तता परिणाम देखें।

उप-घातीय समय

इन्फ्रा-एक्सपोनेंशियल | सब-एक्सपोनेंशियल टाइम शब्द का प्रयोग यह व्यक्त करने के लिए किया जाता है कि कुछ एल्गोरिदम का चलने का समय किसी भी बहुपद से तेज़ी से बढ़ सकता है लेकिन अभी भी एक घातीय से काफी छोटा है। इस अर्थ में, जिन समस्याओं में उप-घातीय समय एल्गोरिदम हैं, वे उन समस्याओं की तुलना में कुछ अधिक सुगम हैं जिनमें केवल घातीय एल्गोरिदम हैं। उप-घातीय की सटीक परिभाषा पर आम तौर पर सहमति नहीं है,^[18] और हम दो सबसे व्यापक रूप से उपयोग किए जाने वाले को नीचे सूचीबद्ध करते हैं।

पहली परिभाषा

एक समस्या को उप-घातीय समय हल करने योग्य कहा जाता है यदि इसे चलने वाले समय में हल किया जा सकता है जिसका लघुगणक किसी दिए गए बहुपद से छोटा होता है। अधिक सटीक रूप से, एक समस्या उप-घातीय समय में है यदि प्रत्येक के लिए ε > 0 एक एल्गोरिदम मौजूद है जो समय ओ (2) में समस्या हल करता है^{n^ε}). ऐसी सभी समस्याओं का सेट जटिलता वर्ग 'SUBEXP' है जिसे निम्नानुसार DTIME के रूप में परिभाषित किया जा सकता है।^[5]^[19]^[20]^[21]

{\text{SUBEXP}}=\bigcap _{\varepsilon >0}{\text{DTIME}}\left(2^{n^{\varepsilon }}\right)

उप-घातीय की यह धारणा ε के संदर्भ में गैर-समान है कि ε इनपुट का हिस्सा नहीं है और समस्या के लिए प्रत्येक ε का अपना एल्गोरिदम हो सकता है।

दूसरी परिभाषा

कुछ लेखक उप-घातीय समय को रनिंग टाइम के रूप में परिभाषित करते हैं $2^{o(n)}$ .^[17]^[22]^[23] यह परिभाषा उप-घातीय समय की पहली परिभाषा की तुलना में बड़े चलने वाले समय की अनुमति देती है। इस तरह के एक उप-घातीय समय एल्गोरिदम का एक उदाहरण पूर्णांक कारककरण के लिए सबसे प्रसिद्ध शास्त्रीय एल्गोरिदम है, सामान्य संख्या फ़ील्ड चलनी, जो समय के बारे में चलती है $2^{{\tilde {O}}(n^{1/3})}$ , जहां इनपुट की लंबाई है $n$ . एक अन्य उदाहरण ग्राफ आइसोमोर्फिज्म समस्या थी, जिसे 1982 से 2016 तक के सबसे प्रसिद्ध एल्गोरिथम में हल किया गया था। $2^{O\left({\sqrt {n\log n}}\right)}$ . हालांकि, 2016 के कम्प्यूटिंग के सिद्धांत पर संगोष्ठी में एक अर्ध-बहुपद समय एल्गोरिथ्म प्रस्तुत किया गया था।^[24] इससे फर्क पड़ता है कि एल्गोरिथम को उदाहरण के आकार, शीर्षों की संख्या, या किनारों की संख्या में उप-घातीय होने की अनुमति है या नहीं। पैरामिट्रीकृत जटिलता में, जोड़े पर विचार करके इस अंतर को स्पष्ट किया जाता है $(L,k)$ निर्णय समस्याओं और मापदंडों की k। 'SUBEPT' सभी पैरामिट्रीकृत समस्याओं का वर्ग है जो k में समय उप-घातीय और इनपुट आकार n में बहुपद में चलता है:^[25]

{\text{SUBEPT}}={\text{DTIME}}\left(2^{o(k)}\cdot {\text{poly}}(n)\right).

अधिक सटीक रूप से, SUBEPT सभी पैरामिट्रीकृत समस्याओं का वर्ग है $(L,k)$ जिसके लिए एक संगणनीय कार्य है $f:\mathbb {N} \to \mathbb {N}$ साथ $f\in o(k)$ और एक एल्गोरिदम जो समय में एल तय करता है $2^{f(k)}\cdot {\text{poly}}(n)$ .

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

एक्सपोनेंशियल टाइम परिकल्पना (ETH) यह है कि 3SAT, बूलियन फॉर्मूले की संतुष्टि की समस्या संयोजन सामान्य रूप में अधिकतम तीन शाब्दिक प्रति खंड और n चर के साथ, समय 2 में हल नहीं की जा सकती^{ओ (एन) </ समर्थन>। अधिक सटीक रूप से, परिकल्पना यह है कि कुछ निरपेक्ष स्थिरांक है $c > 0$ जैसे कि 3SAT को समय 2 में तय नहीं किया जा सकता है^{cn किसी नियतात्मक ट्यूरिंग मशीन द्वारा। m द्वारा खंडों की संख्या को दर्शाने के साथ, ETH इस परिकल्पना के समतुल्य है कि kSAT को समय 2 में हल नहीं किया जा सकता है^ओ(एम) किसी भी पूर्णांक के लिए $k \geq 3$ .^[26] घातीय समय परिकल्पना का तात्पर्य P ≠ NP से है।}}

घातीय समय

एक एल्गोरिथ्म को घातीय समय कहा जाता है, अगर T(n) ऊपरी 2 से घिरा है^{पॉली(एन)}, जहां पॉली(एन) एन में कुछ बहुपद है। अधिक औपचारिक रूप से, एक एल्गोरिदम घातीय समय है यदि टी (एन) ओ (2) से घिरा हुआ है^{n^k}) कुछ स्थिर k के लिए। समस्याएँ जो नियतात्मक ट्यूरिंग मशीन पर घातीय समय एल्गोरिदम को स्वीकार करती हैं, वे जटिलता वर्ग बनाती हैं जिसे 'EXP' के रूप में जाना जाता है।

{\text{EXP}}=\bigcup _{c\in \mathbb {N} }{\text{DTIME}}\left(2^{n^{c}}\right)

कभी-कभी, घातीय समय का उपयोग एल्गोरिदम को संदर्भित करने के लिए किया जाता है जिसमें T(n) = 2 होता है^O(n), जहां घातांक अधिक से अधिक n का रैखिक फलन है। यह जटिलता वर्ग 'ई (जटिलता)' को जन्म देता है।

{\text{E}}=\bigcup _{c\in \mathbb {N} }{\text{DTIME}}\left(2^{cn}\right)

क्रमगुणित समय

एक एल्गोरिदम को फैक्टोरियल टाइम कहा जाता है यदि टी (एन) फैक्टोरियल फ़ंक्शन एन! द्वारा ऊपरी सीमा में है। फैक्टोरियल टाइम एक्सपोनेंशियल टाइम (EXP) का एक सबसेट है क्योंकि $n!=O\left(2^{n^{1+\epsilon }}\right)$ सबके लिए $\epsilon >0$ . हालाँकि, यह E का उपसमुच्चय नहीं है।

फैक्टोरियल टाइम में चलने वाले एल्गोरिदम का एक उदाहरण बोगोसॉर्ट है, जो परीक्षण और त्रुटि के आधार पर एक कुख्यात अक्षम सॉर्टिंग एल्गोरिदम है। बोगोसॉर्ट सूची को बार-बार शफ़ल करते हुए n वस्तुओं की एक सूची को तब तक क्रमबद्ध करता है जब तक कि यह क्रमबद्ध न हो जाए। औसत मामले में, बोगोसॉर्ट एल्गोरिथम के माध्यम से प्रत्येक पास एन में से एक की जांच करेगा! एन आइटम के आदेश। यदि आइटम अलग-अलग हैं, तो केवल एक ऐसा क्रम क्रमबद्ध किया जाता है। बोगोसॉर्ट अनंत बंदर प्रमेय के साथ विरासत साझा करता है।

दोहरा घातीय समय

एक एल्गोरिदम को डबल एक्सपोनेंशियल फ़ंक्शन टाइम कहा जाता है यदि टी (एन) ऊपरी 2 से घिरा हुआ है^{2^{पॉली(एन)}}, जहां पॉली(एन) एन में कुछ बहुपद है। ऐसे एल्गोरिदम जटिलता वर्ग 2-EXPTIME से संबंधित हैं।

{\mbox{2-EXPTIME}}=\bigcup _{c\in \mathbb {N} }{\mbox{DTIME}}\left(2^{2^{n^{c}}}\right)

प्रसिद्ध डबल एक्सपोनेंशियल टाइम एल्गोरिदम में शामिल हैं:

प्रेस्बर्गर अंकगणित के लिए निर्णय प्रक्रियाएं
ग्रोबनेर आधार पर गणना करना (सबसे खराब स्थिति में^[27])
वास्तविक बंद क्षेत्रों पर क्वांटिफायर उन्मूलन में कम से कम दोहरा घातीय समय लगता है,^[28] और इस समय में किया जा सकता है।^[29]

यह भी देखें

एल-नोटेशन
अंतरिक्ष जटिलता

इस पेज में लापता आंतरिक लिंक की सूची

संदर्भ

↑ ^1.0 ^1.1 Sipser, Michael (2006). संगणना के सिद्धांत का परिचय. Course Technology Inc. ISBN 0-619-21764-2.
↑ Mehlhorn, Kurt; Naher, Stefan (1990). "Bounded ordered dictionaries in $O (log log N)$ time and $O (n)$ space". Information Processing Letters. 35 (4): 183–189. doi:10.1016/0020-0190(90)90022-P.
↑ Tao, Terence (2010). "1.11 The AKS primality test". An epsilon of room, II: Pages from year three of a mathematical blog. Graduate Studies in Mathematics. Vol. 117. Providence, RI: American Mathematical Society. pp. 82–86. doi:10.1090/gsm/117. ISBN 978-0-8218-5280-4. MR 2780010.
↑ Lenstra, H. W. Jr.; Pomerance, Carl (2019). "Primality testing with Gaussian periods" (PDF). Journal of the European Mathematical Society. 21 (4): 1229–1269. doi:10.4171/JEMS/861. MR 3941463. S2CID 127807021.
↑ ^5.0 ^5.1 Babai, László; Fortnow, Lance; Nisan, N.; Wigderson, Avi (1993). "जब तक EXPTIME के पास प्रकाशित करने योग्य प्रमाण न हों, तब तक BPP में सबएक्सपोनेंशियल टाइम सिमुलेशन होते हैं". Computational Complexity. Berlin, New York: Springer-Verlag. 3 (4): 307–318. doi:10.1007/BF01275486. S2CID 14802332. {{cite journal}}: zero width space character in |title= at position 18 (help)
↑ Bradford, Phillip G.; Rawlins, Gregory J. E.; Shannon, Gregory E. (1998). "पॉलीलॉग समय में कुशल मैट्रिक्स चेन ऑर्डरिंग". SIAM Journal on Computing. 27 (2): 466–490. doi:10.1137/S0097539794270698. MR 1616556.
↑ Holm, Jacob; Rotenberg, Eva (2020). "Fully-dynamic planarity testing in polylogarithmic time". In Makarychev, Konstantin; Makarychev, Yury; Tulsiani, Madhur; Kamath, Gautam; Chuzhoy, Julia (eds.). कंप्यूटिंग के सिद्धांत पर 52वें वार्षिक ACM SIGACT संगोष्ठी की कार्यवाही, STOC 2020, शिकागो, IL, USA, 22-26 जून, 2020. Association for Computing Machinery. pp. 167–180. arXiv:1911.03449. doi:10.1145/3357713.3384249.
↑ Kumar, Ravi; Rubinfeld, Ronitt (2003). "सबलाइनियर टाइम एल्गोरिदम" (PDF). SIGACT News. 34 (4): 57–67. doi:10.1145/954092.954103. S2CID 65359.
↑ Naik, Ashish V.; Regan, Kenneth W.; Sivakumar, D. (1995). "क्वासिलिनियर-टाइम जटिलता सिद्धांत पर" (PDF). Theoretical Computer Science. 148 (2): 325–349. doi:10.1016/0304-3975(95)00031-Q. MR 1355592.
↑ Sedgewick, Robert; Wayne, Kevin (2011). एल्गोरिदम (4th ed.). Pearson Education. p. 186.
↑ Papadimitriou, Christos H. (1994). अभिकलनात्मक जटिलता. Reading, Mass.: Addison-Wesley. ISBN 0-201-53082-1.
↑ Cobham, Alan (1965). "The intrinsic computational difficulty of functions". प्रक्रिया। तर्कशास्त्र, कार्यप्रणाली और विज्ञान का दर्शन II. North Holland.
↑ Grötschel, Martin; László Lovász; Alexander Schrijver (1988). "Complexity, Oracles, and Numerical Computation". ज्यामितीय एल्गोरिदम और संयोजन अनुकूलन. Springer. ISBN 0-387-13624-X.
↑ Schrijver, Alexander (2003). "Preliminaries on algorithms and Complexity". कॉम्बिनेटरियल ऑप्टिमाइज़ेशन: पॉलीहेड्रा और दक्षता. Vol. 1. Springer. ISBN 3-540-44389-4.
↑ Braverman, Mark; Kun-Ko, Young; Rubinstein, Aviad; Weinstein, Omri (2017). "ETH hardness for densest- $k$ -subgraph with perfect completeness". In Klein, Philip N. (ed.). असतत एल्गोरिदम, सोडा 2017, बार्सिलोना, स्पेन, होटल पोर्टा फ़िरा, जनवरी 16-19 पर ट्वेंटी-आठवीं वार्षिक एसीएम-सियाम संगोष्ठी की कार्यवाही. Society for Industrial and Applied Mathematics. pp. 1326–1341. arXiv:1504.08352. doi:10.1137/1.9781611974782.86. MR 3627815.
↑ Complexity Zoo: Class QP: Quasipolynomial-Time
↑ ^17.0 ^17.1 Impagliazzo, Russell; Paturi, Ramamohan (2001). " $k$ [[Category: Templates Vigyan Ready]]-SAT" (PDF). Journal of Computer and System Sciences. 62 (2): 367–375. doi:10.1006/jcss.2000.1727. MR 1820597. {{cite journal}}: URL–wikilink conflict (help)
↑ Aaronson, Scott (5 April 2009). "एक नहीं-काफी-घातीय दुविधा". Shtetl-Optimized. Retrieved 2 December 2009.
↑ Complexity Zoo: Class SUBEXP: Deterministic Subexponential-Time
↑ Moser, P. (2003). "Baire's Categories on Small Complexity Classes". In Andrzej Lingas; Bengt J. Nilsson (eds.). संगणना सिद्धांत के मूल सिद्धांत: 14वां अंतर्राष्ट्रीय संगोष्ठी, FCT 2003, माल्मो, स्वीडन, 12-15 अगस्त, 2003, कार्यवाही. Lecture Notes in Computer Science. Vol. 2751. Berlin, New York: Springer-Verlag. pp. 333–342. doi:10.1007/978-3-540-45077-1_31. ISBN 978-3-540-40543-6. ISSN 0302-9743.
↑ Miltersen, P.B. (2001). "Derandomizing जटिलता वर्ग". Handbook of Randomized Computing. Combinatorial Optimization. Kluwer Academic Pub. 9: 843. doi:10.1007/978-1-4615-0013-1_19. ISBN 978-1-4613-4886-3.
↑ Kuperberg, Greg (2005). "डायहेड्रल हिडन सबग्रुप प्रॉब्लम के लिए एक सबएक्सपोनेंशियल-टाइम क्वांटम एल्गोरिथम". SIAM Journal on Computing. Philadelphia. 35 (1): 188. arXiv:quant-ph/0302112. doi:10.1137/s0097539703436345. ISSN 1095-7111. S2CID 15965140.
↑ Oded Regev (2004). "पॉलीनॉमियल स्पेस के साथ डायहेड्रल हिडन सबग्रुप प्रॉब्लम के लिए एक सबएक्सपोनेंशियल टाइम एल्गोरिथम". arXiv:quant-ph/0406151v1.
↑ Grohe, Martin; Neuen, Daniel (2021). "ग्राफ समाकृतिकता समस्या पर हालिया प्रगति". arXiv:2011.01366. {{cite journal}}: Cite journal requires |journal= (help)
↑ Flum, Jörg; Grohe, Martin (2006). पैरामीटरयुक्त जटिलता सिद्धांत. Springer. p. 417. ISBN 978-3-540-29952-3.
↑ Impagliazzo, R.; Paturi, R.; Zane, F. (2001). "किन समस्याओं में अत्यधिक घातीय जटिलता है?". Journal of Computer and System Sciences. 63 (4): 512–530. doi:10.1006/jcss.2001.1774.
↑ Mayr, Ernst W.; Meyer, Albert R. (1982). "क्रमविनिमेय अर्धसमूहों और बहुपद आदर्शों के लिए शब्द समस्याओं की जटिलता". Advances in Mathematics. 46 (3): 305–329. doi:10.1016/0001-8708(82)90048-2. MR 0683204.
↑ Davenport, James H.; Heintz, Joos (1988). "वास्तविक क्वांटिफायर उन्मूलन दोगुना घातीय है". Journal of Symbolic Computation. 5 (1–2): 29–35. doi:10.1016/S0747-7171(88)80004-X. MR 0949111.
↑ Collins, George E. (1975). "Quantifier elimination for real closed fields by cylindrical algebraic decomposition". In Brakhage, H. (ed.). ऑटोमेटा सिद्धांत और औपचारिक भाषाएं: दूसरा जीआई सम्मेलन, कैसरस्लॉटर्न, 20-23 मई, 1975. Lecture Notes in Computer Science. Vol. 33. Springer. pp. 134–183. doi:10.1007/3-540-07407-4_17. MR 0403962.

श्रेणी: एल्गोरिदम का विश्लेषण श्रेणी: कम्प्यूटेशनल जटिलता सिद्धांत श्रेणी:कम्प्यूटेशनल संसाधन श्रेणी:समय

[Sipser-1] 1.0 ^1.1 Sipser, Michael (2006). संगणना के सिद्धांत का परिचय. Course Technology Inc. ISBN 0-619-21764-2.

[2] Mehlhorn, Kurt; Naher, Stefan (1990). "Bounded ordered dictionaries in $O (log log N)$ time and $O (n)$ space". Information Processing Letters. 35 (4): 183–189. doi:10.1016/0020-0190(90)90022-P.

[tao-aks-3] Tao, Terence (2010). "1.11 The AKS primality test". An epsilon of room, II: Pages from year three of a mathematical blog. Graduate Studies in Mathematics. Vol. 117. Providence, RI: American Mathematical Society. pp. 82–86. doi:10.1090/gsm/117. ISBN 978-0-8218-5280-4. MR 2780010.

[4] Lenstra, H. W. Jr.; Pomerance, Carl (2019). "Primality testing with Gaussian periods" (PDF). Journal of the European Mathematical Society. 21 (4): 1229–1269. doi:10.4171/JEMS/861. MR 3941463. S2CID 127807021.

[bpp-5] 5.0 ^5.1 Babai, László; Fortnow, Lance; Nisan, N.; Wigderson, Avi (1993). "जब तक EXPTIME के पास प्रकाशित करने योग्य प्रमाण न हों, तब तक BPP में सबएक्सपोनेंशियल टाइम सिमुलेशन होते हैं". Computational Complexity. Berlin, New York: Springer-Verlag. 3 (4): 307–318. doi:10.1007/BF01275486. S2CID 14802332. {{cite journal}}: zero width space character in |title= at position 18 (help)

[6] Bradford, Phillip G.; Rawlins, Gregory J. E.; Shannon, Gregory E. (1998). "पॉलीलॉग समय में कुशल मैट्रिक्स चेन ऑर्डरिंग". SIAM Journal on Computing. 27 (2): 466–490. doi:10.1137/S0097539794270698. MR 1616556.

[7] Holm, Jacob; Rotenberg, Eva (2020). "Fully-dynamic planarity testing in polylogarithmic time". In Makarychev, Konstantin; Makarychev, Yury; Tulsiani, Madhur; Kamath, Gautam; Chuzhoy, Julia (eds.). कंप्यूटिंग के सिद्धांत पर 52वें वार्षिक ACM SIGACT संगोष्ठी की कार्यवाही, STOC 2020, शिकागो, IL, USA, 22-26 जून, 2020. Association for Computing Machinery. pp. 167–180. arXiv:1911.03449. doi:10.1145/3357713.3384249.

[8] Kumar, Ravi; Rubinfeld, Ronitt (2003). "सबलाइनियर टाइम एल्गोरिदम" (PDF). SIGACT News. 34 (4): 57–67. doi:10.1145/954092.954103. S2CID 65359.

[9] Naik, Ashish V.; Regan, Kenneth W.; Sivakumar, D. (1995). "क्वासिलिनियर-टाइम जटिलता सिद्धांत पर" (PDF). Theoretical Computer Science. 148 (2): 325–349. doi:10.1016/0304-3975(95)00031-Q. MR 1355592.

[10] Sedgewick, Robert; Wayne, Kevin (2011). एल्गोरिदम (4th ed.). Pearson Education. p. 186.

[11] Papadimitriou, Christos H. (1994). अभिकलनात्मक जटिलता. Reading, Mass.: Addison-Wesley. ISBN 0-201-53082-1.

[12] Cobham, Alan (1965). "The intrinsic computational difficulty of functions". प्रक्रिया। तर्कशास्त्र, कार्यप्रणाली और विज्ञान का दर्शन II. North Holland.

[13] Grötschel, Martin; László Lovász; Alexander Schrijver (1988). "Complexity, Oracles, and Numerical Computation". ज्यामितीय एल्गोरिदम और संयोजन अनुकूलन. Springer. ISBN 0-387-13624-X.

[14] Schrijver, Alexander (2003). "Preliminaries on algorithms and Complexity". कॉम्बिनेटरियल ऑप्टिमाइज़ेशन: पॉलीहेड्रा और दक्षता. Vol. 1. Springer. ISBN 3-540-44389-4.

[15] Braverman, Mark; Kun-Ko, Young; Rubinstein, Aviad; Weinstein, Omri (2017). "ETH hardness for densest- $k$ -subgraph with perfect completeness". In Klein, Philip N. (ed.). असतत एल्गोरिदम, सोडा 2017, बार्सिलोना, स्पेन, होटल पोर्टा फ़िरा, जनवरी 16-19 पर ट्वेंटी-आठवीं वार्षिक एसीएम-सियाम संगोष्ठी की कार्यवाही. Society for Industrial and Applied Mathematics. pp. 1326–1341. arXiv:1504.08352. doi:10.1137/1.9781611974782.86. MR 3627815.

[16] Complexity Zoo: Class QP: Quasipolynomial-Time

[ETH-17] 17.0 ^17.1 Impagliazzo, Russell; Paturi, Ramamohan (2001). " $k$ [[Category: Templates Vigyan Ready]]-SAT" (PDF). Journal of Computer and System Sciences. 62 (2): 367–375. doi:10.1006/jcss.2000.1727. MR 1820597. {{cite journal}}: URL–wikilink conflict (help)

[18] Aaronson, Scott (5 April 2009). "एक नहीं-काफी-घातीय दुविधा". Shtetl-Optimized. Retrieved 2 December 2009.

[19] Complexity Zoo: Class SUBEXP: Deterministic Subexponential-Time

[20] Moser, P. (2003). "Baire's Categories on Small Complexity Classes". In Andrzej Lingas; Bengt J. Nilsson (eds.). संगणना सिद्धांत के मूल सिद्धांत: 14वां अंतर्राष्ट्रीय संगोष्ठी, FCT 2003, माल्मो, स्वीडन, 12-15 अगस्त, 2003, कार्यवाही. Lecture Notes in Computer Science. Vol. 2751. Berlin, New York: Springer-Verlag. pp. 333–342. doi:10.1007/978-3-540-45077-1_31. ISBN 978-3-540-40543-6. ISSN 0302-9743.

[21] Miltersen, P.B. (2001). "Derandomizing जटिलता वर्ग". Handbook of Randomized Computing. Combinatorial Optimization. Kluwer Academic Pub. 9: 843. doi:10.1007/978-1-4615-0013-1_19. ISBN 978-1-4613-4886-3.

[22] Kuperberg, Greg (2005). "डायहेड्रल हिडन सबग्रुप प्रॉब्लम के लिए एक सबएक्सपोनेंशियल-टाइम क्वांटम एल्गोरिथम". SIAM Journal on Computing. Philadelphia. 35 (1): 188. arXiv:quant-ph/0302112. doi:10.1137/s0097539703436345. ISSN 1095-7111. S2CID 15965140.

[23] Oded Regev (2004). "पॉलीनॉमियल स्पेस के साथ डायहेड्रल हिडन सबग्रुप प्रॉब्लम के लिए एक सबएक्सपोनेंशियल टाइम एल्गोरिथम". arXiv:quant-ph/0406151v1.

[24] Grohe, Martin; Neuen, Daniel (2021). "ग्राफ समाकृतिकता समस्या पर हालिया प्रगति". arXiv:2011.01366. {{cite journal}}: Cite journal requires |journal= (help)

[25] Flum, Jörg; Grohe, Martin (2006). पैरामीटरयुक्त जटिलता सिद्धांत. Springer. p. 417. ISBN 978-3-540-29952-3.

[26] Impagliazzo, R.; Paturi, R.; Zane, F. (2001). "किन समस्याओं में अत्यधिक घातीय जटिलता है?". Journal of Computer and System Sciences. 63 (4): 512–530. doi:10.1006/jcss.2001.1774.

[27] Mayr, Ernst W.; Meyer, Albert R. (1982). "क्रमविनिमेय अर्धसमूहों और बहुपद आदर्शों के लिए शब्द समस्याओं की जटिलता". Advances in Mathematics. 46 (3): 305–329. doi:10.1016/0001-8708(82)90048-2. MR 0683204.

[28] Davenport, James H.; Heintz, Joos (1988). "वास्तविक क्वांटिफायर उन्मूलन दोगुना घातीय है". Journal of Symbolic Computation. 5 (1–2): 29–35. doi:10.1016/S0747-7171(88)80004-X. MR 0949111.

[29] Collins, George E. (1975). "Quantifier elimination for real closed fields by cylindrical algebraic decomposition". In Brakhage, H. (ed.). ऑटोमेटा सिद्धांत और औपचारिक भाषाएं: दूसरा जीआई सम्मेलन, कैसरस्लॉटर्न, 20-23 मई, 1975. Lecture Notes in Computer Science. Vol. 33. Springer. pp. 134–183. doi:10.1007/3-540-07407-4_17. MR 0403962.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]