数学家发现第九个 Dedekind 数

2023-11-20 15:50 by 科玛

在历尽逾三十年的搜索之后，在超级计算机的帮助下，数学家发现了第九个 Dedekind 数。Dedekind 数由德国数学家 Richard Dedekind 在 1897 年定义，其核心是布尔函数（即其值为 false 或 true），它是将 n 个布尔变量作为输入，生成另一个布尔变量作为输出的函数。前六个 Dedekind 数都非常简单，D(1)是 2，之后是 3、6、20、168、7581，后面的数愈来愈大。1991 年当时最强大超算之一的 Cray-2 花了 200 小时计算出 D(8)，32 年后德国帕德博恩大学的数学家使用 Noctua 2 超算和现场可编程门阵列(FPGA)计算出 D(9)为 286 386 577 668 298 411 128 469 151 667 598 498 812 366，这是一个 42 位的数。D(10)无疑也要花费很长时间才可能发现。

https://www.sciencealert.com/mathematicians-have-found-the-ninth-dedekind-number-after-32-years-of-searching
https://en.wikipedia.org/wiki/Dedekind_number

#数学

研究人员发现更快的整数线性规划求解方法

2024-01-30 15:57 by 会飞的人

旅行推销员问题是最古老的计算问题之一：“给定一系列城市和每对城市之间的距离，求解访问每座城市一次并回到起始城市的最短回路。”看起来简单，但求解十分困难。它被认为是一个 NP 完全问题。它的一种形式化方法是整数线性规划。60 多年以来研究人员提出多种解决整数线性规划的算法，但都比较慢，过去四十年改进甚微。普林斯顿高等研究院的 Victor Reis 和华盛顿大学的 Thomas Rothvoss 最近的工作实现了整数线性规划求解算法的最大速度提升，被认为代表了近 40 年来首次求解器的重大改进。他们通过组合了几何工具去限制可能的解决方案，创造了一种更快的算法。

https://www.quantamagazine.org/researchers-approach-new-speed-limit-for-seminal-problem-20240129/
https://arxiv.org/abs/2303.14605

#数学