Computational complexity: Difference between revisions

Revision as of 18:05, 29 December 2017

Latest revision as of 11:35, 31 March 2025

(109 intermediate revisions by 53 users not shown)

Line 1:

{{Short description|Amount of resources to perform an algorithm}}

{{unreferenced|date=September 2017}}

{{CS1 config|mode=cs2}}

In [[computer science]], the '''computational complexity''', or simply '''complexity''' of an [[algorithm]] is the amount of resources required for running it. The '''computational complexity''' of a problem is the minimum of the complexities of all possible algorithms for this problem (including the unknown algorithms).

{{more footnotes|date=December 2017}}

In [[computer science]], the '''computational complexity''', or simply '''complexity''' of an [[algorithm]] is the amount of resources required forto runningrun it. The '''computational complexity''' of a problem is the minimum of the complexities of all possible algorithms for this problem (including the unknown algorithms). <ref>{{citation

| last = Vadhan | first = Salil | author-link = Salil Vadhan

| editor1-last = van Tilborg | editor1-first = Henk C. A.

| editor2-last = Jajodia | editor2-first = Sushil

| contribution = Computational Complexity

| contribution-url = https://people.seas.harvard.edu/~salil/research/ComputationalComplexity-2ndEd.pdf

| doi = 10.1007/978-1-4419-5906-5_442

| isbn = 9781441959065

| pages = 235–240

| publisher = Springer

| title = Encyclopedia of Cryptography and Security

| year = 2011}}</ref> Particular focus is given to [[time complexity|computation time]] (generally measured by the number of needed elementary operations) and [[space complexity|memory storage]] requirements. The complexity of a [[computational problem|problem]] is the complexity of the best algorithms that allow solving the problem.

The study of the complexity of explicitly given algorithms is called [[analysis of algorithms]], while the study of the complexity of problems is called [[computational complexity theory]]. Clearly, bothBoth areas are stronglyhighly related, as the complexity of an algorithm is always an [[upper bound]] ofon the complexity of the problem solved by this algorithm. Moreover, for designing efficient algorithms, it is often fundamental to compare the complexity of a specific algorithm to the complexity of the problem to be solved. Also, in most cases, the only thing that is known about the complexity of a problem is that it is lower than the complexity of the most efficient known algorithms. Therefore, there is a large overlap between analysis of algorithms and complexity theory.

As the amount of needed resources varies with the input, the complexity is generally expressed as a function {{math|''n'' → ''f''(''n'')}}, where {{math|''n''}} is the size of the input, and {{math|''f''(''n'')}} is either the [[worst-case complexity]], that is the maximum of the amount of resources that are needed for all input of size {{math|''n''}}, or the [[average-case complexity]], that is average of the amount of resources over all input of size {{math|''n''}}.

WhenAs the natureamount of the resources isrequired notto explicitlyrun given,an thisalgorithm isgenerally varies usuallywith the timesize neededof forthe runninginput, the algorithmcomplexity is typically expressed as a function {{math|''n'' → ''f''(''n'')}}, andwhere one{{math|''n''}} is the talkssize of the input and {{math|''f''(''n'')}} is either the [[timeworst-case complexity]]. However,(the thismaximum dependsof onthe amount of resources that are needed over all inputs of size {{math|''n''}}) or the [[computeraverage-case complexity]] that(the isaverage used, andof the timeamount of resources over all inputs of size {{math|''n''}}). [[Time complexity]] is generally expressed as the number of neededrequired elementary operations on an input of size {{math|''n''}}, whichwhere elementary operations are supposedassumed to take a constant amount of time on a given computer, and to change only by a constant factor when onerun changeson a different computer. [[Space complexity]] is generally expressed as the amount of [[computer memory|memory]] required by an algorithm on an input of size {{math|''n''}}.

Otherwise, the resource that is considered is often the size of the memory that is needed, and one talks of [[space complexity]].

The study of the complexity of explicitly given algorithms is called [[analysis of algorithms]], while the study of the complexity of problems is called [[computational complexity theory]]. Clearly, both areas are strongly related, as the complexity of an algorithm is always an [[upper bound]] of the complexity of the problem solved by this algorithm.

==Resources==

===Time===

The resource that is most commonly considered is the time, and one talks of [[time complexity]]. When "complexity" is used without being qualifiedqualification, this generally means time complexity.

The usual units of time (seconds, minutes etc.) are not used in [[computational complexity theory|complexity theory]], because they are too dependent on the choice of a specific computer and ofon the evolution of the technology. ThereforeFor instance, insteada computer today can execute an algorithm significantly faster than a computer from the 1960s; however, this is not an intrinsic feature of the realalgorithm but rather a consequence of technological advances in [[computer hardware]]. Complexity theory seeks to quantify the intrinsic time requirements of algorithms, onethat generallyis, considerthe basic time constraints an algorithm would place on ''any'' computer. This is achieved by counting the number of ''elementary operations'' that are doneexecuted during the computation. These operations are supposedassumed to take a constant time (that is, not affected by the size of the input) on a given machine, and are often called ''steps''.

===Bit complexity===

{{anchor|bit complexity}}

Formally, the ''bit complexity'' refers to the number of operations on [[bit]]s that are needed for running an algorithm. With most [[models of computation]], it equals the time complexity up to a constant factor. On [[computer]]s, the number of operations on [[machine word]]s that are needed is also proportional to the bit complexity. So, the ''time complexity'' and the ''bit complexity'' are equivalent for realistic models of computation.

===Space===

Another important resource is the size of [[computer memory]] that is needed for running algorithms.

===Communication===

{{Main article|communication complexity}}

For the class of [[distributed computation|distributed algorithms]] that are commonly executed by multiple, interacting parties, the resource that is of most interest is the communication complexity. It is the necessary amount of communication between the executing parties.

===Others===

The number of [[arithmetic operations]] inis another resource that is commonly used. In this case, one talks of '''arithmetic complexity'''. If one knows an [[upper bound]] on the size of the [[binary representation]] of the numbers that occur during a computation, the time complexity is generally the product of the arithmetic complexity by a constant factor.

{{anchor|bit complexity}}

For many algorithms the size of the integers that are used during a computation is not bounded, and it is not realistic to consider that arithmetic operations take a constant time. Therefore, the time complexity, generally called [['''bit complexity]]''' in this context, may be much larger than the arithmetic complexity. For example, the arithmetic complexity of the computation of the [[determinant]] of a {{math|''n''×''n''}} [[integer matrix]] is <math>O(n^3)</math> for the usual algorithms ([[Gaussian elimination]]). The bit complexity of the same algorithms is [[exponential function |exponential]] in {{mvar|n}}, because the size of the coefficients may grow exponentially during the computation. On the other hand, if these algorithms are coupled with [[modular arithmetic|multi-modular arithmetic]], the bit complexity may be reduced to {{math|[[soft O notation|{{math|''O''^~(''n''⁴)}}]]}}.

In [[sorting]] and [[search algorithm|searching]], the resource that is generally considered is the number of entriesentry comparisons. This is generally a good measure of the time complexity if data are suitably organized.

==Complexity as a function of input size==

:''For clarity, only{{hatnote|Only time complexity is considered in this section, but everything applies (with slight modifications) to the complexity with respect to other resources.'' }}

It is impossible to count the number of steps of an algorithm on all possible inputs. As the complexity increases generally increases with the size of the input, the complexity is generallytypically expressed as a function of the size {{math|''n''}} (in [[bit]]s) of the input, and therefore, the complexity is a function of {{math|''n''}}. However, the complexity of an algorithm may vary dramatically for different inputs of the same size. Therefore, several complexity functions are commonly used.

The [[worst-case complexity]] is the maximum of the complexity over all inputs of size {{mvar|n}}, and the [[average-case complexity]] is the average of the complexity over all inputs of size {{mvar|n}} (this makes sense, as the number of possible inputs of a given size is finite). Generally, when "complexity" is used without being further specified, this is the worst-case time complexity that is considered.

Line 34 ⟶ 52:

==Asymptotic complexity==

{{see also|Asymptotic computational complexity}}

It is generally very difficult to compute exactlyprecisely the worst-case and the average-case complexity. MoreoverIn thisaddition, makesthese notexact reallyvalues provide little practical senseapplication, as any change of computer or of model of computation would change the complexity somewhat. Moreover, the resource use is not critical for small values of {{mvar|n}}, and this makes that, for small {{mvar|n}}, the ease of implementation is generally more interesting than a goodlow complexity.

For these reasons, one generally focuses on the behavior of the complexity for large {{mvar|n}}, that is on its [[asymptotic analysis|asymptotic behavior]] when {{mvar|n}} tends to the infinity. Therefore, the complexity is generally expressed by using [[big O notation]].

For example, the usual algorithm for integer [[multiplication]] has a complexity of <math>O(n^2),</math> this means that there is a constant <math>c_u</math> such that the multiplication of two integers of at most {{mvar|n}} digits may be done in a time less than <math>c_un^2.</math> This bound is ''sharp'' in the sense that the worst-case complexity and the average-case complexity are <math>\Omega(n^2),</math> which means that there is a constant <math>c_l</math> such that these complexities are larger than <math>c_ln^2.</math> The [[radix]] does not appear in these complexity, as changing of radix changes only the constants <math>c_u</math> and <math>c_l.</math>

==Models of computation==

The evaluation of the complexity relies on the choice of a [[model of computation]], which consistconsists in defining the basic operations that are done in a unit of time. When the model of computation is not explicitly specified, thisit is generally meantimplicitely assumed as being a [[multitape Turing machine]], since several more realistic models of computation, such as [[random-access machine]]s are asymptotically equivalent for most problems. It is only for very specific and difficult problems, such as [[integer multiplication]] in time <math>O(n\log n),</math> that the explicit definition of the model of computation is required for proofs.

===Deterministic models===

A [[deterministic model]] of computation is a model of computation such that the successive states of the machine and the operations to be performed are completely determined by the preceding state. Historically, the first deterministic models were [[μ-recursive function|recursive function]]s, [[lambda calculus]], and [[Turing machine]]s. The model of [[Random random-access machine]]s (also called RAM-machines) is also widely used, as a closer counterpart to real [[computer]]s.

When the model of computation is not specified, it is generally theassumed modelto be ofa [[multitape Turing machine]]s. For most algorithms, the time complexity is the same on multitape Turing machines andas on RAM-machines, although, some care may be needed in storinghow data foris stored in memory to gettingget this equivalence.

===Non-deterministic computation===

In a [[non-deterministic algorithm|non-deterministic model of computation]], such as [[non-deterministic Turing machine]]s, some choices may be done at some steps of the computation. In complexity theory, one considers all possible choices simultaneously, and the non-deterministic time complexity is the time needed, when the best choices are always done. In other words, one considers that the computation is done simultaneously on as many (identical) processors as needed, and the non-deterministic computation time time is the time spent by the first computerprocessor that finishes the computation. This parallelism is partly amenable to [[quantum computing]] via superposed [[entangled state]]s in running specific [[quantum algorithms]], like e.g. [[Shor's algorithm|Shor's factorization]] of yet only small integers ({{as of|2018|03|lc=yes}}: 21 = 3 × 7).

SuchEven when such a computation model is not realistic, butyet, it has sometheoretical practical applicationsimportance, mostly related withto the [[P = NP]] problem, which questions the identity of the complexity classes formed by taking "polynomial time" and "non-deterministic polynomial time" as least upper bounds. Simulating an NP-algorithm on a deterministic computer usually takes "exponential time". A problem is in the complexity class [[NP (complexity)|NP]], if isit may be solved in [[polynomial time]] overon a non-deterministic machine. A problem is [[NP-complete]] if, roughly speaking, it is in NP and is not easier than any other NP problem. Many [[combinatorics|combinatorial]] problems, such as the [[Knapsack problem]], the [[travelling salesman problem]], and the [[Boolean satisfiability problem]] are NP-complete. For all these problems, the best known algorithm has an exponential complexity. If any one of these problemproblems could be solved in polynomial time on a deterministic machine, then all NP problems could also be solved in polynomial time, and one would have P = NP. It{{As of|2017}} it is generally conjectured that {{nowrap|P ≠ NP,}} and this haswith the practical implication that the worst cases of NP problems are intrinsically difficult (into thesolve, worsti.e., casetake longer than any reasonable time span (decades!). for interesting lengths of input.

===Parallel and distributed computation===

{{main|Parallel computing|Distributed computing}}

Parallel and distributed computing consist of splitting computation on several processors, which work simultaneously. The difference between the different model lies mainly in the way of transmitting information between processors. Typically, in parallel computing the data transmission between processors is very fast, while, in distributed computing, the data transmission is done through a [[computer network|network]] and is therefore much slower.

The time needed for a computation on {{mvar|N}} processors is at least the quotient by {{mvar|N}} of the time needed by a single processor. In fact this theoretically optimal bound can never be reached, because some subtasks cannot be parallelized, and some processors may have to wait a result from another processor.

The main complexity problem is thus to design algorithms such that the product of the computation time by the number of processors is as close as possible to the time needed for the same computation on a single processor.

===Quantum computing===

A [[quantum computer]] is a computer whose model of computation is basebased on [[quantum mechanics]]. The [[Church–Turing thesis (complexity theory)|Church–Turing thesis]] applies to quantum computers,; that is, every problem that can be solved by a quantum computer may becan also be solved by a Turing machine. However, some problems may theoretically be solved with a much lower [[time complexity]] overusing a quantum computer rather than over a classical computer. This is, for the moment, purely theoretical, as no one doesknows nothow knowto how buildingbuild an efficient quantum computer.

[[Quantum complexity theory]] has been developed forto studyingstudy computationalthe [[complexity class]]es of problems solved using quantum computingcomputers. It is used in [[post-quantum cryptography]], which consists of designing [[cryptographic protocol]]s that willare resistresistant to attacks withby quantum computers, when such computers will really exist.

==Problem complexity (lower bounds)==

The complexity of a problem is the [[infimum]] of the complexities of the algorithms that may solve the problem{{Citation needed|date=May 2023|reason=}}, including unknown algorithms. Thus the complexity of a problem is not greater than the complexity of any algorithm that solves the problems.

It follows that every complexity of an algorithm, that is expressed with [[big O notation]], is also an upper bound on the complexity of the corresponding problem.

On the other hand, it is generally hard to obtain nontrivial lower bounds for problem complexity, and there are few methods for obtaining such lower bounds.

For solving most problems, it is required to read all input data, which, normally, needs a time proportional to the size of the data. Thus, such problems have a complexity that is at least [[linear time|linear]], that is, using [[big omega notation]], a complexity <math>\Omega(n).</math>

The solution of some problems, typically in [[computer algebra]] and [[computational algebraic geometry]], may be very large. In such a case, the complexity is lower bounded by the maximal size of the output, since the output must be written. For example, a [[system of polynomial equations|system of {{mvar|n}} polynomial equations of degree {{mvar|d}} in {{mvar|n}} indeterminates]] may have up to <math>d^n</math> [[complex number|complex]] solutions, if the number of solutions is finite (this is [[Bézout's theorem]]). As these solutions must be written down, the complexity of this problem is <math>\Omega(d^n).</math> For this problem, an algorithm of complexity <math>d^{O(n)}</math> is known, which may thus be considered as asymptotically quasi-optimal.

A nonlinear lower bound of <math>\Omega(n\log n)</math> is known for the number of comparisons needed for a [[sorting algorithm]]. Thus the best sorting algorithms are optimal, as their complexity is <math>O(n\log n).</math> This lower bound results from the fact that there are {{math|''n''!}} ways of ordering {{mvar|n}} objects. As each comparison splits in two parts this set of {{math|''n''!}} orders, the number of {{mvar|N}} of comparisons that are needed for distinguishing all orders must verify <math>2^N>n!,</math> which implies <math>N =\Omega(n\log n),</math> by [[Stirling's formula]].

A standard method for getting lower bounds of complexity consists of ''reducing'' a problem to another problem. More precisely, suppose that one may encode a problem {{mvar|A}} of size {{mvar|n}} into a subproblem of size {{math|''f''(''n'')}} of a problem {{mvar|B}}, and that the complexity of {{mvar|A}} is <math>\Omega(g(n)).</math> Without loss of generality, one may suppose that the function {{mvar|f}} increases with {{mvar|n}} and has an [[inverse function]] {{mvar|h}}. Then the complexity of the problem {{mvar|B}} is <math>\Omega(g(h(n))).</math> This is the method that is used to prove that, if [[P ≠ NP]] (an unsolved conjecture), the complexity of every [[NP-complete problem]] is <math>\Omega(n^k),</math> for every positive integer {{mvar|k}}.

[[Quantum complexity theory]] has been developed for studying computational complexity of quantum computing. It is used in [[post-quantum cryptography]], which consists of designing [[cryptographic protocol]]s that will resist to attacks with quantum computers, when such computers will really exist.

==Use in algorithm design==

Evaluating the complexity of an algorithm is an important part of [[algorithm design]], as this gives useful information on the performance that may be expected.

Evaluating the complexity of an algorithm is an important part of [[algorithm design]], as this gives useful information on the performance that may be expected.

It is a common misconception that the evaluation of the complexity of algorithms becomes less important, because of the exponential growth ([[Moore's law]]) of the power of modern [[computer]]s. This is wrong because, this power increase allows working with large input data ([[big data]]). For example, when one want to sort alphabetically a list of a few hundreds of entries, such as the [[bibliography]] of a book, any algorithm should work well in less than a second. On the other hand, for a list of a million of entries (the phone numbers of a large town, for example), the elementary algorithms that require <math>O(n^2)</math> comparisons would have to do a trillion of comparisons, which would need more than one day at the speed of a million of comparisons per second. On the other hand the [[quicksort]] and [[merge sort]] require only <math>n\log_2 n</math> comparisons (as average-case complexity for the former, as worst-case complexity for the latter). For {{math|1=''n'' = 1,000,000}}, this gives approximately 30,000,000 comparisons, which may be done in a few seconds on a powerful computer.

It is a common misconception that the evaluation of the complexity of algorithms becomeswill become less important, becauseas ofa theresult exponentialof growth ([[Moore's law]]), which posits the [[exponential growth]] of the power of modern [[computer]]s. This is wrong because, this power increase allows working with large input data ([[big data]]). For example, when one wantwants to sort alphabetically a list of a few hundreds of entries, such as the [[bibliography]] of a book, any algorithm should work well in less than a second. On the other hand, for a list of a million of entries (the phone numbers of a large town, for example), the elementary algorithms that require <math>O(n^2)</math> comparisons would have to do a trillion of comparisons, which would need morearound than onethree dayhours at the speed of a10 million of comparisons per second. On the other hand, the [[quicksort]] and [[merge sort]] require only <math>n\log_2 n</math> comparisons (as average-case complexity for the former, as worst-case complexity for the latter). For {{math|1=''n'' = 1,000,000}}, this gives approximately 30,000,000 comparisons, which maywould beonly donetake in3 aseconds fewat seconds10 onmillion acomparisons powerfulper computersecond.

Thus the evaluation of the complexity may allow eliminating many inefficient algorithms before any implementation. This may also be used for tuning complex algorithms without testing all variants. By determining the most costly steps of a complex algorithms, the study of complexity allows also focusing on these steps the effort for improving the efficiency of an implementation.

Thus the evaluation of the complexity may allow eliminating many inefficient algorithms before any implementation. This may also be used for tuning complex algorithms without testing all variants. By determining the most costly steps of a complex algorithmsalgorithm, the study of complexity allows also focusing on these steps the effort for improving the efficiency of an implementation.

==See also==

* [[Computational complexity of mathematical operations]]

* [[Chinese Postman Problem Complexity List]]

* [[Master theorem (analysis of algorithms)]]

==References==

{{Reflist}}

*{{Citation

| last1=Arora | first1=Sanjeev | authorlink1author-link1=Sanjeev Arora

| last2=Barak | first2=Boaz

| title=Computational Complexity: A Modern Approach

Line 79 ⟶ 123:

| isbn=978-0-521-42426-4

| zbl=1193.68112

}}

*{{Citation

| last=Calude

| first=Cristian

| author-link=Cristian Calude

| title=Theories of Computational Complexity

| publisher=[[Elsevier]]

| year=1988

| isbn=9780444703569

| pages=487

}}

* {{citation

Line 86 ⟶ 140:

| title=Theory of Computational Complexity

| publisher=[[John Wiley & Sons]]

| issn= 0167-5060

| year=2000

| isbn=978-0-471-34506-0

Line 93 ⟶ 148:

| last=Goldreich

| first=Oded

| authorlinkauthor-link=Oded Goldreich

| url = http://www.wisdom.weizmann.ac.il/~oded/cc-book.html

| title = Computational Complexity: A Conceptual Perspective

Line 111 ⟶ 166:

| last = Papadimitriou

| first = Christos

| authorlinkauthor-link = Christos Papadimitriou

| title = Computational Complexity

| edition = 1st

Line 121 ⟶ 176:

|last=Sipser

|first=Michael

|authorlinkauthor-link=Michael Sipser

|title=[[Introduction to the Theory of Computation]]

|edition=2nd

Line 129 ⟶ 184:

|isbn=0-534-95097-3

}}

{{Computer science}}

[[Category:Analysis of algorithms]]