计算科学中“二容易,三难”的好例子

计算科学 线性代数 计算物理学 计算几何 计算化学
2021-11-25 19:56:17

我最近遇到了一个元现象的表述:“二易,三难”(Federico Poloni 曾这样表述),可以描述如下:

当为两个实体制定某个问题时,相对容易解决;然而,三实体公式的算法极大地增加了难度,甚至可能使解决方案不可行或无法实现。

(我欢迎提出使措辞更优美、简洁和准确的建议。)

你知道在计算科学的各个领域(从纯线性代数开始,到一揽子计算物理学结束)有哪些好的例子吗?

4个回答

出现在许多物理学领域,尤其是经典力学和量子物理学中的一个例子就是二体问题。这里的二体问题是指计算两个相互作用粒子的动力学任务,例如,通过重力或库仑力相互作用。这个问题的解决方案通常可以通过将变量转换为质心和相对坐标以封闭形式找到。

但是,只要考虑三个粒子,通常不存在封闭形式的解

在一维和二维上,条条大路通罗马,但在三维上却不是。

具体来说,给定一维或二维整数上的随机游走(沿任何方向移动的可能性相同),那么无论起点如何,概率为 1(也就是几乎肯定),随机游走最终将到达特定的指定点(“罗马”)。

但是,对于三个或更多维度,到达“罗马”的概率小于1;随着维数的增加,概率降低。

因此,例如,如果对从“罗马”开始的随机游走进行随机(蒙特卡洛)模拟,当返回罗马时将停止,那么在一维和二维中,您可以确保最终返回罗马并停止模拟 - 如此简单。在三个维度上,你可能永远都回不来了,太难了。

https://en.wikipedia.org/wiki/Random_walk#Higher_dimensions

为了可视化二维情况,可以想象一个人在城市中随意走动。这座城市实际上是无限的,并排列在人行道的方形网格中。在每个十字路口,该人随机选择四种可能的路线之一(包括最初旅行的路线)。形式上,这是在具有整数坐标的平面中所有点的集合上的随机游走。

这个人会回到步行的原始起点吗?这是上面讨论的水平交叉问题的二维等价物。1921 年 George Pólya 证明了这个人几乎肯定会在 2 维随机游走中,但对于 3 维或更高维,返回原点的概率随着维数的增加而降低。在 3 个维度上,概率降低到大约 34%

有关数值,请参见http://mathworld.wolfram.com/PolyasRandomWalkConstants.html 。

一个著名的例子是布尔可满足性问题(SAT)。2-SAT 在多项式时间内求解并不复杂,但 3-SAT 是 NP 完全的。

在社会选择理论中,设计一个有两个候选人的选举方案很容易(多数规则),但设计一个有三个或更多候选人的选举方案必然涉及在各种听起来合理的条件之间进行权衡。阿罗不可能定理)。