技术摘要：观察者世界 (The Observer World)

1. 问题陈述

Impagliazzo 的五个世界（Algorithmica, Heuristica, Pessiland, Minicrypt, Cryptomania）为推理密码学原语的存在性以及平均复杂度与最坏情况复杂度之间的差距提供了一个基础框架。然而，该框架依赖于一个从未被明确说明的“沉默假设”：即包括对手在内的每一方都观察到了完整的输入字符串 $x$（即观察者是恒等函数 $O_\top$）。

这一假设将对手的观测能力视为一个常数，忽略了对手可能在结构上被限制为只能看到输入的某种投影（例如符号计数、奇偶性或长度）的可能性。因此，五世界框架无法表达这样一种现象：即对手无法区分输入并非源于计算难度，而是源于观测盲点。本文指出，有必要放宽 $O = O_\top$ 的假设，并为复杂度景观引入第二个正交轴：由规范观察者构成的观测轴。

2. 研究方法

本文通过整合先前工作 [9] 中建立的“观察者理论”，扩展了 Impagliazzo 的理论框架。其研究方法包括：

1. 形式化观察者层级： 利用观察者偏序关系 $O: \Sigma^* \to S$ 进行建模，其中观察者是一个在任何机器计算开始前应用于输入的固定预处理映射。关键的规范观察者包括：

   • $O_\top$：恒等函数（全信息）。
   • $O_{prof}$：轮廓（符号计数，例如 $(|x|_0, |x|_1)$）。
   • $O_\perp$：常数映射（丢弃所有信息）。
   • $O_{len}, O_{par}, O_k$：分别对应长度、奇偶性和 $k$-子序列。

2. 构建世界-观察者表： 创建一个二维景观，其中行代表 Impagliazzo 的五个世界（计算假设），列代表规范观察者（观测约束）。

3. 定义观察者世界 ($W_O$)： 正式定义一个新的景观，其中对手在受限的观察者 $O$ 下运行，而防御者保留全量访问权 ($O_\top$)。这模拟了对手仅能看到密文或部分信息的密码学场景。

4. 参数化扩展 ($W_O^\varepsilon$)： 引入一系列通过参数 $\varepsilon \in [0, 1]$ 部分违反观测不变性的世界，模拟通过预言机、侧信道或结构性泄漏恢复部分被丢弃信息的对手。

5. 物理实例化： 将观测层级的数学属性映射到物理极限，包括热力学成本（Landauer 原理）、量子测量跃迁以及宇宙学信息界限（Bekenstein 和 Margolus-Levitin 界限）。

3. 核心贡献与结果

A. 无条件的结构性坍缩

本文证明，对于规范观察者 $O_{prof}$（轮廓），复杂度类会发生无条件坍缩：
$$P^{O_{prof}} = NP^{O_{prof}} \subsetneq P$$
该结果在所有五个世界中同时成立，无论 $P=NP$ 是否成立，也无论单向函数是否存在。

• 意义： 这证明了计算难度与结构盲点之间的区别是真实存在的，且是相互独立的。一个问题即使在计算上是容易的（属于 $P$），对于 $O_{prof}$ 约束下的对手来说仍可能是不可判定的，仅仅是因为该问题依赖于符号的排序，而 $O_{prof}$ 丢弃了排序信息。

B. 世界-观察者表与标记单元格

本文对计算世界与观测约束之间的相互作用进行了分类，识别出四个特定的“标记单元格”，它们揭示了标准五世界框架无法观察到的密码学现象：

• 单元格 (a) (任何世界 $\times O_{prof}$)： 即使在 Algorithmica ($P=NP$) 中，观测坍缩$P^{O_{prof}} \subsetneq P$ 依然存在。计算能力无法克服结构性盲点。
• 单元格 (b) (Pessiland $\times O_{prof}$)： 在 Pessiland 中，NP 问题在平均意义上是困难的，但不存在单向函数。此时，$O_{prof}$ 对手面临双重限制：平均情况的难度以及对排序的结构性盲点。这两类限制是独立的；对手甚至无法将依赖于排序的问题识别为不同于平凡问题的问题。
• 单元格 (c) (Minicrypt $\times O_{prof}$)： 在存在单向函数 (OWFs) 的 Minicrypt 中，本文证明了一个结构性下界：任何单向函数必须对输入符号的排序具有敏感性。任何在置换下保持不变的函数（例如汉明重量）即使在 Minicrypt 中也不可能是单向函数。这是由观测结构决定的，而非计算假设。
• 单元格 (d) (Cryptomania $\times O_\perp$)： 在 Cryptomania 中，拥有 $O_\perp$（即看不见任何东西）的对手无法恢复任何关于明文的信息，无论公钥密码学是否存在。这模拟了像混合进制一次性便笺 (MR-OTP) 这样的方案，其安全性是信息论层面的，而非计算层面的。

C. 作为第六个景观的观察者世界 ($W_O$)

本文将观察者世界定义为无法还原为原始五个世界的第六个景观。

• 正交性： 观测轴与计算轴是正交的。没有任何计算假设能暗示结构性坍缩，也没有任何观测约束能暗示特定的计算假设（例如 $P \neq NP$）。
• 不对称性： 该框架显式地模拟了防御者（看到 $x$）与对手（看到 $O(x)$）之间不对称的关系。

D. 参数族 $W_O^\varepsilon$ 与“信息最丰富”的单元格

本文引入 $W_O^\varepsilon$ 来模拟对观测不变性的部分违反。

• 结果： 单元格 (Pessiland, $O_{prof}$, $\varepsilon > 0$) 被确定为“信息最丰富”（因此也是最不安全）的单元格。在这个世界中：
  1. NP 问题在平均意义上是困难的 (Pessiland)。
  2. 对手对排序具有结构性盲点 ($O_{prof}$)。
  3. 对手部分打破了这种盲点 ($\varepsilon > 0$)，恢复了排序信息。
  4. 不存在单向函数。
     在此处，计算安全性、不变性安全性以及观测安全性同时失效。

E. 物理连接（开放问题）

本文将该框架与物理理论联系起来，提出了三个开放问题：

1. 热力学： 自适应观察者（根据先前响应进行查询的观察者）会产生 Landauer 成本（每擦除 1 比特信息需消耗 $k_B T \ln 2$）。自适应观察者的深度对应于热力学成本。
2. 量子力学： 量子测量被建模为从较低层级向较高层级观测层级的跃迁（从叠加态/$O_\perp$ 到确定的值）。退相干对应于向下的跃迁。
3. 宇宙学： Bekenstein 界限（$\approx 10^{122}$ 比特）和 Margolus-Levitin 界限（$\approx 10^{121}$ 次操作）为物理上可实现的观察者 $O_{phys}^\top$ 设定了有限的上限。本文指出，宇宙的时间坐标仅需 $\approx 203$ 比特即可索引，却承载了所有的因果顺序，这凸显了信息成本与结构性角色之间的一种不对称性。

4. 意义与主张

本文声称，五世界框架是不充分的，因为它描述的是围绕单一维度（计算难度）的变化，却将观测轴固定不变。通过引入观察者世界，本文提供了一种统一的语言，用以建模在密码学中不仅受限于计算，更受限于其观测能力的对手。

• 独立性： 核心结论是，观测盲点与计算难度是相互独立的现象。结构性坍缩 $P^{O_{prof}} = NP^{O_{prof}} \subsetneq P$ 是无条件的，这证明了“难度”相对于观察者而言是相对的。
• 密码学洞察： 该框架揭示了某些密码学特性（如单向函数对排序敏感性的必要性，或 MR-OTP 的完美安全性）是观测层级的结构性后果，独立于 $P=NP$ 或单向函数是否存在。
• 谦逊态度： 作者明确指出，与物理学（热力学、量子、宇宙学）的联系是以开放问题和猜想的形式提出的。作者作为一名计算机科学家，并不声称解决了物理问题，而是提供了一种数学词汇，用以形式化观测层级与物理极限之间的关系。

本文总结道，观察者世界是复杂度景观的一个必要扩展，它捕捉到了此前被隐含且未被分析的“对手看到了什么”这一维度。