复杂性

此词条暂由彩云小译翻译，翻译字数共2038，未经人工整理和审校，带来阅读不便，请见谅。

Complexity characterises the behaviour of a system or model whose components interact in multiple ways and follow local rules, meaning there is no reasonable higher instruction to define the various possible interactions.

Complexity characterises the behaviour of a system or model whose components interact in multiple ways and follow local rules, meaning there is no reasonable higher instruction to define the various possible interactions.

复杂性描述了一个系统或模型的行为，其组件以多种方式交互并遵循局部规则，这意味着没有更高级（全局）指令来定义各种可能的交互。.

The term is generally used to characterize something with many parts where those parts interact with each other in multiple ways, culminating in a higher order of emergence greater than the sum of its parts. The study of these complex linkages at various scales is the main goal of complex systems theory.

这个术语通常用来描述具有许多组成部分的事物，其中这些部分以多种方式相互作用，最终以大于其各部分之和的更高级别出现。在不同尺度上研究这些复杂的结构是复杂系统理论的主要目标。

Science 模板:As of takes a number of approaches to characterizing complexity; Zayed et al.reflect many of these. Neil Johnson states that "even among scientists, there is no unique definition of complexity – and the scientific notion has traditionally been conveyed using particular examples..." Ultimately Johnson adopts the definition of "complexity science" as "the study of the phenomena which emerge from a collection of interacting objects".

科学里有许多种刻画复杂性的方法，比如 Zayed 的书中就给出许多案例。Neil Johnson 指出：“即使在科学家群体中，也没有关于复杂性的独特定义——传统上，关于复杂性的科学观念也是通过特定的例子来表达的... ... ”最终，Johnson 采用了“复杂性科学”的定义，即“研究从一系列相互作用的物体中产生的现象”。

综述

Definitions of complexity often depend on the concept of a "system" – a set of parts or elements that have relationships among them differentiated from relationships with other elements outside the relational regime. Many definitions tend to postulate or assume that complexity expresses a condition of numerous elements in a system and numerous forms of relationships among the elements. However, what one sees as complex and what one sees as simple is relative and changes with time.

复杂性的定义往往依赖于“系统”的概念，即一系列组成部分或组成要素之间的关系。许多定义倾向于认为复杂性表达了系统中的众多元素和元素之间的众多关系形式。然而，人们所认为的复杂和简单是相对的，并且随着时间的推移而变化。

Warren Weaver posited in 1948 two forms of complexity: disorganized complexity, and organized complexity.

沃伦 · 韦弗在1948年提出了复杂性的两种形式: 无组织的复杂性 disorganized complexity和有组织的复杂性 organized complexity。

Phenomena of 'disorganized complexity' are treated using probability theory and statistical mechanics, while 'organized complexity' deals with phenomena that escape such approaches and confront "dealing simultaneously with a sizable number of factors which are interrelated into an organic whole".

“无组织的复杂性”现象可以用概率论和统计力学来处理，而‘有组织的复杂性’则要处理不适用这种方法的现象，面对的主要问题是“同时处理大规模的相关因素，且这些因素相互关联，形成一个有机的整体”。

The approaches that embody concepts of systems, multiple elements, multiple relational regimes, and state spaces might be summarized as implying that complexity arises from the number of distinguishable relational regimes (and their associated state spaces) in a defined system.

体现系统、多元素、多关系体系和状态空间概念的方法可以概括为: 复杂性来自于一个已定义系统中可区分的关系体系(及其相关的状态空间)的数量。

Disorganized vs. organized

One of the problems in addressing complexity issues has been formalizing the intuitive conceptual distinction between the large number of variances in relationships extant in random collections, and the sometimes large, but smaller, number of relationships between elements in systems where constraints (related to correlation of otherwise independent elements) simultaneously reduce the variations from element independence and create distinguishable regimes of more-uniform, or correlated, relationships, or interactions.

解决复杂性问题的一个问题是将随机集合中现存的大量关系变量与系统中有时较大但较小的元素之间的关系(与其他独立元素的相关性有关)同时减少了元素独立性的变量，并创造了更加统一或相关的关系或相互作用的可区分的制度之间的直观概念区分形式化。

Weaver perceived and addressed this problem, in at least a preliminary way, in drawing a distinction between "disorganized complexity" and "organized complexity".

在区分“无组织的复杂性”和“有组织的复杂性”时，编织者至少以一种初步的方式察觉并解决了这个问题。

In Weaver's view, disorganized complexity results from the particular system having a very large number of parts, say millions of parts, or many more. Though the interactions of the parts in a "disorganized complexity" situation can be seen as largely random, the properties of the system as a whole can be understood by using probability and statistical methods.

在韦弗看来，无组织的复杂性是由于特定系统具有非常多的部件，比如数百万个部件，或者更多。虽然在“无组织复杂性”的情况下，各部分之间的相互作用可以看作是很大程度上的随机性，但是系统作为一个整体的性质可以通过使用概率和统计方法来理解。

A prime example of disorganized complexity is a gas in a container, with the gas molecules as the parts. Some would suggest that a system of disorganized complexity may be compared with the (relative) simplicity of planetary orbits – the latter can be predicted by applying Newton's laws of motion. Of course, most real-world systems, including planetary orbits, eventually become theoretically unpredictable even using Newtonian dynamics; as discovered by modern chaos theory.

无组织复杂性的一个典型例子是一个容器中的气体，以气体分子为部件。有些人认为，一个无组织的复杂系统可以与行星轨道的(相对)简单性相比较——后者可以通过应用牛顿运动定律来预测。当然，大多数真实世界的系统，包括行星轨道，最终在理论上变得不可预测，即使使用牛顿动力学; 正如现代混沌理论所发现的那样。

Organized complexity, in Weaver's view, resides in nothing else than the non-random, or correlated, interaction between the parts. These correlated relationships create a differentiated structure that can, as a system, interact with other systems. The coordinated system manifests properties not carried or dictated by individual parts. The organized aspect of this form of complexity vis-a-vis to other systems than the subject system can be said to "emerge," without any "guiding hand".

在 Weaver 看来，有组织的复杂性仅仅存在于各部分之间的非随机或相关的交互中。这些相互关联的关系创建了一个可以作为一个系统与其他系统交互的差异化结构。协调系统显示的属性不是由单个部分承载或支配的。这种形式的复杂性相对于主体系统以外的其他系统的有组织的方面可以说是“浮现” ，没有任何“指导手”。

The number of parts does not have to be very large for a particular system to have emergent properties. A system of organized complexity may be understood in its properties (behavior among the properties) through modeling and simulation, particularly modeling and simulation with computers. An example of organized complexity is a city neighborhood as a living mechanism, with the neighborhood people among the system's parts.

对于一个具有涌现特性的特定系统来说，部件的数量不一定非常大。一个有组织的复杂系统可以从它的属性(属性之间的行为)来理解，通过建模与模拟，特别是计算机的建模与模拟。有组织的复杂性的一个例子是一个城市邻里作为一个生活机制，与邻里的人在系统的部分。

There are generally rules which can be invoked to explain the origin of complexity in a given system.

通常有一些规则可以用来解释给定系统中复杂性的起源。

Overview

The source of disorganized complexity is the large number of parts in the system of interest, and the lack of correlation between elements in the system.

无组织复杂性的根源是感兴趣系统中的大量部件，以及系统中各要素之间缺乏相关性。

Definitions of complexity often depend on the concept of a "system" – a set of parts or elements that have relationships among them differentiated from relationships with other elements outside the relational regime. Many definitions tend to postulate or assume that complexity expresses a condition of numerous elements in a system and numerous forms of relationships among the elements. However, what one sees as complex and what one sees as simple is relative and changes with time.

In the case of self-organizing living systems, usefully organized complexity comes from beneficially mutated organisms being selected to survive by their environment for their differential reproductive ability or at least success over inanimate matter or less organized complex organisms. See e.g. Robert Ulanowicz's treatment of ecosystems.

就自我组织的生命系统而言，有效组织的复杂性来自于有益的突变生物体，它们被选择在其环境中生存，因为它们具有不同的生殖能力，或者至少在无生命物质或组织较少的复杂生物体上取得成功。参见。罗伯特·尤兰维奇对生态系统的处理。

Warren Weaver posited in 1948 two forms of complexity: disorganized complexity, and organized complexity.

Complexity of an object or system is a relative property. For instance, for many functions (problems), such a computational complexity as time of computation is smaller when multitape Turing machines are used than when Turing machines with one tape are used. Random Access Machines allow one to even more decrease time complexity (Greenlaw and Hoover 1998: 226), while inductive Turing machines can decrease even the complexity class of a function, language or set (Burgin 2005). This shows that tools of activity can be an important factor of complexity.

对象或系统的复杂性是一个相对的属性。例如，对于许多函数(问题)来说，使用多带图灵机比使用单带图灵机的计算复杂度要小。随机存取机器允许一个人甚至更多地降低时间复杂度(Greenlaw 和 Hoover 1998:226) ，而归纳图灵机甚至可以降低函数、语言或集合的复杂度等级(Burgin 2005)。这表明活动工具可以是复杂性的一个重要因素。

In several scientific fields, "complexity" has a precise meaning:

在一些科学领域，“复杂性”有着精确的含义:

Phenomena of 'disorganized complexity' are treated using probability theory and statistical mechanics, while 'organized complexity' deals with phenomena that escape such approaches and confront "dealing simultaneously with a sizable number of factors which are interrelated into an organic whole". Weaver's 1948 paper has influenced subsequent thinking about complexity.

In information theory, algorithmic information theory is concerned with the complexity of strings of data.

在信息论中，算法信息论关注的是数据串的复杂性。

Organized complexity, in Weaver's view, resides in nothing else than the non-random, or correlated, interaction between the parts. These correlated relationships create a differentiated structure that can, as a system, interact with other systems. The coordinated system manifests properties not carried or dictated by individual parts. The organized aspect of this form of complexity vis-a-vis to other systems than the subject system can be said to "emerge," without any "guiding hand".

Complex strings are harder to compress. While intuition tells us that this may depend on the codec used to compress a string (a codec could be theoretically created in any arbitrary language, including one in which the very small command "X" could cause the computer to output a very complicated string like "18995316"), any two Turing-complete languages can be implemented in each other, meaning that the length of two encodings in different languages will vary by at most the length of the "translation" language – which will end up being negligible for sufficiently large data strings.

复杂的字符串更难压缩。直觉告诉我们，这可能取决于用于压缩字符串的编解码器(编解码器理论上可以在任何语言中创建，包括一个非常小的命令“ x”可以导致计算机输出非常复杂的字符串，比如“18995316”) ，但是任何两种图灵完整语言都可以在彼此中实现，这意味着不同语言中两种编码器的长度最多只会随着“翻译”语言的长度而变化——这对于足够大数据字符串来说可以忽略不计。

The number of parts does not have to be very large for a particular system to have emergent properties. A system of organized complexity may be understood in its properties (behavior among the properties) through modeling and simulation, particularly modeling and simulation with computers. An example of organized complexity is a city neighborhood as a living mechanism, with the neighborhood people among the system's parts.

These algorithmic measures of complexity tend to assign high values to random noise. However, those studying complex systems would not consider randomness as complexity.

这些复杂度的算法测量倾向于给随机噪声赋予较高的值。然而，那些研究复杂系统的人并不认为随机性就是复杂性。

Information entropy is also sometimes used in information theory as indicative of complexity, but entropy is also high for randomness. Information fluctuation complexity, fluctuations of information about entropy, does not consider randomness to be complex and has been useful in many applications.

信息论中有时也会用熵表示复杂性，但是熵的随机性也很高。信息波动的复杂性，熵信息的波动性，不考虑随机性的复杂性，已经在许多应用中得到应用。

Recent work in machine learning has examined the complexity of the data as it affects the performance of supervised classification algorithms. Ho and Basu present a set of complexity measures for binary classification problems.

最近机器学习的工作已经检查了数据的复杂性，因为它影响了监督分类算法的性能。Ho 和 Basu 为二分类问题提出了一套复杂度量方法。

The complexity measures broadly cover:

复杂性指标大致涵盖:

Sources and factors

Instance hardness is a bottom-up approach that first seeks to identify instances that are likely to be misclassified (or, in other words, which instances are the most complex). The characteristics of the instances that are likely to be misclassified are then measured based on the output from a set of hardness measures. The hardness measures are based on several supervised learning techniques such as measuring the number of disagreeing neighbors or the likelihood of the assigned class label given the input features. The information provided by the complexity measures has been examined for use in meta learning to determine for which data sets filtering (or removing suspected noisy instances from the training set) is the most beneficial and could be expanded to other areas.

实例硬度是一种自下而上的方法，它首先寻求识别可能被错误分类的实例(或者，换句话说，哪些实例是最复杂的)。然后，可能被错误分类的实例的特征根据一组硬度测量值的输出进行测量。硬度测量是基于一些监督式学习技术，如测量不同意的邻居的数量或分配的类标签的可能性给予输入特征。复杂性度量提供的信息已经被用于元学习，以确定哪些数据集过滤(或者从训练集中去除可疑的噪音实例)是最有益的，并且可以扩展到其他领域。

There are generally rules which can be invoked to explain the origin of complexity in a given system.

The source of disorganized complexity is the large number of parts in the system of interest, and the lack of correlation between elements in the system.

A recent study based on molecular simulations and compliance constants describes molecular recognition as a phenomenon of organisation.

最近一项基于分子模拟和顺应常数的研究将分子识别描述为一种组织现象。

Even for small molecules like carbohydrates, the recognition process can not be predicted or designed even assuming that each individual hydrogen bond's strength is exactly known.

即使是像碳水化合物这样的小分子，识别过程也不能被预测或设计，即使假设每个单独的氢键的强度是确切知道的。

In the case of self-organizing living systems, usefully organized complexity comes from beneficially mutated organisms being selected to survive by their environment for their differential reproductive ability or at least success over inanimate matter or less organized complex organisms. See e.g. Robert Ulanowicz's treatment of ecosystems.

Complexity of an object or system is a relative property. For instance, for many functions (problems), such a computational complexity as time of computation is smaller when multitape Turing machines are used than when Turing machines with one tape are used. Random Access Machines allow one to even more decrease time complexity (Greenlaw and Hoover 1998: 226), while inductive Turing machines can decrease even the complexity class of a function, language or set (Burgin 2005). This shows that tools of activity can be an important factor of complexity.

Computational complexity theory is the study of the complexity of problems – that is, the difficulty of 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 in time [math]\displaystyle{ 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.

计算复杂性理论是研究问题的复杂性，也就是解决问题的难度。问题可以根据算法(通常是计算机程序)解决它们所需的时间(作为问题大小的函数)按复杂性类别进行分类。有些问题很难解决，而有些则很容易。例如，一些困难的问题需要算法花费指数量的时间来解决问题的大小。以旅行推销员问题为例。这个问题可以在时间上得到解决(其中 n 是要访问的网络的大小，也就是货郎担必须访问一次的城市数)。随着城市网络规模的扩大，寻找路线所需的时间呈指数增长(超过倍)。

Varied meanings

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.

即使一个问题在原则上是可以计算解决的，但在实际操作中可能没有那么简单。这些问题可能需要大量的时间或过多的空间。计算复杂性可以从许多不同的方面来看待。计算复杂性可以根据时间，内存或其他资源用于解决问题的基础上进行研究。在分析复杂性问题时，时间和空间是最重要和最普遍的两个考虑因素。

In several scientific fields, "complexity" has a precise meaning:

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 intractable.

有一类问题，虽然原则上是可以解决的，但是它们需要很多时间和空间，因此试图解决它们是不切实际的。这些问题被称为棘手的。

• In computational complexity theory, the amounts of resources required for the execution of algorithms is studied. The most popular types of computational complexity are the time complexity of a problem equal to the number of steps that it takes to solve an instance of the problem as a function of the size of the input (usually measured in bits), using the most efficient algorithm, and the space complexity of a problem equal to the volume of the memory used by the algorithm (e.g., cells of the tape) that it takes to solve an instance of the problem as a function of the size of the input (usually measured in bits), using the most efficient algorithm. This allows classification of computational problems by complexity class (such as P, NP, etc.). An axiomatic approach to computational complexity was developed by Manuel Blum. It allows one to deduce many properties of concrete computational complexity measures, such as time complexity or space complexity, from properties of axiomatically defined measures.

• In algorithmic information theory, the Kolmogorov complexity (also called descriptive complexity, algorithmic complexity or algorithmic entropy) of a string is the length of the shortest binary program that outputs that string. Minimum message length is a practical application of this approach. Different kinds of Kolmogorov complexity are studied: the uniform complexity, prefix complexity, monotone complexity, time-bounded Kolmogorov complexity, and space-bounded Kolmogorov complexity. An axiomatic approach to Kolmogorov complexity based on Blum axioms (Blum 1967) was introduced by Mark Burgin in the paper presented for publication by Andrey Kolmogorov. The axiomatic approach encompasses other approaches to Kolmogorov complexity. It is possible to treat different kinds of Kolmogorov complexity as particular cases of axiomatically defined generalized Kolmogorov complexity. Instead of proving similar theorems, such as the basic invariance theorem, for each particular measure, it is possible to easily deduce all such results from one corresponding theorem proved in the axiomatic setting. This is a general advantage of the axiomatic approach in mathematics. The axiomatic approach to Kolmogorov complexity was further developed in the book (Burgin 2005) and applied to software metrics (Burgin and Debnath, 2003; Debnath and Burgin, 2003).

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

还有另外一种复杂性，叫做层次复杂性。它与迄今为止所讨论的复杂性的形式是正交的，即所谓的横向复杂性。

• In information theory, information fluctuation complexity is the fluctuation of information about information entropy. It is derivable from fluctuations in the predominance of order and chaos in a dynamic system and has been used as a measure of complexity in many diverse fields.

• In information processing, complexity is a measure of the total number of properties transmitted by an object and detected by an observer. Such a collection of properties is often referred to as a state.

• In physical systems, complexity is a measure of the probability of the state vector of the system. This should not be confused with entropy; it is a distinct mathematical measure, one in which two distinct states are never conflated and considered equal, as is done for the notion of entropy in statistical mechanics.

• In dynamical systems, statistical complexity measures the size of the minimum program able to statistically reproduce the patterns (configurations) contained in the data set (sequence). While the algorithmic complexity implies a deterministic description of an object (it measures the information content of an individual sequence), the statistical complexity, like forecasting complexity, implies a statistical description, and refers to an ensemble of sequences generated by a certain source. Formally, the statistical complexity reconstructs a minimal model comprising the collection of all histories sharing a similar probabilistic future, and measures the entropy of the probability distribution of the states within this model. It is a computable and observer-independent measure based only on the internal dynamics of the system, and has been used in studies of emergence and self-organization.

• In mathematics, Krohn–Rhodes complexity is an important topic in the study of finite semigroups and automata.

• In Network theory complexity is the product of richness in the connections between components of a system, and defined by a very unequal distribution of certain measures (some elements being highly connected and some very few, see complex network).

• In software engineering, programming complexity is a measure of the interactions of the various elements of the software. This differs from the computational complexity described above in that it is a measure of the design of the software.

• In abstract sense – Abstract Complexity, is based on visual structures perception It is complexity of binary string defined as a square of features number divided by number of elements (0's and 1's). Features comprise here all distinctive arrangements of 0's and 1's. Though the features number have to be always approximated the definition is precise and meet intuitive criterion.

Other fields introduce less precisely defined notions of complexity:

• A complex adaptive system has some or all of the following attributes:

• • The number of parts (and types of parts) in the system and the number of relations between the parts is non-trivial – however, there is no general rule to separate "trivial" from "non-trivial";

• • The system has memory or includes feedback;

• • The system can adapt itself according to its history or feedback;

• • The relations between the system and its environment are non-trivial or non-linear;

• • The system can be influenced by, or can adapt itself to, its environment;

• • The system is highly sensitive to initial conditions.

Study

Complexity has always been a part of our environment, and therefore many scientific fields have dealt with complex systems and phenomena. From one perspective, that which is somehow complex – displaying variation without being random – is most worthy of interest given the rewards found in the depths of exploration.

The use of the term complex is often confused with the term complicated. In today's systems, this is the difference between myriad connecting "stovepipes" and effective "integrated" solutions. This means that complex is the opposite of independent, while complicated is the opposite of simple.

While this has led some fields to come up with specific definitions of complexity, there is a more recent movement to regroup observations from different fields to study complexity in itself, whether it appears in anthills, human brains, or stock markets, social systems. One such interdisciplinary group of fields is relational order theories.

Topics

Behaviour

The behavior of a complex system is often said to be due to emergence and self-organization. Chaos theory has investigated the sensitivity of systems to variations in initial conditions as one cause of complex behaviour.

Mechanisms

Recent developments around artificial life, evolutionary computation and genetic algorithms have led to an increasing emphasis on complexity and complex adaptive systems.

Simulations

In social science, the study on the emergence of macro-properties from the micro-properties, also known as macro-micro view in sociology. The topic is commonly recognized as social complexity that is often related to the use of computer simulation in social science, i.e.: computational sociology.

生物科学理论

Systems

Systems theory has long been concerned with the study of complex systems (in recent times, complexity theory and complex systems have also been used as names of the field). These systems are present in the research of a variety disciplines, including biology, economics, social studies and technology. Recently, complexity has become a natural domain of interest of real world socio-cognitive systems and emerging systemics research. Complex systems tend to be high-dimensional, non-linear, and difficult to model. In specific circumstances, they may exhibit low-dimensional behaviour.

Data

In information theory, algorithmic information theory is concerned with the complexity of strings of data.

Complex strings are harder to compress. While intuition tells us that this may depend on the codec used to compress a string (a codec could be theoretically created in any arbitrary language, including one in which the very small command "X" could cause the computer to output a very complicated string like "18995316"), any two Turing-complete languages can be implemented in each other, meaning that the length of two encodings in different languages will vary by at most the length of the "translation" language – which will end up being negligible for sufficiently large data strings.

These algorithmic measures of complexity tend to assign high values to random noise. However, those studying complex systems would not consider randomness as complexity模板:Who.

Information entropy is also sometimes used in information theory as indicative of complexity, but entropy is also high for randomness. Information fluctuation complexity, fluctuations of information about entropy, does not consider randomness to be complex and has been useful in many applications.

Recent work in machine learning has examined the complexity of the data as it affects the performance of supervised classification algorithms. Ho and Basu present a set of complexity measures for binary classification problems.

The complexity measures broadly cover:

• the overlaps in feature values from differing classes.

• the separability of the classes.

• measures of geometry, topology, and density of manifolds. Instance hardness is another approach seeks to characterize the data complexity with the goal of determining how hard a data set is to classify correctly and is not limited to binary problems.

Instance hardness is a bottom-up approach that first seeks to identify instances that are likely to be misclassified (or, in other words, which instances are the most complex). The characteristics of the instances that are likely to be misclassified are then measured based on the output from a set of hardness measures. The hardness measures are based on several supervised learning techniques such as measuring the number of disagreeing neighbors or the likelihood of the assigned class label given the input features. The information provided by the complexity measures has been examined for use in meta learning to determine for which data sets filtering (or removing suspected noisy instances from the training set) is the most beneficial and could be expanded to other areas.

In molecular recognition

A recent study based on molecular simulations and compliance constants describes molecular recognition as a phenomenon of organisation.

Even for small molecules like carbohydrates, the recognition process can not be predicted or designed even assuming that each individual hydrogen bond's strength is exactly known.

Applications

Computational complexity theory is the study of the complexity of problems – that is, the difficulty of 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 in time [math]\displaystyle{ 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 intractable.

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