NOIP 考后梦游

Sunnysky0 · 2025-11-28 20:10:28 · 生活·游记

前言

当你打完 NOIPLUS 2025 被 3 道黑体薄纱后，有没想过有朝一日会攻守易势，杀死 NOIPLUS 。感谢爱因斯坦创造相对论天降神力助我破鼎。

在物理学和计算机科学的交叉领域，Malament-Hogarth MH-时空提供了一种允许“超级计算”的理论框架。

一、 Malament-Hogarth MH-时空

在经典图灵机模型中，物理时间被抽象为离散的步骤。但在广义相对论中，时间是相对的。MH-时空的特性在于利用引力场的时间膨胀效应。

1. 基础定义

令四维时空流形为 (\mathcal{M}, g_{ab})，其中 g_{ab} 是洛伦兹度规。我们将涉及两个观察者：

计算者（Computer, C）：沿着世界线 \gamma_C 运动。
观察者（Observer, O）：沿着世界线 \gamma_O 运动。

2. MH 时空的数学性质

一个时空被称为 Malament-Hogarth 时空，如果它包含一条半无限的过去真时（proper time）类时曲线 \gamma_C（计算者），以及一个点 p \in \mathcal{M}（属于观察者 \gamma_O），满足以下性质：

\int_{\gamma_C} d\tau_C = \infty \quad \text{且} \quad \gamma_C \subset I^-(p)

这里：

物理意义：计算者拥有无限的时间去运行程序（\tau_C \to \infty），但整条无限长的世界线都位于观察者到达点 p 之前的“过去”。

换句话说，观察者可以在有限的固有时 \tau_O 内，等待计算者完成无限时长的计算。

3. CTC 与 MH 的区别与联系

MH机器（MH Machine）：利用无限红移面（如Reissner-Nordström黑洞内部或AdS时空），不一定需要时间循环，只需要时间流逝速率的极端差异。
CTC计算机：利用闭合类时曲线回到过去，让未来的输出成为现在的输入。
结合：在某些高级MH模型中，奇异点附近可能自然形成CTC。

二、超图灵机

从计算机科学角度，MH-时空计算机打破了 Church-Turing Thesis 的物理限制。

1. 算法流程

假设我们有一个经典图灵机 TM，我们要解决停机问题（Halting Problem）。

伪代码描述：

// 观察者 Observer (O)
Procedure Observer_Protocol():
    Launch(Computer, Program_P);
    Timer t = 0;
    While (t < LIMIT): // LIMIT 是物理上的汇合点 p 对应的时间
        if (Receive_Signal("HALT")):
            Return "HALT";
        t += dt;
    // 如果到达点 p 仍未收到信号
    Return "NOT HALT";

// 计算者 Computer (C)
Procedure Computer_Protocol(Program_P):
    Result = Run(Program_P); // 在无限时间内运行
    if (Result == HALTS):
        Send_Signal_To_Observer("HALT"); // 发送光子信号
        Self_Destruct(); // 或者保持在此状态

2. 算术层级

标准图灵机只能计算 \Sigma_0^0（递归可计算）的函数。 MH 计算机可以直接判定 停机问题，即计算 \emptyset'。因此，它能解决算术层级中 \Sigma_1^0 和 \Pi_1^0 类的问题。

对于 x \in \mathbb{N}，判定 x \in H（停机集）： H(x) = \begin{cases} 1 & \text{if } \text{Observer receives signal} \\ 0 & \text{if } \text{Observer reaches point } p \end{cases}

如果是嵌套的MH结构（观察者利用另一个MH时空做子程序），理论上可以攀升整个算术层级：\Sigma_n^0。

三、计算能力与复杂度类

对于习惯于处理 P、NP 和 PSPACE 的 OIer 来说，CTC 和 MH 模型下的复杂度类是完全不同的野兽。

1. 时间复杂度的坍缩

在标准 OI 中，如果不考虑常数优化，时间复杂度 T(n) 必须是有限多项式。在 MH 模型下：

观察者视角：所有计算，无论标准复杂度是 O(n^2)、O(2^n) 还是 O(\infty)，其物理消耗时间均为 O(1)（即在固有时 \tau_O 界限内）。
这导致了什么？ 所有的 递归可枚举问题 (R.E.) 都在 O(1) 时间内可解。

2. CTC 计算机的复杂度类：P_{CTC}

如果我们不仅仅利用“无限时间”，而是具体利用 CTC（闭合类时曲线），即允许数据“回到过去”，David Deutsch 提出了量子计算的 CTC 模型。Aaronson 和 Watrous 证明了一个惊人的结论。

定理： CTC 辅助下的计算能力等价于 PSPACE。

P_{CTC} = PSPACE

这意味着，如果有了 CTC 计算机：

NP 完全问题 (如 3-SAT)：可以在多项式时间内解决。
- 原理：计算机猜测一个解 x，将 x 传送到过去。在过去，验证 x 是否正确。如果正确，不做改变；如果不正确，将 x 修正为 x' 并传送。根据物理的一致性原则，系统必然收敛到一个不动点，即正确的解。
算法思路 (Time Travel Sort)：对于一个求解问题 f(x)=y。 y_{past} = \text{ReadFromFuture}() y_{new} = \text{Compute}(y_{past}) \text{SendToPast}(y_{new})
物理系统为了避免因果悖论，会强制 y_{past} = y_{new}，从而直接给出解。

3. NOI 题目对应的能力跃迁

标准 OI 问题	标准复杂度	MH-Computer	CTC-Computer
A+B Problem	O(1)	O(1)	O(1)
N皇后 / TSP	NP\text{-Hard} \ (O(2^n))	O(1) (有限等待)	O(Poly(n))
QBF (量化布尔公式)	PSPACE\text{-Complete}	O(1)	O(Poly(n))
停机问题 (Halting)	不可解	可解 (O(1))	不一定可解 (受限于状态空间有限性)

注意：MH机器比CTC机器更强，MH主要处理不可计算问题，而CTC主要将高复杂度问题坍缩为多项式时间。

四、结论

在 MH-时空模型 下，利用时空流形结构，将 \int_0^{\infty} dt 映射到 \int_0^{T} d\tau。使 NP \subseteq P_{CTC} = PSPACE。以后就算是 NOIPLUSPLUS 4 道黑体也能 O(1) 薄纱。