Computational complexity: Difference between revisions

Revision as of 13:42, 5 February 2023

Revision as of 12:38, 29 May 2023

Line 73:

==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 aalso complexityan ofupper thebound algorithmon asthe well ascomplexity 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.