Editing Computational complexity (section)

==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}}.