tag:blogger.com,1999:blog-43547518705497668532023-06-20T21:17:12.717-07:00blog-harianvirgosamsofihttp://www.blogger.com/profile/12794342593186572847noreply@blogger.comBlogger16125tag:blogger.com,1999:blog-4354751870549766853.post-31243991130288515962021-02-24T20:10:00.001-08:002021-02-24T20:10:29.347-08:0043)Sheikh Hasina the right choice as main guest to the Republic Day but trust the PMO to miss the obvious
<a href="https://indiarepublicday.com/"><b>India Republic Day</b></a> -- From your record 10 Chief Guests for the Republic Day Ornement in 2018 to none in 2021 is as considerably a reflection on Prime Minister Narendra Modis out of the box approach to foreign policy.
<br><br>
From your record 10 Chief Guests for the Republic Day Ornement in 2018 to none in 2021 is as considerably a reflection on Prime Minister Narendra Modis out of the box approach to foreign policy as his blind spots whilst zeroing in on an extraordinary foreign dignitary.
<br><br>
Sheikh Hasina Prime Minister of Bangladesh would have been the perfect Republic Day Chief Guest this current year for umpteen reasons nevertheless it obviously didnt occur to Modi to single her out there for the honour. I shiver to even speculate if the visionary and statesman similar to Modi is blinded through her religion or sexual category or both to pass your girlfriend up?
<br><br>
Instead of inviting United kingdom PM Boris Johnson who have ultimately chickened out Hasina should have been Modis auto choice this year as it is often the 50th anniversary of the delivery of Bangladesh in 1971 and also the 50th year of the business of diplomatic relations among New Delhi and Dhaka. Indias role in the generation of Bangladesh by mashing the Pakistani army is too well known. I have brought it up only to underline our pegs in Bangladesh. Moreover Hasina has been Indias steadfast as well as unwavering ally in Southern region Asia who has even surpassesd swords with Pakistan upon Indias behalf. Her real commitment to New Delhi is a proven and recognized fact. My friends in the Additional Affairs Ministry and the safety measures establishment tell me that that a person of the biggest priorities in our foreign policy is to make sure that Hasina somehow remains often the PM of Bangladesh which often proves how invested we have been in her.
<br><br>
Modi have a strange fixation for Initially World leaders. Last year they pulled out all stops to seize Donald Trump as the Main Guest to show his home constituency that whether it is Barrack Obama or Trump zero US President can say no to Modi. But Trump was too frightened through pollution levels in Delhi or simply too bored with Modi to accept the invitation which often resulted in an eleventh hours invite to the obnoxious as well as repulsive Jair Bolsonaro connected with Brazil. In a sense Modi experienced the last laugh though. This individual lured Trump to Ahmedabad and Delhi in March 2020 with the promise associated with Gujarati votes in the US elections! This time Modi eyed often the dishevelled Johnson who is furthermore also hard of ability to hear. It was a done offer until it suddenly fell by means of so close to January 21 that finding another Main Guest on the rebound has been well and truly not possible leaving Modi stranded.
<br><br>
Hasina has done so much for Indian that Modi keeps spending Bangladesh compliment after compliment. He recently described the latest phase of bilateral relationships as the golden era associated with India-Bangladesh ties. Modi certainly doesnt talk out of his or her hat. He means just what he says. During a 90-minute long Virtual Summit using Hasina on December teen 2020 he said: Bangladesh is a major pillar associated with Indias Neighbourhood First plan. From the very first day as PM strengthening and development of relationships with Ban
gladesh has been a specific priority for me. Hasina immediately reciprocated by calling India Bangladeshs true friend.
<br><br>
There are far too many instances of such cordial exchanges. But I became most touched by what Hasina said during a World Economical Forum meeting in 2018 in Dalian. Our relationships with India are organic. It cannot be measured by a few billion dollars associated with trade. India and Bangladesh shed blood together for any creation of my nation.
<br><br>
In Octobe
r 2020 India posted a new Large Commissioner Bikram Doraiswami who have drove to Dhaka as opposed to flying there. While visiting the Awami League headquarters upon December 23 2020 Doraiswami according to a report in Ittefaq a leading Bangladeshi newspaper said that if the Awami League isnt there Indian will be friendless in Bangladesh. If thats indeed correct doesnt Awami League soberano Hasina - who has invited Modi to Dhaka as being the Chief Guest on the event of the 50th anniversary associated with Bangladeshs independence in Walk 2021 - deserve to be the Chief Guest at our own Republic Day?samsofihttp://www.blogger.com/profile/12794342593186572847noreply@blogger.com0tag:blogger.com,1999:blog-4354751870549766853.post-13995612022307379162021-01-20T04:11:00.027-08:002021-01-20T04:11:57.187-08:00Table of common time complexities<br/><br/><br/><p>The following table summarizes some classes of commonly encountered time complexities. In the table, poly(<i>x</i>) = <i>x</i><i>O</i>(1), i.e., polynomial in <i>x</i>.
</p><table class="wikitable sortable">
<tbody><tr>
<th>Name</th>
<th>Complexity class</th>
<th>Running time (<i>T</i>(<i>n</i>))</th>
<th>Examples of running times</th>
<th>Example algorithms
</th></tr>
<tr>
<td>constant time</td>
<td></td>
<td><i>O</i>(1)</td>
<td>10</td>
<td>Finding the median value in a sorted array of numbers
<p>Calculating <span class="texhtml">(−1)<i>n</i></span>
</p>
</td></tr>
<tr>
<td>inverse Ackermann time</td>
<td></td>
<td><i>O</i>(<i>α</i>(<i>n</i>))</td>
<td></td>
<td>Amortized time per operation using a disjoint set
</td></tr>
<tr>
<td>iterated logarithmic time</td>
<td></td>
<td><i>O</i>(log<span style="vertical-align: 10%">*</span> <i>n</i>)</td>
<td></td>
<td>Distributed coloring of cycles
</td></tr>
<tr>
<td>log-logarithmic</td>
<td></td>
<td><i>O</i>(log log <i>n</i>)</td>
<td></td>
<td>Amortized time per operation using a bounded priority queue
</td></tr>
<tr>
<td>logarithmic time</td>
<td>DLOGTIME</td>
<td><i>O</i>(log <i>n</i>)</td>
<td>log <i>n</i>, log(<i>n</i>2)</td>
<td>Binary search
</td></tr>
<tr>
<td>polylogarithmic time</td>
<td></td>
<td>poly(log <i>n</i>)</td>
<td>(log <i>n</i>)2</td>
<td>
</td></tr>
<tr>
<td>fractional power</td>
<td></td>
<td><span class="texhtml"><i>O</i>(<i>n</i>c)</span> where <span class="texhtml">0 < c < 1</span></td>
<td><i>n</i>1/2, <i>n</i>2/3</td>
<td>Searching in a kd-tree
</td></tr>
<tr>
<td>linear time</td>
<td></td>
<td><i>O</i>(<i>n</i>)</td>
<td><i>n</i>, <i>2n + 5</i></td>
<td>Finding the smallest or largest item in an unsorted array, Kadane's algorithm, linear search
</td></tr>
<tr>
<td>"n log-star n" time</td>
<td></td>
<td><i>O</i>(<i>n</i> log<span style="vertical-align: 10%">*</span> <i>n</i>)</td>
<td></td>
<td>Seidel's polygon triangulation algorithm.
</td></tr>
<tr>
<td>linearithmic time</td>
<td></td>
<td><i>O</i>(<i>n</i> log <i>n</i>)</td>
<td><i>n</i> log <i>n</i>, log <i>n</i>!</td>
<td>Fastest possible comparison sort; Fast Fourier transform.
</td></tr>
<tr>
<td>quasilinear time</td>
<td></td>
<td><i>n</i> poly(log <i>n</i>)</td>
<td></td>
<td>
</td></tr>
<tr>
<td>quadratic time</td>
<td></td>
<td><i>O</i>(<i>n</i>2)</td>
<td><i>n</i>2</td>
<td>Bubble sort; Insertion sort; Direct convolution
</td></tr>
<tr>
<td>cubic time</td>
<td></td>
<td><i>O</i>(<i>n</i>3)</td>
<td><i>n</i>3</td>
<td>Naive multiplication of two <i>n</i>×<i>n</i> matrices. Calculating partial correlation.
</td></tr>
<tr>
<td>polynomial time</td>
<td>P</td>
<td>2<i>O</i>(log <i>n</i>) = poly(<i>n</i>)</td>
<td><i>n</i>2 + <i>n</i>, <i>n</i>10</td>
<td>Karmarkar's algorithm for linear programming; AKS primality test
</td></tr>
<tr>
<td>quasi-polynomial time</td>
<td>QP</td>
<td>2poly(log <i>n</i>)</td>
<td><i>n</i>log log <i>n</i>, <i>n</i>log <i>n</i></td>
<td>Best-known O(log2 <i>n</i>)-approximation algorithm for the directed Steiner tree problem.
</td></tr>
<tr>
<td>sub-exponential time<br/>(first definition)</td>
<td>SUBEXP</td>
<td><i>O</i>(2<i>n</i><i>ε</i>) for all <i>ε</i> > 0</td>
<td></td>
<td>Contains BPP unless EXPTIME (see below) equals MA.
</td></tr>
<tr>
<td>sub-exponential time<br/>(second definition)</td>
<td></td>
<td>2<i>o</i>(<i>n</i>)</td>
<td>2<i>n</i>1/3</td>
<td>Best-known algorithm for integer factorization; formerly-best algorithm for graph isomorphism
</td></tr>
<tr>
<td>exponential time<br/>(with linear exponent)</td>
<td>E</td>
<td>2<i>O</i>(<i>n</i>)</td>
<td>1.1<i>n</i>, 10<i>n</i></td>
<td>Solving the traveling salesman problem using dynamic programming
</td></tr>
<tr>
<td>exponential time</td>
<td>EXPTIME</td>
<td>2poly(<i>n</i>)</td>
<td>2<i>n</i>, 2<i>n</i>2</td>
<td>Solving matrix chain multiplication via brute-force search
</td></tr>
<tr>
<td>factorial time</td>
<td></td>
<td><i>O</i>(<i>n</i>!)</td>
<td><i>n</i>!</td>
<td>Solving the traveling salesman problem via brute-force search
</td></tr>
<tr>
<td>double exponential time</td>
<td>2-EXPTIME</td>
<td>22poly(<i>n</i>)</td>
<td>22<i>n</i></td>
<td>Deciding the truth of a given statement in Presburger arithmetic
</td></tr></tbody></table>samsofihttp://www.blogger.com/profile/12794342593186572847noreply@blogger.com0tag:blogger.com,1999:blog-4354751870549766853.post-34985830064729792712021-01-20T04:11:00.025-08:002021-01-20T04:11:52.510-08:00Constant time<br/><br/><br/><p>An algorithm is said to be <b>constant time</b> (also written as <b>O(1)</b> time) if the value of <i>T</i>(<i>n</i>) is bounded by a value that does not depend on the size of the input. For example, accessing any single element in an array takes constant time as only one operation has to be performed to locate it. In a similar manner, finding the minimal value in an array sorted in ascending order; it is the first element. However, finding the minimal value in an unordered array is not a constant time operation as scanning over each element in the array is needed in order to determine the minimal value. Hence it is a linear time operation, taking O(n) time. If the number of elements is known in advance and does not change, however, such an algorithm can still be said to run in constant time.
</p><p>Despite the name "constant time", the running time does not have to be independent of the problem size, but an upper bound for the running time has to be bounded independently of the problem size. For example, the task "exchange the values of <i>a</i> and <i>b</i> if necessary so that <i>a</i>≤<i>b</i>" is called constant time even though the time may depend on whether or not it is already true that <i>a</i> ≤ <i>b</i>. However, there is some constant <i>t</i> such that the time required is always <i>at most</i> <i>t</i>.
</p><p>Here are some examples of code fragments that run in constant time :
</p><pre>int index = 5;
int item = listindex;
<b>if</b> (condition true) <b>then</b>
perform some operation that runs in constant time
<b>else</b>
perform some other operation that runs in constant time
<b>for</b> i = 1 <b>to</b> 100
<b>for</b> j = 1 <b>to</b> 200
perform some operation that runs in constant time
</pre><p>If <i>T</i>(<i>n</i>) is O(<i>any constant value</i>), this is equivalent to and stated in standard notation as <i>T</i>(<i>n</i>) being O(1).
</p>samsofihttp://www.blogger.com/profile/12794342593186572847noreply@blogger.com0tag:blogger.com,1999:blog-4354751870549766853.post-88603164864031197082021-01-20T04:11:00.023-08:002021-01-20T04:11:48.318-08:00Logarithmic time<br/><br/><br/><p>An algorithm is said to take <b>logarithmic time</b> when <i>T</i>(<i>n</i>) = <b>O(log <i>n</i>)</b>. Since log<sub>a</sub> <i>n</i> and log<sub>b</sub> <i>n</i> are related by a constant multiplier, and such a multiplier is irrelevant to big-O classification, the standard usage for logarithmic-time algorithms is O(log <i>n</i>) regardless of the base of the logarithm appearing in the expression of <i>T</i>.
</p><p>Algorithms taking logarithmic time are commonly found in operations on binary trees or when using binary search.
</p><p>An O(log n) algorithm is considered highly efficient, as the ratio of the number of operations to the size of the input decreases and tends to zero when <i>n</i> increases. An algorithm that must access all elements of its input cannot take logarithmic time, as the time taken for reading an input of size <i>n</i> is of the order of <i>n</i>.
</p><p>An example of logarithmic time is given by dictionary search. Consider a dictionary <span class="texhtml"><i>D</i></span> which contains <i>n</i> entries, sorted by alphabetical order. We suppose that, for <span class="texhtml">1 ≤ <i>k</i> ≤ <i>n</i></span>, one may access the <span class="texhtml mvar" style="font-style:italic;">k</span>th entry of the dictionary in a constant time. Let <span class="texhtml"><i>D</i>(<i>k</i>)</span> denote this <span class="texhtml mvar" style="font-style:italic;">k</span>-th entry. Under these hypotheses, the test to see if a word <span class="texhtml mvar" style="font-style:italic;"><i>w</i></span> is in the dictionary may be done in logarithmic time: consider <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math alttext="{\displaystyle D(\lfloor n/2\rfloor ),}" xmlns="http://www.w3.org/1998/Math/MathML">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>D</mi>
<mo stretchy="false">(</mo>
<mo fence="false" stretchy="false">⌊<!-- ⌊ --></mo>
<mi>n</mi>
<mrow class="MJX-TeXAtom-ORD">
<mo>/</mo>
</mrow>
<mn>2</mn>
<mo fence="false" stretchy="false">⌋<!-- ⌋ --></mo>
<mo stretchy="false">)</mo>
<mo>,</mo>
</mstyle>
</mrow>
{\displaystyle D(\lfloor n/2\rfloor ),}
</semantics>
</math></span><img alt="{\displaystyle D(\lfloor n/2\rfloor ),}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/352c13a37e2c9bc3cded5a2df7484894bac626db" style="vertical-align: -0.838ex; width:10.165ex; height:2.843ex;"/></span> where <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math alttext="{\displaystyle \lfloor \;\rfloor }" xmlns="http://www.w3.org/1998/Math/MathML">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mo fence="false" stretchy="false">⌊<!-- ⌊ --></mo>
<mspace width="thickmathspace"></mspace>
<mo fence="false" stretchy="false">⌋<!-- ⌋ --></mo>
</mstyle>
</mrow>
{\displaystyle \lfloor \;\rfloor }
</semantics>
</math></span><img alt="\lfloor \;\rfloor " aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/8d1d99deef81d9e1b3f2757b901042a218e2322a" style="vertical-align: -0.838ex; width:2.71ex; height:2.843ex;"/></span> denotes the floor function. If <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math alttext="{\displaystyle w=D(\lfloor n/2\rfloor ),}" xmlns="http://www.w3.org/1998/Math/MathML">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>w</mi>
<mo>=</mo>
<mi>D</mi>
<mo stretchy="false">(</mo>
<mo fence="false" stretchy="false">⌊<!-- ⌊ --></mo>
<mi>n</mi>
<mrow class="MJX-TeXAtom-ORD">
<mo>/</mo>
</mrow>
<mn>2</mn>
<mo fence="false" stretchy="false">⌋<!-- ⌋ --></mo>
<mo stretchy="false">)</mo>
<mo>,</mo>
</mstyle>
</mrow>
{\displaystyle w=D(\lfloor n/2\rfloor ),}
</semantics>
</math></span><img alt="{\displaystyle w=D(\lfloor n/2\rfloor ),}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e032686e418956decefacb961a20ce19f9066572" style="vertical-align: -0.838ex; width:14.927ex; height:2.843ex;"/></span> then we are done. Else, if <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math alttext="{\displaystyle w<D(\lfloor n/2\rfloor ),}" xmlns="http://www.w3.org/1998/Math/MathML">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>w</mi>
<mo><</mo>
<mi>D</mi>
<mo stretchy="false">(</mo>
<mo fence="false" stretchy="false">⌊<!-- ⌊ --></mo>
<mi>n</mi>
<mrow class="MJX-TeXAtom-ORD">
<mo>/</mo>
</mrow>
<mn>2</mn>
<mo fence="false" stretchy="false">⌋<!-- ⌋ --></mo>
<mo stretchy="false">)</mo>
<mo>,</mo>
</mstyle>
</mrow>
{\displaystyle w<D(\lfloor n/2\rfloor ),}
</semantics>
</math></span><img alt="{\displaystyle w<D(\lfloor n/2\rfloor ),}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/1f9754ef0e147fd9074d36aab7909455a26c028d" style="vertical-align: -0.838ex; width:14.927ex; height:2.843ex;"/></span> continue the search in the same way in the left half of the dictionary, otherwise continue similarly with the right half of the dictionary. This algorithm is similar to the method often used to find an entry in a paper dictionary.
</p>samsofihttp://www.blogger.com/profile/12794342593186572847noreply@blogger.com0tag:blogger.com,1999:blog-4354751870549766853.post-65122706947528596202021-01-20T04:11:00.021-08:002021-01-20T04:11:44.363-08:00Polylogarithmic time<br/><br/><br/><p>An algorithm is said to run in <b>polylogarithmic time</b> if its time <span class="texhtml"><i>T</i>(<i>n</i>)</span> is <span class="texhtml"><i>O</i>((log <i>n</i>)<i>k</i>)</span> for some constant <i>k</i>. Another way to write this is <span class="texhtml"><i>O</i>(log<i>k</i> <i>n</i>)</span>.
</p><p>For example, matrix chain ordering can be solved in polylogarithmic time on a parallel random-access machine, and a graph can be determined to be planar in a fully dynamic way in <i>O(log3 n)</i> time per insert/delete operation.
</p>samsofihttp://www.blogger.com/profile/12794342593186572847noreply@blogger.com0tag:blogger.com,1999:blog-4354751870549766853.post-88480594619921888042021-01-20T04:11:00.019-08:002021-01-20T04:11:40.178-08:00Sub-linear time<br/><br/><br/><p>An algorithm is said to run in <b>sub-linear time</b> (often spelled <b>sublinear time</b>) if <i>T</i>(<i>n</i>) = o(<i>n</i>). In particular this includes algorithms with the time complexities defined above.
</p><p>Typical algorithms that are exact and yet run in sub-linear time use parallel processing (as the NC<sub>1</sub> matrix determinant calculation does), or alternatively have guaranteed assumptions on the input structure (as the logarithmic time binary search and many tree maintenance algorithms do). However, formal languages such as the set of all strings that have a 1-bit in the position indicated by the first log(n) bits of the string may depend on every bit of the input and yet be computable in sub-linear time.
</p><p>The specific term <i>sublinear time algorithm</i> is usually reserved to algorithms that are unlike the above in that they are run over classical serial machine models and are not allowed prior assumptions on the input. They are however allowed to be randomized, and indeed must be randomized for all but the most trivial of tasks.
</p><p>As such an algorithm must provide an answer without reading the entire input, its particulars heavily depend on the access allowed to the input. Usually for an input that is represented as a binary string <i>b</i><sub>1</sub>,...,<i>b<sub>k</sub></i> it is assumed that the algorithm can in time O(1) request and obtain the value of <i>b<sub>i</sub></i> for any <i>i</i>.
</p><p>Sub-linear time algorithms are typically randomized, and provide only approximate solutions. In fact, the property of a binary string having only zeros (and no ones) can be easily proved not to be decidable by a (non-approximate) sub-linear time algorithm. Sub-linear time algorithms arise naturally in the investigation of property testing.
</p>samsofihttp://www.blogger.com/profile/12794342593186572847noreply@blogger.com0tag:blogger.com,1999:blog-4354751870549766853.post-27891232241214350412021-01-20T04:11:00.017-08:002021-01-20T04:11:36.255-08:00Linear time<br/><br/><br/><p>An algorithm is said to take <b>linear time</b>, or <span class="texhtml"><i>O</i>(<i>n</i>)</span> time, if its time complexity is <span class="texhtml"><i>O</i>(<i>n</i>)</span>. Informally, this means that the running time increases at most linearly with the size of the input. More precisely, this means that there is a constant <span class="texhtml mvar" style="font-style:italic;">c</span> such that the running time is at most <span class="texhtml"><i>cn</i></span> for every input of size <span class="texhtml mvar" style="font-style:italic;">n</span>. For example, a procedure that adds up all elements of a list requires time proportional to the length of the list, if the adding time is constant, or, at least, bounded by a constant.
</p><p>Linear time is the best possible time complexity in situations where the algorithm has to sequentially read its entire input. Therefore, much research has been invested into discovering algorithms exhibiting linear time or, at least, nearly linear time. This research includes both software and hardware methods. There are several hardware technologies which exploit parallelism to provide this. An example is content-addressable memory. This concept of linear time is used in string matching algorithms such as the Boyer–Moore algorithm and Ukkonen's algorithm.
</p>samsofihttp://www.blogger.com/profile/12794342593186572847noreply@blogger.com0tag:blogger.com,1999:blog-4354751870549766853.post-57438558039331063052021-01-20T04:11:00.015-08:002021-01-20T04:11:31.485-08:00 Quasilinear time<br/><br/><br/><p>An algorithm is said to run in <b>quasilinear time</b> (also referred to as <b>log-linear time</b>) if <i>T</i>(<i>n</i>) = <b>O(<i>n</i> log<i>k</i> <i>n</i>)</b> for some positive constant <i>k</i>; <b>linearithmic time</b> is the case <i>k</i> = 1. Using soft O notation these algorithms are Õ(<i>n</i>). Quasilinear time algorithms are also O(<i>n</i>1+ε) for every constant ε > 0, and thus run faster than any polynomial time algorithm whose time bound includes a term <i>n</i><i>c</i> for any <i>c</i> > 1.
</p><p>Algorithms which run in quasilinear time include:
</p><ul><li>In-place merge sort, O(<i>n</i> log<i>2</i> <i>n</i>)</li>
<li>Quicksort, O(<i>n</i> log <i>n</i>), in its randomized version, has a running time that is O(<i>n</i> log <i>n</i>) in expectation on the worst-case input. Its non-randomized version has an O(<i>n</i> log <i>n</i>) running time only when considering average case complexity.</li>
<li>Heapsort, O(<i>n</i> log <i>n</i>), merge sort, introsort, binary tree sort, smoothsort, patience sorting, etc. in the worst case</li>
<li>Fast Fourier transforms, O(<i>n</i> log <i>n</i>)</li>
<li>Monge array calculation, O(<i>n</i> log <i>n</i>)</li></ul><p>In many cases, the <i>n</i> · log <i>n</i> running time is simply the result of performing a Θ(log <i>n</i>) operation <i>n</i> times (for the notation, see Big O notation § Family of Bachmann–Landau notations). For example, binary tree sort creates a binary tree by inserting each element of the <i>n</i>-sized array one by one. Since the insert operation on a self-balancing binary search tree takes <i>O</i>(log <i>n</i>) time, the entire algorithm takes <i>O</i>(<i>n</i> log <i>n</i>) time.
</p><p>Comparison sorts require at least <i>Ω</i>(<i>n</i> log <i>n</i>) comparisons in the worst case because log(<i>n</i>!) = Θ(<i>n</i> log <i>n</i>), by Stirling's approximation. They also frequently arise from the recurrence relation <i>T</i>(<i>n</i>) = 2<i>T</i>(<i>n</i>/2) + <i>O</i>(<i>n</i>).
</p>samsofihttp://www.blogger.com/profile/12794342593186572847noreply@blogger.com0tag:blogger.com,1999:blog-4354751870549766853.post-52503134404407132021-01-20T04:11:00.013-08:002021-01-20T04:11:26.721-08:00Sub-quadratic time<br/><br/><br/><p>An algorithm is said to be <b>subquadratic time</b> if <i>T</i>(<i>n</i>) = o(<i>n</i>2).
</p><p>For example, simple, comparison-based sorting algorithms are quadratic (e.g. insertion sort), but more advanced algorithms can be found that are subquadratic (e.g. shell sort). No general-purpose sorts run in linear time, but the change from quadratic to sub-quadratic is of great practical importance.
</p>samsofihttp://www.blogger.com/profile/12794342593186572847noreply@blogger.com0tag:blogger.com,1999:blog-4354751870549766853.post-12897227031704359782021-01-20T04:11:00.011-08:002021-01-20T04:11:22.687-08:00Polynomial time<br/><br/><br/><p>An algorithm is said to be of <b>polynomial time</b> if its running time is upper bounded by a polynomial expression in the size of the input for the algorithm, i.e., <i>T</i>(<i>n</i>) = O(<i>n</i><i>k</i>) for some positive constant <i>k</i>. Problems for which a deterministic polynomial time algorithm exists belong to the complexity class <b>P</b>, which is central in the field of computational complexity theory. Cobham's thesis states that polynomial time is a synonym for "tractable", "feasible", "efficient", or "fast".
</p><p>Some examples of polynomial time algorithms:
</p><ul><li>The selection sort sorting algorithm on <i>n</i> integers performs <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math alttext="{\displaystyle An^{2}}" xmlns="http://www.w3.org/1998/Math/MathML">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>A</mi>
<msup>
<mi>n</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>2</mn>
</mrow>
</msup>
</mstyle>
</mrow>
{\displaystyle An^{2}}
</semantics>
</math></span><img alt="An^{2}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2796e53b94e7bd410c057a6d425c4923ed580156" style="vertical-align: -0.338ex; width:4.192ex; height:2.676ex;"/></span> operations for some constant <i>A</i>. Thus it runs in time <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math alttext="{\displaystyle O(n^{2})}" xmlns="http://www.w3.org/1998/Math/MathML">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>O</mi>
<mo stretchy="false">(</mo>
<msup>
<mi>n</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>2</mn>
</mrow>
</msup>
<mo stretchy="false">)</mo>
</mstyle>
</mrow>
{\displaystyle O(n^{2})}
</semantics>
</math></span><img alt="O(n^{2})" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/6cd9594a16cb898b8f2a2dff9227a385ec183392" style="vertical-align: -0.838ex; width:6.032ex; height:3.176ex;"/></span> and is a polynomial time algorithm.</li>
<li>All the basic arithmetic operations (addition, subtraction, multiplication, division, and comparison) can be done in polynomial time.</li>
<li>Maximum matchings in graphs can be found in polynomial time.</li></ul><h3><span class="mw-headline" id="Strongly_and_weakly_polynomial_time">Strongly and weakly polynomial time</span><span class="mw-editsection"><span class="mw-editsection-bracket"></span>edit<span class="mw-editsection-bracket"></span></span></h3><p>In some contexts, especially in optimization, one differentiates between <b>strongly polynomial time</b> and <b>weakly polynomial time</b> algorithms. These two concepts are only relevant if the inputs to the algorithms consist of integers.
</p><p>Strongly polynomial time is defined in the arithmetic model of computation. In this model of computation the basic arithmetic operations (addition, subtraction, multiplication, division, and comparison) take a unit time step to perform, regardless of the sizes of the operands. The algorithm runs in strongly polynomial time if
</p><ol><li>the number of operations in the arithmetic model of computation is bounded by a polynomial in the number of integers in the input instance; and</li>
<li>the space used by the algorithm is bounded by a polynomial in the size of the input.</li></ol><p>Any algorithm with these two properties can be converted to a polynomial time algorithm by replacing the arithmetic operations by suitable algorithms for performing the arithmetic operations on a Turing machine. If the second of the above requirements is not met, then this is not true anymore. Given the integer <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math alttext="{\displaystyle 2^{n}}" xmlns="http://www.w3.org/1998/Math/MathML">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msup>
<mn>2</mn>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
</mrow>
</msup>
</mstyle>
</mrow>
{\displaystyle 2^{n}}
</semantics>
</math></span><img alt="2^{n}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/8226f30650ee4fe4e640c6d2798127e80e9c160d" style="vertical-align: -0.338ex; width:2.381ex; height:2.343ex;"/></span> (which takes up space proportional to <i>n</i> in the Turing machine model), it is possible to compute <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math alttext="{\displaystyle 2^{2^{n}}}" xmlns="http://www.w3.org/1998/Math/MathML">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msup>
<mn>2</mn>
<mrow class="MJX-TeXAtom-ORD">
<msup>
<mn>2</mn>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
</mrow>
</msup>
</mrow>
</msup>
</mstyle>
</mrow>
{\displaystyle 2^{2^{n}}}
</semantics>
</math></span><img alt="2^{2^{n}}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/6bcc9417763ad5d68870290ddaa2ca025ffdaf85" style="vertical-align: -0.338ex; width:3.182ex; height:2.676ex;"/></span>
with <i>n</i> multiplications using repeated squaring. However, the space used to represent <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math alttext="{\displaystyle 2^{2^{n}}}" xmlns="http://www.w3.org/1998/Math/MathML">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msup>
<mn>2</mn>
<mrow class="MJX-TeXAtom-ORD">
<msup>
<mn>2</mn>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
</mrow>
</msup>
</mrow>
</msup>
</mstyle>
</mrow>
{\displaystyle 2^{2^{n}}}
</semantics>
</math></span><img alt="2^{2^{n}}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/6bcc9417763ad5d68870290ddaa2ca025ffdaf85" style="vertical-align: -0.338ex; width:3.182ex; height:2.676ex;"/></span> is proportional to <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math alttext="{\displaystyle 2^{n}}" xmlns="http://www.w3.org/1998/Math/MathML">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msup>
<mn>2</mn>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
</mrow>
</msup>
</mstyle>
</mrow>
{\displaystyle 2^{n}}
</semantics>
</math></span><img alt="2^{n}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/8226f30650ee4fe4e640c6d2798127e80e9c160d" style="vertical-align: -0.338ex; width:2.381ex; height:2.343ex;"/></span>, and thus exponential rather than polynomial in the space used to represent the input. Hence, it is not possible to carry out this computation in polynomial time on a Turing machine, but it is possible to compute it by polynomially many arithmetic operations.
</p><p>Conversely, there are algorithms that run in a number of Turing machine steps bounded by a polynomial in the length of binary-encoded input, but do not take a number of arithmetic operations bounded by a polynomial in the number of input numbers. The Euclidean algorithm for computing the greatest common divisor of two integers is one example. Given two integers <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math alttext="{\displaystyle a}" xmlns="http://www.w3.org/1998/Math/MathML">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>a</mi>
</mstyle>
</mrow>
{\displaystyle a}
</semantics>
</math></span><img alt="a" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ffd2487510aa438433a2579450ab2b3d557e5edc" style="vertical-align: -0.338ex; width:1.23ex; height:1.676ex;"/></span> and <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math alttext="{\displaystyle b}" xmlns="http://www.w3.org/1998/Math/MathML">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>b</mi>
</mstyle>
</mrow>
{\displaystyle b}
</semantics>
</math></span><img alt="b" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f11423fbb2e967f986e36804a8ae4271734917c3" style="vertical-align: -0.338ex; width:0.998ex; height:2.176ex;"/></span>, the algorithm
performs <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math alttext="{\displaystyle O(\log \ a+\log \ b)}" xmlns="http://www.w3.org/1998/Math/MathML">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>O</mi>
<mo stretchy="false">(</mo>
<mi>log</mi>
<mo><!-- --></mo>
<mtext> </mtext>
<mi>a</mi>
<mo>+</mo>
<mi>log</mi>
<mo><!-- --></mo>
<mtext> </mtext>
<mi>b</mi>
<mo stretchy="false">)</mo>
</mstyle>
</mrow>
{\displaystyle O(\log \ a+\log \ b)}
</semantics>
</math></span><img alt="{\displaystyle O(\log \ a+\log \ b)}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b2ecb5ad9cd41f86759d595c1f7ad4a2afc31720" style="vertical-align: -0.838ex; width:16.529ex; height:2.843ex;"/></span> arithmetic operations on numbers with
at most <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math alttext="{\displaystyle O(\log \ a+\log \ b)}" xmlns="http://www.w3.org/1998/Math/MathML">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>O</mi>
<mo stretchy="false">(</mo>
<mi>log</mi>
<mo><!-- --></mo>
<mtext> </mtext>
<mi>a</mi>
<mo>+</mo>
<mi>log</mi>
<mo><!-- --></mo>
<mtext> </mtext>
<mi>b</mi>
<mo stretchy="false">)</mo>
</mstyle>
</mrow>
{\displaystyle O(\log \ a+\log \ b)}
</semantics>
</math></span><img alt="{\displaystyle O(\log \ a+\log \ b)}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b2ecb5ad9cd41f86759d595c1f7ad4a2afc31720" style="vertical-align: -0.838ex; width:16.529ex; height:2.843ex;"/></span> bits.
At the same time, the number of arithmetic operations cannot be bounded by the number of integers in the input (which is constant in this case, there are always only two integers in the input). Due to the latter observation, the algorithm does not run in strongly polynomial time. Its real running time depends on the magnitudes of <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math alttext="{\displaystyle a}" xmlns="http://www.w3.org/1998/Math/MathML">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>a</mi>
</mstyle>
</mrow>
{\displaystyle a}
</semantics>
</math></span><img alt="a" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ffd2487510aa438433a2579450ab2b3d557e5edc" style="vertical-align: -0.338ex; width:1.23ex; height:1.676ex;"/></span> and <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math alttext="{\displaystyle b}" xmlns="http://www.w3.org/1998/Math/MathML">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>b</mi>
</mstyle>
</mrow>
{\displaystyle b}
</semantics>
</math></span><img alt="b" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f11423fbb2e967f986e36804a8ae4271734917c3" style="vertical-align: -0.338ex; width:0.998ex; height:2.176ex;"/></span> and not only on the number of integers in the input.
</p><p>An algorithm that runs in polynomial time but that is not strongly polynomial is said to run in <b>weakly polynomial time</b>.
A well-known example of a problem for which a weakly polynomial-time algorithm is known, but is not known to admit a strongly polynomial-time algorithm,
is linear programming. Weakly-polynomial time should not be confused with pseudo-polynomial time.
</p><h3><span class="mw-headline" id="Complexity_classes">Complexity classes</span><span class="mw-editsection"><span class="mw-editsection-bracket"></span>edit<span class="mw-editsection-bracket"></span></span></h3><p>The concept of polynomial time leads to several complexity classes in computational complexity theory. Some important classes defined using polynomial time are the following.
</p><table class="wikitable">
<tbody><tr>
<td><b>P</b></td>
<td>The complexity class of decision problems that can be solved on a deterministic Turing machine in polynomial time
</td></tr>
<tr>
<td><b>NP</b></td>
<td>The complexity class of decision problems that can be solved on a non-deterministic Turing machine in polynomial time
</td></tr>
<tr>
<td><b>ZPP</b></td>
<td>The complexity class of decision problems that can be solved with zero error on a probabilistic Turing machine in polynomial time
</td></tr>
<tr>
<td><b>RP</b></td>
<td>The complexity class of decision problems that can be solved with 1-sided error on a probabilistic Turing machine in polynomial time.
</td></tr>
<tr>
<td><b>BPP</b></td>
<td>The complexity class of decision problems that can be solved with 2-sided error on a probabilistic Turing machine in polynomial time
</td></tr>
<tr>
<td><b>BQP</b></td>
<td>The complexity class of decision problems that can be solved with 2-sided error on a quantum Turing machine in polynomial time
</td></tr></tbody></table><p>P is the smallest time-complexity class on a deterministic machine which is robust in terms of machine model changes. (For example, a change from a single-tape Turing machine to a multi-tape machine can lead to a quadratic speedup, but any algorithm that runs in polynomial time under one model also does so on the other.) Any given abstract machine will have a complexity class corresponding to the problems which can be solved in polynomial time on that machine.
</p>samsofihttp://www.blogger.com/profile/12794342593186572847noreply@blogger.com0tag:blogger.com,1999:blog-4354751870549766853.post-81704529371964363432021-01-20T04:11:00.009-08:002021-01-20T04:11:18.413-08:00Superpolynomial time<br/><br/><br/><p>An algorithm is said to take <b>superpolynomial time</b> if <i>T</i>(<i>n</i>) is not bounded above by any polynomial. Using little omega notation, it is ω(<i>n</i><i>c</i>) time for all constants <i>c</i>, where <i>n</i> is the input parameter, typically the number of bits in the input.
</p><p>For example, an algorithm that runs for 2<i>n</i> steps on an input of size <i>n</i> requires superpolynomial time (more specifically, exponential time).
</p><p>An algorithm that uses exponential resources is clearly superpolynomial, but some algorithms are only very weakly superpolynomial. For example, the Adleman–Pomerance–Rumely primality test runs for <i>n</i>O(log log <i>n</i>) time on <i>n</i>-bit inputs; this grows faster than any polynomial for large enough <i>n</i>, but the input size must become impractically large before it cannot be dominated by a polynomial with small degree.
</p><p>An algorithm that requires superpolynomial time lies outside the complexity class <b>P</b>. Cobham's thesis posits that these algorithms are impractical, and in many cases they are. Since the P versus NP problem is unresolved, it is unknown whether NP-complete problems require superpolynomial time.
</p>samsofihttp://www.blogger.com/profile/12794342593186572847noreply@blogger.com0tag:blogger.com,1999:blog-4354751870549766853.post-82712217404606584352021-01-20T04:11:00.007-08:002021-01-20T04:11:14.430-08:00Quasi-polynomial time<br/><br/><br/><p><b>Quasi-polynomial time</b> algorithms are algorithms that run longer than polynomial time, yet not so long as to be exponential time. The worst case running time of a quasi-polynomial time algorithm is <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math alttext="{\displaystyle 2^{O((\log n)^{c})}}" xmlns="http://www.w3.org/1998/Math/MathML">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msup>
<mn>2</mn>
<mrow class="MJX-TeXAtom-ORD">
<mi>O</mi>
<mo stretchy="false">(</mo>
<mo stretchy="false">(</mo>
<mi>log</mi>
<mo><!-- --></mo>
<mi>n</mi>
<msup>
<mo stretchy="false">)</mo>
<mrow class="MJX-TeXAtom-ORD">
<mi>c</mi>
</mrow>
</msup>
<mo stretchy="false">)</mo>
</mrow>
</msup>
</mstyle>
</mrow>
{\displaystyle 2^{O((\log n)^{c})}}
</semantics>
</math></span><img alt="2^{O((\log n)^{c})}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4510ae6dc14f73fdf53a8237b01ed9eb08cf8ef3" style="vertical-align: -0.338ex; width:9.424ex; height:2.843ex;"/></span> for some fixed <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math alttext="{\displaystyle c>0}" xmlns="http://www.w3.org/1998/Math/MathML">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>c</mi>
<mo>></mo>
<mn>0</mn>
</mstyle>
</mrow>
{\displaystyle c>0}
</semantics>
</math></span><img alt="c>0" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2ba126f626d61752f62eaacaf11761a54de4dc84" style="vertical-align: -0.338ex; width:5.268ex; height:2.176ex;"/></span>. For <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math alttext="{\displaystyle c=1}" xmlns="http://www.w3.org/1998/Math/MathML">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>c</mi>
<mo>=</mo>
<mn>1</mn>
</mstyle>
</mrow>
{\displaystyle c=1}
</semantics>
</math></span><img alt="c=1" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/3e3467f9e219a5ea38a30da5c3a02c2c23f61a79" style="vertical-align: -0.338ex; width:5.268ex; height:2.176ex;"/></span> we get a polynomial time algorithm, for <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math alttext="{\displaystyle c<1}" xmlns="http://www.w3.org/1998/Math/MathML">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>c</mi>
<mo><</mo>
<mn>1</mn>
</mstyle>
</mrow>
{\displaystyle c<1}
</semantics>
</math></span><img alt="{\displaystyle c<1}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d8f310fc940b3622eefb2bb82bb2cb2a049a60c2" style="vertical-align: -0.338ex; width:5.268ex; height:2.176ex;"/></span> we get a sub-linear time algorithm.
</p><p>Quasi-polynomial time algorithms typically arise in reductions from an NP-hard problem to another problem. For example, one can take an instance of an NP hard problem, say 3SAT, and convert it to an instance of another problem B, but the size of the instance becomes <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math alttext="{\displaystyle 2^{O((\log n)^{c})}}" xmlns="http://www.w3.org/1998/Math/MathML">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msup>
<mn>2</mn>
<mrow class="MJX-TeXAtom-ORD">
<mi>O</mi>
<mo stretchy="false">(</mo>
<mo stretchy="false">(</mo>
<mi>log</mi>
<mo><!-- --></mo>
<mi>n</mi>
<msup>
<mo stretchy="false">)</mo>
<mrow class="MJX-TeXAtom-ORD">
<mi>c</mi>
</mrow>
</msup>
<mo stretchy="false">)</mo>
</mrow>
</msup>
</mstyle>
</mrow>
{\displaystyle 2^{O((\log n)^{c})}}
</semantics>
</math></span><img alt="2^{O((\log n)^{c})}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4510ae6dc14f73fdf53a8237b01ed9eb08cf8ef3" style="vertical-align: -0.338ex; width:9.424ex; height:2.843ex;"/></span>. In that case, this reduction does not prove that problem B is NP-hard; this reduction only shows that there is no polynomial time algorithm for B unless there is a quasi-polynomial time algorithm for 3SAT (and thus all of NP). Similarly, there are some problems for which we know quasi-polynomial time algorithms, but no polynomial time algorithm is known. Such problems arise in approximation algorithms; a famous example is the directed Steiner tree problem, for which there is a quasi-polynomial time approximation algorithm achieving an approximation factor of <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math alttext="{\displaystyle O(\log ^{3}n)}" xmlns="http://www.w3.org/1998/Math/MathML">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>O</mi>
<mo stretchy="false">(</mo>
<msup>
<mi>log</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>3</mn>
</mrow>
</msup>
<mo><!-- --></mo>
<mi>n</mi>
<mo stretchy="false">)</mo>
</mstyle>
</mrow>
{\displaystyle O(\log ^{3}n)}
</semantics>
</math></span><img alt="O(\log ^{3}n)" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a7f77c48b4c4e7b58b75244a9c512673896f6236" style="vertical-align: -0.838ex; width:9.39ex; height:3.176ex;"/></span> (n being the number of vertices), but showing the existence of such a polynomial time algorithm is an open problem.
</p><p>Other computational problems with quasi-polynomial time solutions but no known polynomial time solution include the planted clique problem in which the goal is to find a large clique in the union of a clique and a random graph. Although quasi-polynomially solvable, it has been conjectured that the planted clique problem has no polynomial time solution; this planted clique conjecture has been used as a computational hardness assumption to prove the difficulty of several other problems in computational game theory, property testing, and machine learning.
</p><p>The complexity class <b>QP</b> consists of all problems that have quasi-polynomial time algorithms. It can be defined in terms of DTIME as follows.
</p><dl><dd><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math alttext="{\displaystyle {\mbox{QP}}=\bigcup _{c\in \mathbb {N} }{\mbox{DTIME}}(2^{(\log n)^{c}})}" xmlns="http://www.w3.org/1998/Math/MathML">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="false" scriptlevel="0">
<mtext>QP</mtext>
</mstyle>
</mrow>
<mo>=</mo>
<munder>
<mo>⋃<!-- ⋃ --></mo>
<mrow class="MJX-TeXAtom-ORD">
<mi>c</mi>
<mo>∈<!-- ∈ --></mo>
<mrow class="MJX-TeXAtom-ORD">
<mi mathvariant="double-struck">N</mi>
</mrow>
</mrow>
</munder>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="false" scriptlevel="0">
<mtext>DTIME</mtext>
</mstyle>
</mrow>
<mo stretchy="false">(</mo>
<msup>
<mn>2</mn>
<mrow class="MJX-TeXAtom-ORD">
<mo stretchy="false">(</mo>
<mi>log</mi>
<mo><!-- --></mo>
<mi>n</mi>
<msup>
<mo stretchy="false">)</mo>
<mrow class="MJX-TeXAtom-ORD">
<mi>c</mi>
</mrow>
</msup>
</mrow>
</msup>
<mo stretchy="false">)</mo>
</mstyle>
</mrow>
{\displaystyle {\mbox{QP}}=\bigcup _{c\in \mathbb {N} }{\mbox{DTIME}}(2^{(\log n)^{c}})}
</semantics>
</math></span><img alt="{\mbox{QP}}=\bigcup _{c\in \mathbb {N} }{\mbox{DTIME}}(2^{(\log n)^{c}})" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/95d208d25e852d185d236076977329095da9d089" style="vertical-align: -3.171ex; width:26.579ex; height:5.676ex;"/></span></dd></dl><h3><span class="mw-headline" id="Relation_to_NP-complete_problems">Relation to NP-complete problems</span><span class="mw-editsection"><span class="mw-editsection-bracket"></span>edit<span class="mw-editsection-bracket"></span></span></h3><p>In complexity theory, the unsolved P versus NP problem asks if all problems in NP have polynomial-time algorithms. All the best-known algorithms for NP-complete problems like 3SAT etc. take exponential time. Indeed, it is conjectured for many natural NP-complete problems that they do not have sub-exponential time algorithms. Here "sub-exponential time" is taken to mean the second definition presented below. (On the other hand, many graph problems represented in the natural way by adjacency matrices are solvable in subexponential time simply because the size of the input is square of the number of vertices.) This conjecture (for the k-SAT problem) is known as the exponential time hypothesis. Since it is conjectured that NP-complete problems do not have quasi-polynomial time algorithms, some inapproximability results in the field of approximation algorithms make the assumption that NP-complete problems do not have quasi-polynomial time algorithms. For example, see the known inapproximability results for the set cover problem.
</p>samsofihttp://www.blogger.com/profile/12794342593186572847noreply@blogger.com0tag:blogger.com,1999:blog-4354751870549766853.post-81665475168255947212021-01-20T04:11:00.005-08:002021-01-20T04:11:10.170-08:00Sub-exponential time<br/><br/><br/><p>The term <b>sub-exponential time</b> is used to express that the running time of some algorithm may grow faster than any polynomial but is still significantly smaller than an exponential. In this sense, problems that have sub-exponential time algorithms are somewhat more tractable than those that only have exponential algorithms. The precise definition of "sub-exponential" is not generally agreed upon, and we list the two most widely used ones below.
</p><h3><span class="mw-headline" id="First_definition">First definition</span><span class="mw-editsection"><span class="mw-editsection-bracket"></span>edit<span class="mw-editsection-bracket"></span></span></h3><p>A problem is said to be sub-exponential time solvable if it can be solved in running times whose logarithms grow smaller than any given polynomial. More precisely, a problem is in sub-exponential time if for every ε > 0 there exists an algorithm which solves the problem in time O(2nε). The set of all such problems is the complexity class <b>SUBEXP</b> which can be defined in terms of DTIME as follows.
</p><dl><dd><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math alttext="{\displaystyle {\text{SUBEXP}}=\bigcap _{\varepsilon >0}{\text{DTIME}}\left(2^{n^{\varepsilon }}\right)}" xmlns="http://www.w3.org/1998/Math/MathML">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mtext>SUBEXP</mtext>
</mrow>
<mo>=</mo>
<munder>
<mo>⋂<!-- ⋂ --></mo>
<mrow class="MJX-TeXAtom-ORD">
<mi>ε<!-- ε --></mi>
<mo>></mo>
<mn>0</mn>
</mrow>
</munder>
<mrow class="MJX-TeXAtom-ORD">
<mtext>DTIME</mtext>
</mrow>
<mrow>
<mo>(</mo>
<msup>
<mn>2</mn>
<mrow class="MJX-TeXAtom-ORD">
<msup>
<mi>n</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>ε<!-- ε --></mi>
</mrow>
</msup>
</mrow>
</msup>
<mo>)</mo>
</mrow>
</mstyle>
</mrow>
{\displaystyle {\text{SUBEXP}}=\bigcap _{\varepsilon >0}{\text{DTIME}}\left(2^{n^{\varepsilon }}\right)}
</semantics>
</math></span><img alt="{\text{SUBEXP}}=\bigcap _{\varepsilon >0}{\text{DTIME}}\left(2^{n^{\varepsilon }}\right)" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4250b13f4892da1b3905e37beee2070232690b3f" style="vertical-align: -3.005ex; width:30.279ex; height:6.009ex;"/></span></dd></dl><p>This notion of sub-exponential is non-uniform in terms of ε in the sense that ε is not part of the input and each ε may have its own algorithm for the problem.
</p><h3><span class="mw-headline" id="Second_definition">Second definition</span><span class="mw-editsection"><span class="mw-editsection-bracket"></span>edit<span class="mw-editsection-bracket"></span></span></h3><p>Some authors define sub-exponential time as running times in 2o(<i>n</i>). This definition allows larger running times than the first definition of sub-exponential time. An example of such a sub-exponential time algorithm is the best-known classical algorithm for integer factorization, the general number field sieve, which runs in time about <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math alttext="{\displaystyle 2^{{\tilde {O}}(n^{1/3})}}" xmlns="http://www.w3.org/1998/Math/MathML">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msup>
<mn>2</mn>
<mrow class="MJX-TeXAtom-ORD">
<mrow class="MJX-TeXAtom-ORD">
<mrow class="MJX-TeXAtom-ORD">
<mover>
<mi>O</mi>
<mo stretchy="false">~<!-- ~ --></mo>
</mover>
</mrow>
</mrow>
<mo stretchy="false">(</mo>
<msup>
<mi>n</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>1</mn>
<mrow class="MJX-TeXAtom-ORD">
<mo>/</mo>
</mrow>
<mn>3</mn>
</mrow>
</msup>
<mo stretchy="false">)</mo>
</mrow>
</msup>
</mstyle>
</mrow>
{\displaystyle 2^{{\tilde {O}}(n^{1/3})}}
</semantics>
</math></span><img alt="2^{{\tilde {O}}(n^{1/3})}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/30d319f41f6fb8ab309bf15ad8a64c870cb52021" style="vertical-align: -0.338ex; width:7.08ex; height:3.176ex;"/></span>, where the length of the input is <i>n</i>. Another example is the graph isomorphism problem, where Luks's algorithm runs in time <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math alttext="{\displaystyle 2^{O({\sqrt {n\log n}})}}" xmlns="http://www.w3.org/1998/Math/MathML">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msup>
<mn>2</mn>
<mrow class="MJX-TeXAtom-ORD">
<mi>O</mi>
<mo stretchy="false">(</mo>
<mrow class="MJX-TeXAtom-ORD">
<msqrt>
<mi>n</mi>
<mi>log</mi>
<mo><!-- --></mo>
<mi>n</mi>
</msqrt>
</mrow>
<mo stretchy="false">)</mo>
</mrow>
</msup>
</mstyle>
</mrow>
{\displaystyle 2^{O({\sqrt {n\log n}})}}
</semantics>
</math></span><img alt="{\displaystyle 2^{O({\sqrt {n\log n}})}}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d85744ae3b34f61e6e81a3955290e95dbde5a2ad" style="vertical-align: -0.338ex; width:10.419ex; height:3.009ex;"/></span>. (In 2015–2017, Babai reduced the complexity of this problem to quasi-polynomial time.)
</p><p>It makes a difference whether the algorithm is allowed to be sub-exponential in the size of the instance, the number of vertices, or the number of edges. In parameterized complexity, this difference is made explicit by considering pairs <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math alttext="{\displaystyle (L,k)}" xmlns="http://www.w3.org/1998/Math/MathML">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mo stretchy="false">(</mo>
<mi>L</mi>
<mo>,</mo>
<mi>k</mi>
<mo stretchy="false">)</mo>
</mstyle>
</mrow>
{\displaystyle (L,k)}
</semantics>
</math></span><img alt="(L,k)" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/60912d6e9f29e343e9e77d28e3a19ede88d9d655" style="vertical-align: -0.838ex; width:5.637ex; height:2.843ex;"/></span> of decision problems and parameters <i>k</i>. <b>SUBEPT</b> is the class of all parameterized problems that run in time sub-exponential in <i>k</i> and polynomial in the input size <i>n</i>:
</p><dl><dd><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math alttext="{\displaystyle {\text{SUBEPT}}={\text{DTIME}}\left(2^{o(k)}\cdot {\text{poly}}(n)\right).}" xmlns="http://www.w3.org/1998/Math/MathML">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mtext>SUBEPT</mtext>
</mrow>
<mo>=</mo>
<mrow class="MJX-TeXAtom-ORD">
<mtext>DTIME</mtext>
</mrow>
<mrow>
<mo>(</mo>
<mrow>
<msup>
<mn>2</mn>
<mrow class="MJX-TeXAtom-ORD">
<mi>o</mi>
<mo stretchy="false">(</mo>
<mi>k</mi>
<mo stretchy="false">)</mo>
</mrow>
</msup>
<mo>⋅<!-- ⋅ --></mo>
<mrow class="MJX-TeXAtom-ORD">
<mtext>poly</mtext>
</mrow>
<mo stretchy="false">(</mo>
<mi>n</mi>
<mo stretchy="false">)</mo>
</mrow>
<mo>)</mo>
</mrow>
<mo>.</mo>
</mstyle>
</mrow>
{\displaystyle {\text{SUBEPT}}={\text{DTIME}}\left(2^{o(k)}\cdot {\text{poly}}(n)\right).}
</semantics>
</math></span><img alt="{\text{SUBEPT}}={\text{DTIME}}\left(2^{o(k)}\cdot {\text{poly}}(n)\right)." aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ff05fe27e749e87ad729180e2538feb7414883e8" style="vertical-align: -1.838ex; width:38.367ex; height:4.843ex;"/></span></dd></dl><p>More precisely, SUBEPT is the class of all parameterized problems <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math alttext="{\displaystyle (L,k)}" xmlns="http://www.w3.org/1998/Math/MathML">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mo stretchy="false">(</mo>
<mi>L</mi>
<mo>,</mo>
<mi>k</mi>
<mo stretchy="false">)</mo>
</mstyle>
</mrow>
{\displaystyle (L,k)}
</semantics>
</math></span><img alt="(L,k)" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/60912d6e9f29e343e9e77d28e3a19ede88d9d655" style="vertical-align: -0.838ex; width:5.637ex; height:2.843ex;"/></span> for which there is a computable function <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math alttext="{\displaystyle f:\mathbb {N} \to \mathbb {N} }" xmlns="http://www.w3.org/1998/Math/MathML">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>f</mi>
<mo>:</mo>
<mrow class="MJX-TeXAtom-ORD">
<mi mathvariant="double-struck">N</mi>
</mrow>
<mo stretchy="false">→<!-- → --></mo>
<mrow class="MJX-TeXAtom-ORD">
<mi mathvariant="double-struck">N</mi>
</mrow>
</mstyle>
</mrow>
{\displaystyle f:\mathbb {N} \to \mathbb {N} }
</semantics>
</math></span><img alt="f:\mathbb {N} \to \mathbb {N} " aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/dfa847e103c9e2e5075b1b510f67aad8ceae9349" style="vertical-align: -0.671ex; width:10.186ex; height:2.509ex;"/></span> with <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math alttext="{\displaystyle f\in o(k)}" xmlns="http://www.w3.org/1998/Math/MathML">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>f</mi>
<mo>∈<!-- ∈ --></mo>
<mi>o</mi>
<mo stretchy="false">(</mo>
<mi>k</mi>
<mo stretchy="false">)</mo>
</mstyle>
</mrow>
{\displaystyle f\in o(k)}
</semantics>
</math></span><img alt="f\in o(k)" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ea31b6df475b663254eeea2570f974d8ce662741" style="vertical-align: -0.838ex; width:8.267ex; height:2.843ex;"/></span> and an algorithm that decides <i>L</i> in time <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math alttext="{\displaystyle 2^{f(k)}\cdot {\text{poly}}(n)}" xmlns="http://www.w3.org/1998/Math/MathML">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msup>
<mn>2</mn>
<mrow class="MJX-TeXAtom-ORD">
<mi>f</mi>
<mo stretchy="false">(</mo>
<mi>k</mi>
<mo stretchy="false">)</mo>
</mrow>
</msup>
<mo>⋅<!-- ⋅ --></mo>
<mrow class="MJX-TeXAtom-ORD">
<mtext>poly</mtext>
</mrow>
<mo stretchy="false">(</mo>
<mi>n</mi>
<mo stretchy="false">)</mo>
</mstyle>
</mrow>
{\displaystyle 2^{f(k)}\cdot {\text{poly}}(n)}
</semantics>
</math></span><img alt="2^{f(k)}\cdot {\text{poly}}(n)" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e830c3a9cf201dda30b0a6126e1cf7b7c66569a7" style="vertical-align: -0.838ex; width:13.647ex; height:3.343ex;"/></span>.
</p><h4><span class="mw-headline" id="Exponential_time_hypothesis">Exponential time hypothesis</span><span class="mw-editsection"><span class="mw-editsection-bracket"></span>edit<span class="mw-editsection-bracket"></span></span></h4><p>The <b>exponential time hypothesis</b> (<b>ETH</b>) is that 3SAT, the satisfiability problem of Boolean formulas in conjunctive normal form with, at most, three literals per clause and with <i>n</i> variables, cannot be solved in time 2<i>o</i>(<i>n</i>). More precisely, the hypothesis is that there is some absolute constant <span class="texhtml"><i>c</i>>0</span> such that 3SAT cannot be decided in time 2<i>cn</i> by any deterministic Turing machine. With <i>m</i> denoting the number of clauses, ETH is equivalent to the hypothesis that <i>k</i>SAT cannot be solved in time 2<i>o</i>(<i>m</i>) for any integer <span class="texhtml"><i>k</i> ≥ 3</span>. The exponential time hypothesis implies P ≠ NP.
</p>samsofihttp://www.blogger.com/profile/12794342593186572847noreply@blogger.com0tag:blogger.com,1999:blog-4354751870549766853.post-62541970333891059962021-01-20T04:11:00.003-08:002021-01-20T04:11:05.262-08:00Exponential time<br/><br/><br/><p>An algorithm is said to be <b>exponential time</b>, if <i>T</i>(<i>n</i>) is upper bounded by 2poly(<i>n</i>), where poly(<i>n</i>) is some polynomial in <i>n</i>. More formally, an algorithm is exponential time if <i>T</i>(<i>n</i>) is bounded by O(2<i>n</i><i>k</i>) for some constant <i>k</i>. Problems which admit exponential time algorithms on a deterministic Turing machine form the complexity class known as <b>EXP</b>.
</p><dl><dd><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math alttext="{\displaystyle {\text{EXP}}=\bigcup _{c\in \mathbb {N} }{\text{DTIME}}\left(2^{n^{c}}\right)}" xmlns="http://www.w3.org/1998/Math/MathML">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mtext>EXP</mtext>
</mrow>
<mo>=</mo>
<munder>
<mo>⋃<!-- ⋃ --></mo>
<mrow class="MJX-TeXAtom-ORD">
<mi>c</mi>
<mo>∈<!-- ∈ --></mo>
<mrow class="MJX-TeXAtom-ORD">
<mi mathvariant="double-struck">N</mi>
</mrow>
</mrow>
</munder>
<mrow class="MJX-TeXAtom-ORD">
<mtext>DTIME</mtext>
</mrow>
<mrow>
<mo>(</mo>
<msup>
<mn>2</mn>
<mrow class="MJX-TeXAtom-ORD">
<msup>
<mi>n</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>c</mi>
</mrow>
</msup>
</mrow>
</msup>
<mo>)</mo>
</mrow>
</mstyle>
</mrow>
{\displaystyle {\text{EXP}}=\bigcup _{c\in \mathbb {N} }{\text{DTIME}}\left(2^{n^{c}}\right)}
</semantics>
</math></span><img alt="{\text{EXP}}=\bigcup _{c\in \mathbb {N} }{\text{DTIME}}\left(2^{n^{c}}\right)" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/cab57d7deb67a1253b19de1d875abaa392fa1418" style="vertical-align: -3.171ex; width:25.682ex; height:6.176ex;"/></span></dd></dl><p>Sometimes, exponential time is used to refer to algorithms that have <i>T</i>(<i>n</i>) = 2O(<i>n</i>), where the exponent is at most a linear function of <i>n</i>. This gives rise to the complexity class <b>E</b>.
</p><dl><dd><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math alttext="{\displaystyle {\text{E}}=\bigcup _{c\in \mathbb {N} }{\text{DTIME}}\left(2^{cn}\right)}" xmlns="http://www.w3.org/1998/Math/MathML">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mtext>E</mtext>
</mrow>
<mo>=</mo>
<munder>
<mo>⋃<!-- ⋃ --></mo>
<mrow class="MJX-TeXAtom-ORD">
<mi>c</mi>
<mo>∈<!-- ∈ --></mo>
<mrow class="MJX-TeXAtom-ORD">
<mi mathvariant="double-struck">N</mi>
</mrow>
</mrow>
</munder>
<mrow class="MJX-TeXAtom-ORD">
<mtext>DTIME</mtext>
</mrow>
<mrow>
<mo>(</mo>
<msup>
<mn>2</mn>
<mrow class="MJX-TeXAtom-ORD">
<mi>c</mi>
<mi>n</mi>
</mrow>
</msup>
<mo>)</mo>
</mrow>
</mstyle>
</mrow>
{\displaystyle {\text{E}}=\bigcup _{c\in \mathbb {N} }{\text{DTIME}}\left(2^{cn}\right)}
</semantics>
</math></span><img alt="{\text{E}}=\bigcup _{c\in \mathbb {N} }{\text{DTIME}}\left(2^{cn}\right)" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/90a73905632297c23232f3ea47c87409aff8d53e" style="vertical-align: -3.171ex; width:21.36ex; height:5.676ex;"/></span></dd></dl>samsofihttp://www.blogger.com/profile/12794342593186572847noreply@blogger.com0tag:blogger.com,1999:blog-4354751870549766853.post-50551109886551491712021-01-20T04:11:00.001-08:002021-01-20T04:11:01.169-08:00Factorial time<br/><br/><br/><p>An example of an algorithm that runs in factorial time is bogosort, a notoriously inefficient sorting algorithm based on trial and error. Bogosort sorts a list of <i>n</i> items by repeatedly shuffling the list until it is found to be sorted. In the average case, each pass through the bogosort algorithm will examine one of the <i>n</i>! orderings of the <i>n</i> items. If the items are distinct, only one such ordering is sorted. Bogosort shares patrimony with the infinite monkey theorem.
</p>samsofihttp://www.blogger.com/profile/12794342593186572847noreply@blogger.com0tag:blogger.com,1999:blog-4354751870549766853.post-86243542181878456982021-01-20T04:10:00.001-08:002021-01-20T04:10:56.716-08:00Double exponential time<br/><br/><br/><p>An algorithm is said to be double exponential time if <i>T</i>(<i>n</i>) is upper bounded by 22poly(<i>n</i>), where poly(<i>n</i>) is some polynomial in <i>n</i>. Such algorithms belong to the complexity class 2-EXPTIME.
</p><dl><dd><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math alttext="{\displaystyle {\mbox{2-EXPTIME}}=\bigcup _{c\in \mathbb {N} }{\mbox{DTIME}}\left(2^{2^{n^{c}}}\right)}" xmlns="http://www.w3.org/1998/Math/MathML">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="false" scriptlevel="0">
<mtext>2-EXPTIME</mtext>
</mstyle>
</mrow>
<mo>=</mo>
<munder>
<mo>⋃<!-- ⋃ --></mo>
<mrow class="MJX-TeXAtom-ORD">
<mi>c</mi>
<mo>∈<!-- ∈ --></mo>
<mrow class="MJX-TeXAtom-ORD">
<mi mathvariant="double-struck">N</mi>
</mrow>
</mrow>
</munder>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="false" scriptlevel="0">
<mtext>DTIME</mtext>
</mstyle>
</mrow>
<mrow>
<mo>(</mo>
<msup>
<mn>2</mn>
<mrow class="MJX-TeXAtom-ORD">
<msup>
<mn>2</mn>
<mrow class="MJX-TeXAtom-ORD">
<msup>
<mi>n</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>c</mi>
</mrow>
</msup>
</mrow>
</msup>
</mrow>
</msup>
<mo>)</mo>
</mrow>
</mstyle>
</mrow>
{\displaystyle {\mbox{2-EXPTIME}}=\bigcup _{c\in \mathbb {N} }{\mbox{DTIME}}\left(2^{2^{n^{c}}}\right)}
</semantics>
</math></span><img alt="{\mbox{2-EXPTIME}}=\bigcup _{c\in \mathbb {N} }{\mbox{DTIME}}\left(2^{2^{n^{c}}}\right)" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/0ae0eedc226c47bc0d6bf831c2796d3f4412762b" style="vertical-align: -3.171ex; width:34.62ex; height:6.176ex;"/></span></dd></dl><p>Well-known double exponential time algorithms include:
</p><ul><li>Decision procedures for Presburger arithmetic</li>
<li>Computing a Gröbner basis (in the worst case)</li>
<li>Quantifier elimination on real closed fields takes at least double exponential time, and can be done in this time.</li></ul>samsofihttp://www.blogger.com/profile/12794342593186572847noreply@blogger.com0