算法与理论计算机2021arxiv.org编辑精选
最小割算法运行时间 25 年来首次改进（2019）
Runtime improvement for Minimum Cut algorithm first time in 25 years (2019)
专业 · 约 90 分钟读完前置知识：图论基础、最小割与最大流、算法复杂度分析
导读
这篇论文研究无向图的全局最小割（global min-cut，即边连通度）算法，并给出了运行时间上的改进——该问题的复杂度上界约 25 年没有被实质性推进（2019 年）。评论中的关键澄清是：这里的“最小割”不是最大流最小割定理中固定 s、t 的最小割，而是把图任意分成两部分的全局最小割。
HN 关注点：一项长期停滞的经典图算法复杂度纪录被打破，以及随之而来的“这到底有什么用、工程上实现得了吗”的争论。
HN 评论精选
这几条评论里：质疑 2 补充 2
补充澄清这是全局最小割，与最大流最小割（固定 s、t）不是同一个问题。
其他评论者已经有一些误解了。这里的最小割不同于最大流最小割定理里的最小割。这里指的是全局最小割（global min-cut），它不固定端点。最大流最小割定理讨论的是把两个固定顶点 s 和 t 断开；而全局最小割是把任意的两个顶点断开。来源：我的学位论文做的就是超图最小割。
chaoxu查看英文原文
There are a few misconceptions that some other commenters are already making. This min-cut is different from the max-flow min-cut theorem's min-cut. This is what referred to as global min-cut, which does not fix the terminals. In max-flow min-cut theorem, it is about disconnecting two fixed vertices s and t. In the global min-cut, it is about disconnecting two arbitrary vertices. Source: thesis was on hypergraph min-cut
质疑质疑问题的实用价值：最小割常常只是孤立度最小的单个节点。
有人能给出这个问题的更具体例子吗？我读了维基页面，印象是：几乎所有情况下，最小割就是把某一个节点与其余节点分开。如果结果的两部分之一通常只是一个单节点，那这个算法听起来既不算计算困难，也没什么用处……
londons_explore查看英文原文
Can someone give a more concrete example of this problem? I read the wiki page[1], and I'm left with the impression that for almost all cases, the minimum cut will be to pick a node and seperate it from the rest of the nodes. It doesn't sound like a very computationally difficult or useful algorithm if one of the two parts of the results usually consists of a single node... [1]: https://en.wikipedia.org/wiki/Minimum_cut
补充补充当前最快实现的论文与开源代码。
顺着这个话题，这里有一个该问题目前最快的实现：https://arxiv.org/abs/1808.05458 ，GitHub 代码在 https://github.com/viecut/viecut
0x23查看英文原文
On that note, here is the currently fastest implementation for the problem https://arxiv.org/abs/1808.05458 and here on github https://github.com/viecut/viecut
质疑关心理论改进是否能落地为实用实现。
提问：这个算法实现起来实用吗？
saagarjha查看英文原文
Question: is this algorithm practical to implement?
相关资源
从这篇论文所有 HN 讨论帖的全部评论里整理出来的链接。
历次讨论
- 2021Hacker News 讨论帖153 分 · 56 评
同领域还值得读
哲学家为何应关注计算复杂性
Why Philosophers Should Care About Computational Complexity (2011)
Scott Aaronson 的这篇长文论证计算复杂性理论（如 P vs NP、停机问题的复杂度视角）对哲学问题（如知识的本质、中文房间、水槽论证等）具有实质意义，而不仅是技术细…
算法与理论计算机2015 · 552 分 · 120 评进阶 · 约 90 分钟编辑精选通信的数学理论
A Mathematical Theory of Communication
是香农1948年的《通信的数学理论》，为通信建立数学框架：把信息量定义为不确定性或自由度（信息熵），并讨论信源编码、信道容量与可靠传输。
算法与理论计算机2020 · 495 分 · 91 评进阶 · 约 120 分钟编辑精选物理、拓扑、逻辑与计算：罗塞塔石碑
Physics, Topology, Logic and Computation: A Rosetta Stone (2009)
用范畴论充当“罗塞塔石碑”，试图在量子物理、拓扑、逻辑与计算四个领域之间建立统一的结构性类比：物理中的量子过程、拓扑中的配边、逻辑中的证明和计算中的程序，都可被视为某类范畴中的态…
算法与理论计算机2009 · 390 分 · 55 评 · 引用 13专业 · 约 180 分钟编辑精选一种快速、极小内存的一致性哈希算法
A Fast, Minimal Memory, Consistent Hash Algorithm
论文给出一种快速、省内存的一致哈希方案，目标是在桶数量变化时保持较小的键迁移成本，同时降低计算和内存开销。
算法与理论计算机2014 · 327 分 · 57 评 · 引用 4进阶 · 约 25 分钟编辑精选第五个 Busy Beaver 值的确定
Determination of the fifth Busy Beaver value
宣布确定了第五个 Busy Beaver 值 BB(5)：即 5 状态图灵机中停机前运行步数最多的机器（Champion）在 47,176,870 步后停机。
算法与理论计算机2025 · 288 分 · 116 评 · 引用 1专业 · 约 75 分钟编辑精选