Editing Complexity (section)

== Applications ==
Computational complexity theory is the study of the complexity of problems – that is, the difficulty of [[problem solving|solving]] them. Problems can be classified by complexity class according to the time it takes for an algorithm – usually a computer program – to solve them as a function of the problem size. Some problems are difficult to solve, while others are easy. For example, some difficult problems need algorithms that take an exponential amount of time in terms of the size of the problem to solve. Take the [[travelling salesman problem]], for example. It can be solved, as denoted in [[Big O notation]], in time <math>O(n^2 2^n)</math> (where ''n'' is the size of the network to visit – the number of cities the travelling salesman must visit exactly once). As the size of the network of cities grows, the time needed to find the route grows (more than) exponentially.

Even though a problem may be computationally solvable in principle, in actual practice it may not be that simple. These problems might require large amounts of time or an inordinate amount of space. Computational complexity may be approached from many different aspects. Computational complexity can be investigated on the basis of time, memory or other resources used to solve the problem. Time and space are two of the most important and popular considerations when problems of complexity are analyzed.

There exist a certain class of problems that although they are solvable in principle they require so much time or space that it is not practical to attempt to solve them. These problems are called [[Computational complexity theory#Intractability|intractable]].

There is another form of complexity called [[Model of hierarchical complexity|hierarchical complexity]]. It is orthogonal to the forms of complexity discussed so far, which are called horizontal complexity.