Exponential complexity

Exponential complexity - in the theory of complexity of algorithms , the complexity of the problem, limited by the exponent of the polynomial on the dimension of the problem, that is, is limited by the function $\exp(P(n))$ ${\ displaystyle \ exp (P (n))}$ ${\ displaystyle \ exp (P (n))}$ where $P$ ${\ displaystyle P}$ $P$ Is some polynomial, and $n$ ${\ displaystyle n}$ $n$ - task size. In this case, they say that the complexity of the problem grows exponentially . Often, complexity refers to the execution time of an algorithm. In this case, it is said that the algorithm belongs to the EXPTIME class. However, complexity may also apply to memory or other resources needed for the algorithm to work.

The difference between polynomial and exponential algorithms goes back to von Neumann . ^[one]

Content

Temporal difficulty

Tasks with exponential complexity of working time form the class EXPTIME , formally defined as:

{\text{EXPTIME}}=\bigcup _{k=1}^{\infty }TIME\left(2^{n^{k}}\right)

{\ displaystyle {\ text {EXPTIME}} = \ bigcup _ {k = 1} ^ {\ infty} TIME \ left (2 ^ {n ^ {k}} \ right)}

,

Where $TIME(f(n))$ ${\ displaystyle TIME (f (n))}$ - a lot of tasks that can be solved by algorithms whose runtime is limited by the function above $f(t)$ ${\ displaystyle f (t)}$ .

Comparison with polynomial complexity

It is generally accepted that algorithms with polynomial complexity are “fast”, while algorithms whose complexity is greater than polynomial complexity are “slow”. From this point of view, algorithms with exponential complexity are slow. However, this assumption is not entirely accurate. The fact is that the running time of the algorithm depends on the value of n (the dimension of the problem) and related constants hidden in the O-notation . In some cases, for small values of n, polynomial time can exceed exponential. However, for larger values of n , the running time of the algorithm with exponential complexity is significantly longer.

Subexponential complexity

There are algorithms that work more than in polynomial time ( “super-polynomial” ), but less than in exponential time ( “sub-exponential” ). An example of such a problem is the decomposition of an integer into prime factors ( factorization ). Such algorithms are also referred to as "slow."

Notes

↑ John von Neumann. A certain zero-sunn two-person game equivalent to the optimal assignment problem // Contributions to the Theory of Games. - Princeton Univ. Press

[1] John von Neumann. A certain zero-sunn two-person game equivalent to the optimal assignment problem // Contributions to the Theory of Games. - Princeton Univ. Press