人们如何评估一个问题的复杂度

评估一个问题的复杂度,涉及理解若干彼此关联的因素,它们共同影响着一个人的感知与体验。这些因素包括:知识、度量、可预测性,以及可用的资源。

知识指一个人所拥有的背景信息与专业能力,它会显著地塑造他驾驭复杂任务的能力。

度量关乎我们如何量化或评估一个问题的复杂之处,往往依赖某些指标或标准,而这些指标在不同情境下可能各不相同。

可预测性与一个问题的结果有多可被预见有关;结果越可预测的问题往往被认为越简单,而结果不确定的问题则会被视为更复杂。

最后,资源涵盖一个人可支配的工具、时间与支持,它们既可能帮助、也可能阻碍他有效地应对复杂性。

把这些要素放在一起考量,我们就能更深入地理解:复杂性在各种情境中是如何被评估与管理的。

无序与有序

正如第二定律所言:在一个封闭系统里,无序程度会随时间趋于增加,导致熵增大,直到系统达到平衡态。

在我们的世界里,我们观察到:若没有外力管理,几乎所有系统都会朝着更大的无序演化。你能感觉到——如果你想独自完成某件事,却没有任何引导或结构,事情最终会变得混乱、失控,直到你发现任务多到无法完成。

我们也把熵的概念用到信息系统中,比如用”交叉熵”来训练大模型。这种联系说明了数据中的不确定性与无序如何影响算法的表现。在机器学习中,越高的熵往往意味着模型预测分布中越多的无序。训练时最小化交叉熵,能帮助模型学会做出准确的预测——这正是我们想要达成的。

直觉上,无序与有序密切相连,因为无序的增加往往带来复杂度的升高。把事物梳理得井然有序,是在解决问题时找到平衡、结构乃至简单的关键。

越无序的东西越复杂。 这是我们日常生活中的本能感受。

复杂与简单

要用一个客观的度量来判断一件作品是复杂还是简单,并不容易。复杂性常常是主观的:一个人觉得繁复而困难的东西,另一个人可能觉得直白而好办。

诸如先验知识、经验,以及处理任务时的具体情境,都会显著影响这种判断。

此外,一个人可支配的工具与资源,也会让他对某项任务复杂度的感知或简化、或复杂化。因此,理解复杂性不仅需要分析任务本身,也需要意识到个体独特的视角与处境。

复杂性也很难定义。一个非正式的说法是:复杂度是为了刻画、预测或生成一个系统或问题,所需的最小资源量(信息、能量、计算或描述长度)。

无序与复杂度的关系

进一步探究这层关系,我们可以认为:复杂性常常源于系统内部各组分之间的相互作用与依赖。在许多情形下,随着无序的增加,系统可能的状态或构型数目也随之增加,从而带来更高的复杂度。

举例来说,在信息论里,一个高度无序的数据集可能需要更精巧的算法才能从中提取有意义的模式或洞见,因为噪声会掩盖相关的信号。

类似地,在物理系统中,熵的增加会引出更复杂、更难以预测或控制的行为。

再者,在计算的语境下,为处理复杂问题而设计的算法,往往需要考虑各种无序的来源,例如数据中的噪声或用户行为的多变。这就要求我们发展出足够稳健的模型,使其能在变化的条件下依然给出准确的输出。

归根结底,无序确实会通过引入不确定性与多变性来贡献复杂度;但同样重要的是要认识到:并非所有复杂性都是负面的。系统要有效且自适应地运转,某种程度的复杂性是必需的。因此,理解有序与无序之间的平衡,对于在任何领域(无论技术、生物还是社会系统)中管理复杂性,都至关重要。最终,正是这种相互作用,塑造了我们解决问题与创新的方式。

问题设定

让我们设定一个问题,并从中做些观察。

你有一瓶可乐。你打开它,放进几块冰,再把瓶盖拧上。这个环境里的主要观察是:

• 开始时: 边界清晰——固体冰块浮在液体里。
• 中途: 精巧的、蕾丝般的融化锋面,对流羽流,以及气泡的路径——丰富的、多尺度的几何形态。
• 最后: 温度趋于均一;饮料变得整体冰凉而平静,几乎不剩什么特征。

用热力学第二定律解释

根据热力学第二定律,一个孤立系统的总熵永不随时间减少。

起初,当固体冰块被放入液态可乐时,固相与液相之间界限分明——这是一个低熵状态。

随着冰的融化,能量从较暖的液体传向较冷的冰,两相中的分子开始混合,无序随之增加。热量流动、相变发生,过程中生出错综的图样与对流。熵增加了。

最终,当平衡到来,系统的熵达到最大,整杯饮料温度均一,几乎不剩任何特征。这个演进说明了系统如何随时间走向更大的无序,与第二定律所述的原理一致。

用简单的数学来思考

热力学第一定律告诉我们:

$$\Delta U = Q - W$$

其中 $U$ 代表系统所含的总能量,包括其粒子的动能与势能;$Q$ 是加入系统的热量,$W$ 是系统所做的功。

设可乐、冰、以及融化后的冰的能量分别为 $U_{coke}$、$U_{ice}$、$U_{melt\ ice}$,并以 $U_{total}$ 表示最终这杯冰可乐的能量。因为能量守恒,

$$\Delta U_{\text{coke}} + \Delta U_{\text{ice}} + \Delta U_{melt\ ice} = 0$$

从熵的一侧看,我们把这个系统的熵定义为 $S_{sys}$。无论可乐降温、冰块融化的过程中发生了什么,这个封闭系统的熵都单调增加,直到平衡,于是

$$\Delta S_{sys} \ge 0$$

那复杂度呢?

这里的复杂度,可以理解为衡量系统各组分之间的相互作用如何随时间演化。起初,当冰块加入可乐,我们看到一个结构简单、固液边界清晰的状态;由于相态分明,这个初始状态是低复杂度的。

然而,随着冰融化、能量交换,我们目睹了复杂度的上升——错综的图样与行为(如对流与气泡路径)从分子间的相互作用中涌现出来。

这种从简单到复杂的过渡,展示了系统在走向平衡的过程中如何表现出丰富的行为。融化的冰引入了多变与无序,进而带来粒子间更复杂的相互作用。熵在增加,复杂度也在增加;这层关系表明:复杂度不只关乎组分之多寡,更关乎这些组分如何动态地相互作用。

再者,一旦平衡到来、系统在均一温度下稳定下来,我们看到可观测的复杂度下降了。那些错综的图样消融为一个均匀的状态,只剩很少的特征。

这暗示着:复杂度虽可由无序与相互作用而生,却也会随着系统趋于稳定而消退。

小结

在一个封闭系统中,我们看到熵单调增加,但复杂度并非如此。随着系统变得无序,它的复杂度会先上升、抵达一个最大值,而后回落。

柯尔莫哥洛夫复杂度

柯尔莫哥洛夫复杂度(Kolmogorov Complexity),从信息论的一侧给了我们描述一个问题复杂度的方法。

它(KC)通过确定”能在某个固定计算模型下生成某字符串的、最短的描述或程序”的长度,来量化该字符串或数据集的复杂度。

本质上,它衡量的是:表示一个对象或问题所需的信息量。

用它解释冰可乐

我们能用 KC 来解释这杯冰可乐的实验吗?

可以——以一种粗粒度的方式,我们可以用柯尔莫哥洛夫复杂度来分析:随着冰在可乐中融化,系统的复杂度如何演化。

起初,冰块刚加入时,系统处于一个相对简单的状态,固相冰与液相可乐分明。此刻的柯尔莫哥洛夫复杂度很低,因为我们可以用一个直白的表述来描述它:“可乐里的冰块”。

当冰开始融化,能量传递发生,分子间的相互作用与无序随之增加。这一过渡引入了更错综的图样与行为,例如液体内部形成的对流与气泡。在这个阶段,柯尔莫哥洛夫复杂度上升,因为需要更详尽的描述才能刻画这些动态相互作用与涌现现象。 我们可能不仅要描述冰与可乐的存在,还要描述它们如何随时间相互作用——温度变化、分子运动、能量传递。

最终,当平衡到来、系统在均一温度下稳定,我们观察到可观测复杂度的下降。此时,尽管熵因无序而居高,柯尔莫哥洛夫复杂度却可能再次下降,因为系统现在可以简单地描述为”均匀的冰可乐”。这说明:虽然在封闭系统里熵倾向于单调增加,复杂度却会随着组分动态相互作用的不同阶段而起伏。

复杂度与 KC

我们可以用柯尔莫哥洛夫复杂度来解释这一现象,但 KC 只是一个理论构造,并不能涵盖真实世界复杂性的方方面面。

在实际应用中,KC 可能忽略诸如环境影响、外部相互作用,以及复杂系统固有的不可预测性等因素;它也没有考虑到那些会显著影响复杂性如何显现的时间动态与情境变化。因此,尽管 KC 为我们理解复杂性的本质提供了宝贵的洞见,它仍应与其他方法互补,才能完整地理解像冰可乐实验这样的动态系统中所观察到的多面行为。

作为人的感受,系统的复杂度是迅速攀升的;但 KC 只以对数的速度增长,这非常反直觉。在这背后,或许还有某种潜在的本质,左右着我们对复杂度的感知。

---

参考:Scott Aaronson — The First Law of Complexodynamics

How people evaluate the complexity of a problem

Evaluating the complexity of a problem involves understanding several interrelated factors that can influence an individual’s perception and experience. These factors include knowledge, measurement, predictability, and available resources.

Knowledge refers to the background information and expertise a person possesses, which can significantly shape their ability to navigate complex tasks.

Measurement pertains to how we quantify or assess the intricacies of a problem, often relying on metrics or criteria that may vary across different contexts.

Predictability relates to how foreseeable the outcomes of a problem are; more predictable problems tend to be perceived as simpler, while those with uncertain outcomes may be viewed as more complex.

Lastly, resources encompass the tools, time, and support available to an individual, which can either facilitate or hinder their ability to tackle complexity effectively.

By considering these elements together, we can gain deeper insights into how complexity is evaluated and managed in various situations.

Disorder and order

As the 2nd Law states, in a closed system the level of disorder tends to increase over time, leading to greater entropy, until the system reaches a state of equilibrium.

In our world, we observe that almost all systems tend to evolve toward greater disorder if not managed by external forces. You can sense that if you attempt to accomplish something on your own without any guidance or structure, things will eventually become chaotic and unmanageable. Ultimately, you may find that tasks become overwhelming and cannot be completed.

We also apply the concept of entropy to information systems — for example, when we use “cross-entropy” to train large models. This connection illustrates how uncertainty and disorder in data can affect the performance of algorithms. In machine learning, higher entropy often indicates more disorder in the model’s prediction distribution. Minimizing cross-entropy during training helps models learn to make accurate predictions, and this is precisely what we aim to achieve.

Intuitively, disorder and order are intricately linked, as increased disorder often results in heightened complexity. Making things well-ordered is essential to finding the balance and structure that achieve simplicity in problem-solving.

More disordered things are more complex. This is an instinctive feeling in our daily lives.

Complexity and simplicity

It is not easy to evaluate whether a work is complex or simple with an objective measurement. Complexity can often be subjective: what one person finds intricate and challenging, another may perceive as straightforward and manageable.

Factors such as prior knowledge, experience, and the specific context in which a task is approached can significantly influence this judgment.

Additionally, the tools and resources available to an individual can either simplify or complicate their perception of a task’s complexity. Thus, understanding complexity requires not only an analysis of the task itself but also an awareness of the individual’s unique perspective and circumstances.

Complexity is also hard to define. One informal definition is: complexity is the minimal amount of resources (information, energy, computation, or description length) required to specify, predict, or generate a system or problem.

The relationship between disorder and complexity

To explore this relationship further, we can consider that complexity often arises from the interactions and dependencies within a system. In many cases, as disorder increases, the number of possible states or configurations of a system also increases, leading to greater complexity.

For instance, in information theory a highly disordered dataset may require more sophisticated algorithms to extract meaningful patterns or insights, as the noise can obscure relevant signals.

Similarly, in physical systems, increased entropy can lead to more complex behaviors that are difficult to predict or control.

Moreover, in computational contexts, algorithms designed to handle complex problems often need to account for various sources of disorder, such as noise in data or variability in user behavior. This necessitates the development of robust models that can adapt to changing conditions while still providing accurate outputs.

In essence, while disorder can contribute to complexity by introducing uncertainty and variability, it is also essential to recognize that not all complexity is inherently negative. Some degree of complexity is necessary for systems to function effectively and adaptively. Therefore, understanding the balance between order and disorder is crucial for managing complexity in any domain — technology, biology, or social systems. Ultimately, this interplay shapes our approach to problem-solving and innovation.

Problem setup

Let’s set up a problem and take some observations from it.

You have a bottle of Coke. You open it, put some ice cubes into it, and close the bottle again. The main observations from this environment are:

• At the start: a clear boundary — solid cubes in liquid.
• In the middle: intricate, lace-like melt fronts, convection plumes, and bubbly paths — rich, multiscale geometry.
• In the end: temperature equalizes; the drink is uniformly cold and still. Few features remain.

Explanation by the 2nd law of thermodynamics

According to the second law of thermodynamics, the total entropy of an isolated system can never decrease over time.

Initially, when the solid ice cubes are placed in the liquid Coke, there is a clear distinction between the solid and liquid phases — a state of low entropy.

As the ice melts, energy is transferred from the warmer liquid to the colder ice, increasing disorder as the molecules in both phases begin to mix. This process produces intricate patterns and convection currents as heat flows and phase changes occur. Entropy increases.

Eventually, as equilibrium is reached, the system’s entropy maximizes, resulting in a uniform temperature throughout the drink with minimal features remaining. This progression illustrates how systems evolve towards greater disorder over time, aligning with the principles outlined by the second law.

Thinking in a simple mathematical way

The 1st law of thermodynamics tells us:

$$\Delta U = Q - W$$

where $U$ represents the total energy contained within the system, including both the kinetic and potential energy of its particles. $Q$ is the heat added to the system, and $W$ is the work done.

Let the energies of the Coke, the ice, and the melted ice be $U_{coke}$, $U_{ice}$, and $U_{melt\ ice}$, with $U_{total}$ the final iced Coke’s energy. Because energy is conserved,

$$\Delta U_{\text{coke}} + \Delta U_{\text{ice}} + \Delta U_{melt\ ice} = 0$$

From the entropy side, we can define the entropy of this system as $S_{sys}$. No matter what happened as the Coke cooled or the ice cubes melted, the entropy of this closed system increases monotonically until equilibrium, so

$$\Delta S_{sys} \ge 0$$

How about the complexity?

Complexity in this context can be understood as a measure of how the interactions between different components of a system evolve over time. Initially, when the ice cubes are added to the Coke, we observe a simple structure with clear boundaries between solid and liquid. This initial state represents low complexity because of the distinct phases.

However, as the ice melts and energy is exchanged, we witness an increase in complexity characterized by intricate patterns and behaviors — such as convection currents and bubbly paths — emerging from the interactions of molecules.

This transition from a simple to a complex state illustrates how systems can exhibit rich behaviors as they move towards equilibrium. The melting ice introduces variability and disorder, which in turn leads to more complex interactions among particles. As entropy increases, so does complexity; this relationship highlights that complexity is not merely about having many components, but also about how those components interact dynamically.

Moreover, once equilibrium is reached and the system stabilizes at a uniform temperature, we see a reduction in observable complexity. The intricate patterns dissolve into a homogeneous state where fewer features are present.

This suggests that while complexity can arise from disorder and interactions, it can also diminish as systems reach stable states.

Conclusion

In a closed system, we observe that entropy increases monotonically, but complexity does not. As the system becomes disordered, its complexity rises and reaches a maximum before decreasing.

The Kolmogorov complexity

Kolmogorov complexity gives us a way to describe the complexity of a problem from the information-theory side.

Kolmogorov complexity (KC) quantifies the complexity of a string or dataset by determining the length of the shortest possible description — or program — that can generate that string using a fixed computational model.

In essence, it measures how much information is required to represent an object or problem.

Explaining the iced Coke

Can we use KC to explain the iced-Coke experiment?

Yes — in a coarse-grained way, we can apply Kolmogorov complexity by analyzing how the complexity of the system evolves as ice melts in Coke.

Initially, when ice cubes are added, we have a relatively simple state characterized by distinct phases — solid ice and liquid Coke. The Kolmogorov complexity at this stage is low because we can describe the state with a straightforward representation: “ice cubes in Coke.”

As the ice begins to melt, energy transfer occurs, leading to increased molecular interactions and disorder. This transition introduces more intricate patterns and behaviors, such as convection currents and bubbles forming within the liquid. The Kolmogorov complexity increases during this phase because a more detailed description is required to capture these dynamic interactions and emergent phenomena. We might need to describe not just the presence of ice and Coke, but also how they interact over time — temperature changes, molecular movement, and energy transfer.

Eventually, when equilibrium is reached and the system stabilizes at a uniform temperature, we observe a reduction in observable complexity. At this point, while entropy remains high due to disorder, the Kolmogorov complexity may decrease again, because the system can now be described simply as “uniform iced Coke.” This illustrates that while entropy tends to increase monotonically in a closed system, complexity can fluctuate based on how components interact dynamically throughout the different phases of the process.

The complexity and the KC

We can explain this phenomenon using Kolmogorov complexity, but KC is just a theoretical construct that does not account for all aspects of real-world complexity.

In practical applications, KC may overlook factors such as environmental influences, external interactions, and the inherent unpredictability of complex systems. It also does not account for the temporal dynamics and contextual variations that can significantly affect how complexity manifests in real-world scenarios. Thus, while KC offers valuable insights into the nature of complexity, it should be complemented with other approaches to fully understand the multifaceted behaviors observed in dynamic systems like the iced-Coke experiment.

As a human feeling, the system’s complexity rises rapidly — but KC increases only at a logarithmic speed, which is deeply unintuitive. There should be some other latent essence that shapes our perception of complexity.

---

Reference: Scott Aaronson — The First Law of Complexodynamics