复杂性 · 算法 · 集合论 · 模型论 · 可计算性 · 离散动力
| 名称 | 子领域 | 提出时间 | 难度 | 关注度 | 奖金 | 当前进展 |
|---|---|---|---|---|---|---|
| ▶P vs NP 千禧 | 计算复杂性 | 1971 | ★★★★★ | ★★★★★ | $1,000,000 | 所有已知证明路径均被排除。 |
P vs NP可多项式时间验证 ⇒ 可多项式时间求解？Relativization (1975)、Natural Proofs (1994)、Algebrization (2008) 三大障碍。GCT 与代数复杂性提供潜在路径。 | ||||||
| ▶NP vs coNP | 复杂性 | 1970s | ★★★★★ | ★★★★ | 无 | 普遍相信 ≠；证明 ⇒ P ≠ NP。 |
NP vs coNP是否每 coNP 问题有短证书？等价问 "是否每 unsatisfiable 公式都有短反驳"。是有效证明长度核心问题。 | ||||||
| ▶L vs NL | 空间复杂性 | 1970s | ★★★★ | ★★★ | 无 | Savitch NL ⊆ DSPACE(log² n)；L = NL 开放。 |
L vs NL对数空间的确定性 vs 非确定性。Reingold 2004 证 SL = L（无向连通性 in L）；定向 NL 仍开放。 | ||||||
| ▶Unique Games 猜想 | 近似算法 | 2002 | ★★★★ | ★★★★ | 无 | Khot–Minzer–Safra 2018 证 2-to-2 Games。 |
UGC若成立，确定大量 NP-hard 问题的最优近似比 = SDP 给出的比 (Raghavendra 2008)。 | ||||||
| ▶指数时间假设 (ETH / SETH) | 细粒度复杂性 | 2001 (Impagliazzo–Paturi) | ★★★★ | ★★★★ | 无 | 驱动细粒度复杂性整个领域。 |
SETH$k$-SAT 无 $(2 - \varepsilon)^n$ 算法。蕴含 OV、APSP、editdistance 等大量"硬"问题的下界。 | ||||||
| ▶BQP vs PH | 量子复杂性 | 1993 | ★★★★ | ★★★ | 无 | Raz–Tal 2018 证 oracle 分离。 |
BQP vs PH量子多项式 BQP 是否被多项式层级 PH 包含？Raz–Tal 给出强 oracle 分离；无 oracle 一般答案未知。 | ||||||
| ▶BPP = P | 去随机化 | 1990s | ★★★★ | ★★★★ | 无 | 条件证（IW 1997 在 strong circuit lower bound 下）。 |
BPP = P"随机算法可去随机化"是普遍信念；Impagliazzo–Wigderson 1997 在 E 需要 $2^{\Omega(n)}$ circuit 下证 BPP = P；下界开放。 | ||||||
| ▶Permanent vs Determinant（VP vs VNP） | 代数复杂性 | 1979（Valiant） | ★★★★★ | ★★★★ | 无 | 超多项式下界开放；已知 $\Omega(n^2)$。 |
Valiant 代数 P vs NPpermanent 不可用多项式大小算术电路（VP）表达？最佳下界 $\Omega(n^2)$；GCT (Mulmuley–Sohoni) 试图用几何不变量证。 | ||||||
| ▶Boolean 电路下界（NEXP ⊄ ACC⁰⁺） | 电路下界 | 1980s+ | ★★★★★ | ★★★★ | 无 | Williams 2011 证 NEXP ⊄ ACC⁰。 |
电路下界程序对 TC⁰、NC¹、P/poly 的超线性 / 超多项式下界仍极难。Williams "algorithmic method" 是少数突破。 | ||||||
| ▶P vs PSPACE / IP = PSPACE 边界 | 复杂性层级 | 1990 | ★★★★★ | ★★★ | 无 | P ⊂ PSPACE 严格未证；IP = PSPACE 已证 (Shamir)。 |
P 与 PSPACEP ≠ PSPACE 是显然的"信念"但严格未证。任何严格分离都将是重大突破。 | ||||||
| ▶OV / APSP / 3-SUM 严格 (SETH 下) | 细粒度复杂性 | 2010s | ★★★ | ★★★ | 无 | 条件下界已证；无条件开放。 |
细粒度下界OV (Orthogonal Vectors)、APSP (All-Pairs Shortest Paths)、3-SUM 之间的还原网络精细化；无条件 ω(n^{2−ε}) 下界对许多关键问题开放。 | ||||||
| ▶Continuum Hypothesis 的"自然"扩展 | 集合论 | 1878 / Gödel 1947 | ★★★★★ | ★★★ | 无 | ZFC 独立 (Cohen 1963)；Ω-逻辑下选 ¬CH (Woodin)。 |
CH 自然性Woodin 提出 Ω-逻辑下 CH 有"明确"答案（倾向 ¬CH，后更倾向 CH 之 V=Ultimate-L）。哲学问题尚未达成共识。 | ||||||
| ▶Ultimate-L 猜想 (Woodin) | 集合论 / 内模型 | 2010s | ★★★★★ | ★★★ | 无 | 取决于 supercompact 内模型存在性。 |
Ultimate L是否存在一个能容纳所有大基数的"终极"内模型 L^{ult}。若成立，CH 在该模型成立，是集合论真理的"自然"候选。 | ||||||
| ▶HOD 猜想 (Woodin) | 集合论 | 2010s | ★★★★★ | ★★★ | 无 | 高度技术性，全开放。 |
HOD 猜想若存在 supercompact 基数，则 V 与 HOD 在足够大基数上 "接近"。决定了"large cardinal vs choice" 的关键张力。 | ||||||
| ▶Vopěnka 原理 / Strong reflection | 集合论 | 1970s | ★★★★ | ★★ | 无 | 大基数公理；与 ZFC 独立但相对一致。 |
Vopěnka 原理极强大基数公理；其在不同基数层级的精确强度与含义仍是研究热点。 | ||||||
| ▶Hilbert 第十问题（实数 / ℚ） | 可计算性 / 模型论 | 1900 | ★★★★ | ★★★ | 无 | ℤ 上 MRDP 1970 不可解；ℚ 上开放。 |
Hilbert 10 over ℚℚ 上 Diophantine 方程可解性是否可判定？倾向不可判，但严格证明仍缺。Koenigsmann、Park、Mazur 等给部分进展。 | ||||||
| ▶Schanuel 猜想 (模型论版) | o-minimal | 1960s | ★★★★★ | ★★★ | 无 | 蕴含 ℝ_{exp} 可判定。 |
Schanuel ⇒ ℝ_{exp} 可判定Macintyre–Wilkie 1996 证：若 Schanuel 猜想成立，则 (ℝ, +, ·, exp) 的一阶理论可判定。 | ||||||
| ▶Vaught 猜想 | 模型论 | 1961 | ★★★★ | ★★★ | 无 | 特定理论已证；一般开放。 |
Vaught 猜想可数完备一阶理论的可数模型数若不是 ℵ₀ 即 2^{ℵ₀}（无中间数）。ω-stable 等情形已证（Shelah, Harrington）。 | ||||||
| ▶Boolean Pythagorean Triple (推广) | SAT / 组合 | 2016 | ★★★ | ★★ | 无 | {1..7824} Heule–Kullmann–Marek 2016 解决；推广开放。 |
Pythagorean Triple Coloring原版（2-着色 {1..N}）n=7825 不可行（200TB SAT 证明）。3-着色版本 / 几何类比开放。 | ||||||
| ▶Cohomological Coordination (FOM 程序) | 逻辑基础 | — | ★★★★ | ★ | 无 | Reverse mathematics 中各种 Π¹₂ 命题强度未确定。 |
Reverse Math 开放例如 Hindman 定理在 RCA₀ 下精确证明强度；许多组合 / 拓扑命题在反向数学层级中未定。 | ||||||
| ▶Aanderaa–Karp–Rosenberg (evasiveness) | 判定树复杂性 | 1973 | ★★★★ | ★★ | 无 | 单调图性质 evasiveness 一般开放。 |
Evasiveness Conjecture所有非平凡 monotone graph property 是 evasive（判定需查询所有 (n,2) 边）。素数 n 情形 Kahn–Saks–Sturtevant 1984 用拓扑不动点证；一般开放。 | ||||||
| ▶对称 Krohn–Rhodes 复杂度 | 有限半群 | 1965 | ★★★ | ★ | 无 | 复杂度可计算性开放。 |
Krohn–Rhodes 复杂度有限半群的 Krohn–Rhodes 复杂度（最少 group 复杂度因子数）是否可计算？长期开放问题。 | ||||||
| ▶Černý 猜想 | 自动机 | 1964 | ★★★ | ★★★ | 无 | 最佳上界 $(15 n^3 + \ldots)/96$；猜想 $(n-1)^2$。 |
Černý 猜想$n$ 态同步自动机最短同步字长 $\le (n - 1)^2$。Pin 1983 给立方上界；Szykuła 2018 微改进至 $(114 n^3 - \ldots)/725$。下界 $(n - 1)^2$ 由 Černý 序列达到。 | ||||||
| ▶Collatz 可判定性 | 动力 / 可计算性 | 1937 | ★★★★ | ★★★★ | 小额历史悬赏 | Tao 2019 几乎处处有界。 |
Collatz 猜想3n+1 序列总到 1。Conway 证一般化 Collatz 类问题 Turing-undecidable，留下原 Collatz 是否本质同样困难。 | ||||||
| ▶Busy Beaver BB(6) / BB(5) (后续) | 可计算性 | 1962 | ★★★ | ★★★ | 无 | BB(5) = 47176870 由 bbchallenge 2024 确定。 |
Busy Beaver5 状态停机最大步数 BB(5) 由分布式 bbchallenge.org 2024 确定 $= 47{,}176{,}870$；BB(6) 已知 $\gg 10^{10^{10^{10^{10^{2.5}}}}}$，不可计算（与 ZFC 独立 above some $n$）。 | ||||||