若取经的目标是「到达灵山」,那是一个 P 问题,一个筋斗就解完了;但取经要的是走满八十一条证书,解本身不是交付物,验证记录才是。
《西游记》第九十九回「九九数完魔灭尽 三三行满道归根」,五方揭谛呈上「灾难簿」,观音从头看过,见只有八十难,急传声道:「佛门中九九归真。圣僧受过八十难,还少一难,不得完成此数。」即命揭谛赶上金刚,再生一难。
任何一本计算复杂性教材都会先指出一件事:复杂性类是对无限问题族在输入规模 n→∞ 时的渐近刻画。八十一难是 81 个固定实例,严格地说,任何有限集合的时间上界都是 O(1),既不是 NP-Complete,也不是 P。若直接给每一难贴 P 或 NP 的标签而不作说明,这个框架从第一句起就不成立。
所以本文做的是另一件事:把「一难」看作参数化问题族的一个模式——n 是三界名录的规模、候选身份的个数、路径的长度、约束的条数;比较的也不是绝对耗时,而是三层成本之间的关系:
- 构造解(从表象找出脱难方案)要付多少搜索;
- 验证解(给定方案,施行并确认此难已解)要付多少代价;
- 获取外部信息(是否需要查询一个自己不持有的名录)是否构成独立的一步。
复杂性理论里最有生命力的那组区分,恰恰就是这三层:找到解与认出解,以及允许调用神谕时二者会发生什么。八十一难把这三层关系演了八十一遍,这才是它值得用 P / NP 来读的理由。
下文所有 NC* 标记都是隐喻性的,表示「在叙事结构上充当同类问题的通用 hardest case」,不构成 Cook–Levin 式的多项式归约证明。本文也不声称对 P ?= NP 有任何主张——那是尚未解决的数学问题,《西游记》既没有证明它,也没有暗示它。
设一难为实例 x = (地点, 队伍状态, 妖魔表象, 可用资源, 时限)。 设脱难方案为证书 w(关键身份、克制物、法宝、救援者、路径选择)。 设验证器 V(x, w) 为「按 w 施行,此难是否解除」。
在原著里,V 几乎总是廉价的:喊一声名号、亮一件法宝、请一位主人,妖魔立刻现形。真正昂贵的是从 x 反推 w。因此绝大多数难的固有形状是 NP,而不是「打不过」——打不过是算力描述,不是问题结构描述。
| 记号 | 计算含义 | 西游判据 | 代表难 |
|---|---|---|---|
| P | 存在 poly(n) 的确定性求解算法 | 不需外部信息,按确定动作序列即可脱身;含「规模大但线性」的情形 | 稀柿衕秽阻、赛城扫塔、收降八戒 |
| NP | 解长度 poly(n),验证 poly(n),构造靠搜索 | 解是「它是谁/哪件法宝/谁是主人」这类短证书;猜中一验即明,反推需遍历名录 | 黄风怪阻、无底洞遭困、天竺招婚 |
| NC* | 隐喻性 NP-Complete | 多条约束互相牵制、须同时满足,且常规策略全部归约到同一个换表示动作 | 金兜山遇怪、普天神难伏、诸天神遭困 |
| NH | NP-Hard(优化/函数型) | 目标不是「能否通过」,而是「代价最小的通过方案」;验证「已最优」本身困难 | 难活人参、西梁国留婚、朱紫国行医 |
| PS | PSPACE(量词交替/博弈) | 与对手多回合交替出招,需维护整棵状态与策略树,不能只记当前步 | 大赌输赢、莲花洞高悬、求取芭蕉扇 |
| coNP | 补问题在 NP,证伪易、证成难 | 难在证明「无」或识破高仿输入;反例短,正面证明长 | 铜台府监禁、难辨猕猴、松林救怪 |
| M | 元层级,非求解问题 | 初始设定、验证器自检、求解器增删、状态相变、完整性校验 | 金蝉遭贬、贬退心猿、凌云渡脱胎、湿经书 |
另设一维与复杂度类正交:证书来源——自求(团队内部构造)/外部·X(向三界名录查询所得)/预置·X(观音、如来事先交付)/无(该行不是求解型问题)。这一维是后文整体归类的关键证据。
阶段 I 前史与初始化(1–4)
| # | 难名 | 计算问题(形式化) | 证书 w | 类 | 证书来源 | 复杂度注记 |
|---|---|---|---|---|---|---|
| 1 | 金蝉遭贬 | 初始状态被强制降级:金蝉子 → 十世凡僧 | 无 | M | 无 | 这是实例的输入设定,不是待解问题;整个问题族由设计者注入 |
| 2 | 出胎几杀 | 出生即置于致死环境,求一条存活路径 | 转移至寺门 | P | 自求 | 解空间极小,一次状态转移即可脱离 |
| 3 | 满月抛江 | 被抛入江,需在有限时间内被第三方拾取 | 法明长老 | NP | 外部·法明长老 | 被动获救,证书由环境注入而非自求,是「外部 witness」的最早样本 |
| 4 | 寻亲报冤 | 由血书、姓氏线索反推亲子关系并复原身份 | 血书、丞相府信物 | NP | 自求 | 短证书一验即明,反推需遍历;全篇第一次完整的猜测—验证闭环 |
阶段 II 队伍组建与工具集扩容(5–16)
| # | 难名 | 计算问题(形式化) | 证书 w | 类 | 证书来源 | 复杂度注记 |
|---|---|---|---|---|---|---|
| 5 | 出城逢虎 | 遭遇确定性敌对实体,求脱身 | 直接格斗 | P | 自求 | 常数步,无搜索 |
| 6 | 落坑折从 | 随从遇害,队伍规模缩减 | 无 | M | 无 | 约束条件被改写,属实例变更而非求解 |
| 7 | 双叉岭上 | 寅将军等三怪围困,本地无解 | 太白金星解围 | NP | 外部·太白金星 | 「猜不出就查名录」的原型,神谕模式首次出现 |
| 8 | 两界山头 | 需解除五行山封印并纳入新求解器 | 六字真言压帖 | NP | 预置·观音 | 证书已被事先交付,团队执行的是验证而非发现 |
| 9 | 陡涧换马 | 鹰愁涧白马被吞,需识别吞马者 | 小白龙身份、观音 | NP | 外部·观音 | 一次名录查询把搜索压成常数 |
| 10 | 夜被火烧 | 金池长老纵火,需在火中保住唐僧 | 辟火罩 | P | 外部·广目天王 | 借工具不借知识;局部反制,常数步 |
| 11 | 失却袈裟 | 锦襕袈裟失窃,需定位持有者 | 黑熊精、守山大神之位 | NP | 外部·观音 | 归属查询,验证极快 |
| 12 | 收降八戒 | 高老庄降伏并招募 | 招募口令 | P | 自求 | 非对抗,本质是算力扩容 |
| 13 | 黄风怪阻 | 三昧神风使既有识别能力失效 | 定风丹、飞龙宝杖 | NP | 自求 | 火眼金睛被针对性攻击——验证器遭到定向失效 |
| 14 | 请求灵吉 | 求取克制三昧神风的解 | 灵吉菩萨 | NP | 外部·灵吉菩萨 | 与 13 构成「搜索失败 → 神谕查询」的成对结构,此后反复出现 |
| 15 | 流沙难渡 | 弱水不可渡,需构造可浮载体 | 九骷髅+葫芦 | NP | 预置·观音 | 证书是特定物件组合,验明即通 |
| 16 | 收得沙僧 | 流沙河降伏并招募 | 招募口令 | P | 自求 | 第二次算力扩容;至此求解器配置齐备 |
阶段 III 试心、识妖与验证器攻击(17–46)
| # | 难名 | 计算问题(形式化) | 证书 w | 类 | 证书来源 | 复杂度注记 |
|---|---|---|---|---|---|---|
| 17 | 四圣显化 | 判定团队内部是否存在「凡心」这一隐藏变量 | 撞天婚之试 | coNP | 外部·四圣(测试) | 全篇唯一一次对验证器自身做测试;要证的是「无」 |
| 18 | 五庄观中 | 推倒人参果树,求恢复不可恢复之物 | 活树之方 | NH | 自求 | 目标不是打赢,是最小化不可逆损失 |
| 19 | 难活人参 | 遍历三岛十洲求可行解,而非验证已有解 | 观音甘露 | NH | 外部·观音 | 最像 NP-Hard 的一次:求可行解,验证「别无他法」比验证解更贵 |
| 20 | 贬退心猿 | 尸魔三戏后主动删除主求解器 | 无 | M | 无 | 后续难度陡升的直接原因是算力下降,不是妖怪变强 |
| 21 | 黑松林失散 | 队伍走散,求在有限半径内恢复同步 | 路径搜索 | P | 自求 | 状态空间小,线性扫描可覆盖 |
| 22 | 宝象国捎书 | 把问题编译成一封可传递的短消息 | 书信 | NP | 外部·白龙马→悟空 | 证书化传输:把本地不可解实例转交给外部算力 |
| 23 | 金銮殿变虎 | 判别被变形者的真身并复原 | 黄袍怪(奎木狼) | NP | 外部·悟空 | 真身判别,验证一步完成 |
| 24 | 平顶山逢魔 | 五件法宝构成五条独立约束,需逐条定位 | 金角银角=老君童子 | NP | 外部·太上老君 | 每件法宝是一个 clause,解是统一归属 |
| 25 | 莲花洞高悬 | 被紫金红葫芦收摄,须在名号应答中求生 | 应答策略 | PS | 自求 | 「我叫你一声你敢答应吗」是标准的量词交替:∀名字 ∃应对 |
| 26 | 乌鸡国救主 | 辨真假国王并复活已死三年的真主 | 白玉圭、还魂丹 | NP | 外部·文殊/老君 | 证书短,验证快,构造需查两层名录 |
| 27 | 被魔化身 | 区分高仿副本与原件 | 真身特征 | coNP | 自求 | 对抗样本:负担在判别,不在搜索 |
| 28 | 号山逢怪 | 三昧真火克制既有能力集 | 观音净瓶之水 | NP | 外部·观音 | 相克关系是外部知识,无法从表象推出 |
| 29 | 风摄圣僧 | 唐僧被风卷走,求定位 | 妖洞方位 | P | 自求 | 局部搜索,线性 |
| 30 | 心猿遭害 | 主求解器受损,可用资源骤减 | 无 | M | 无 | 资源约束变化,非新问题 |
| 31 | 请圣降妖 | 收伏红孩儿 | 观音、善财童子之位 | NP | 外部·观音 | 与 28 成对,构成完整的查询—验证对 |
| 32 | 黑河沉没 | 黑水河鼍龙,需查明出身 | 西海龙王外甥、摩昂 | NP | 外部·摩昂太子 | 纯身份查询型,全篇最干净的 NP 样本之一 |
| 33 | 搬运车迟 | 五百僧人服苦役,求最小代价解救 | 调度方案 | NH | 自求 | 人力调度与劳动量最小化 |
| 34 | 大赌输赢 | 与虎力、鹿力、羊力多轮斗法 | 逐轮克制策略 | PS | 自求 | 全篇最标准的博弈型:轮流选招,须记住整棵策略树 |
| 35 | 祛道兴僧 | 翻转国家政策约束 | 无 | M | 无 | 改写环境而非求解实例 |
| 36 | 路逢大水 | 通天河阻隔,需在多个渡河方案中权衡 | 渡河策略 | NH | 自求 | 成本—风险权衡,无唯一最优 |
| 37 | 身落天河 | 灵感大王擒唐僧,需查来历 | 观音莲花池金鱼 | NP | 自求 | 反推需遍历,验明即解 |
| 38 | 鱼篮现身 | 收伏灵感大王 | 鱼篮 | NP | 外部·观音 | 与 37 成对 |
| 39 | 金兜山遇怪 | 金刚琢没收全部兵器,所有常规算子失效 | 「此物之主」 | NC* | 自求 | 任何「请天兵」策略都被同一约束吸收,全部归约到「查明主人」 |
| 40 | 普天神难伏 | 暴力枚举整个天庭工具集仍无解 | 换问题表示 | NC* | 外部·天庭众神(失败) | 枚举失效暴露出必须上移一层表示,而非增加算力 |
| 41 | 问佛根源 | 一次查询定位金刚琢归属 | 太上老君 | NP | 外部·如来 | 全篇最清晰的 P^NP 样本:指数搜索被单次神谕调用压成常数 |
| 42 | 吃水遭毒 | 子母河成胎,求逆转 | 落胎泉、如意真仙 | NP | 自求 | 短证书(特定泉水)一验即明 |
| 43 | 西梁国留婚 | 不破戒、不伤人、不失国体地脱身 | 假亲脱网之计 | NH | 自求 | 多目标优化,无唯一最优解,只能求满意解 |
| 44 | 琵琶洞受苦 | 倒马毒桩伤及悟空,需相克者 | 昴日星官 | NP | 外部·昴日星官 | 相生相克名录的精确查询 |
| 45 | 再贬心猿 | 诛草寇后第二次删除主求解器 | 无 | M | 无 | 直接导致下一难的验证器危机 |
| 46 | 难辨猕猴 | 出现两个不可区分的等价证书 | 如来的判别 | coNP | 外部·如来 | 全篇唯一一次证书被完整复制;任何内部验证器都失效,只能诉诸更高层权威 |
阶段 IV 国度、优化与大规模约束(47–72)
| # | 难名 | 计算问题(形式化) | 证书 w | 类 | 证书来源 | 复杂度注记 |
|---|---|---|---|---|---|---|
| 47 | 路阻火焰山 | 八百里火焰,求可行通过方案 | 芭蕉扇 | NH | 自求 | 找代价最小的通过路径,而非判断能否通过 |
| 48 | 求取芭蕉扇 | 三调芭蕉扇,多次策略失败与状态累积 | 变化之术、多次重试 | PS | 自求 | 与牛魔王反复博弈,状态随回合数膨胀 |
| 49 | 收缚魔王 | 收伏牛魔王 | 李靖、哪吒、金刚 | NP | 外部·李靖哪吒 | 博弈终止于一次外部查询 |
| 50 | 赛城扫塔 | 逐层扫塔以定位盗宝线索 | 逐层扫描 | P | 自求 | 线性扫描;P 不等于不费力 |
| 51 | 取宝救僧 | 碧波潭九头虫,需专门克制 | 二郎神、哮天犬 | NP | 外部·二郎神 | 单一专长查询 |
| 52 | 棘林吟咏 | 无兵器的多轮语义应答,陷阱藏在诗里 | 应答链 | PS | 自求 | 树精谈诗、杏仙招亲:唯一一次纯语义博弈 |
| 53 | 小雷音遇难 | 高仿「灵山」输入骗过识别,金铙困住主求解器 | 亢金龙、弥勒 | coNP | 外部·亢金龙/弥勒 | 验证器被高仿输入欺骗,属输入层攻击 |
| 54 | 诸天神遭困 | 增援被批量收入人种袋 | 瓜田之计 | NC* | 外部·弥勒 | 常规增援被整体吸收,须换表示层级 |
| 55 | 稀柿衕秽阻 | 清除 n 个障碍物以开路 | 八戒变巨猪拱路 | P | 自求 | 输入规模极大但只需线性清扫——P 是「随规模多项式」,不是「轻松」 |
| 56 | 朱紫国行医 | 由症状反推隐藏病因(溯因推理) | 乌金丹、悬丝诊脉 | NH | 自求 | 验证药方快,构造药方难,且需排除大量候选 |
| 57 | 拯救疲癃 | 诊治三年沉疴,定位隐藏变量 | 「金圣宫被掳」 | NP | 自求 | 证书是隐藏状态,一揭示即解 |
| 58 | 降妖取后 | 赛太岁紫金铃,盗铃并查主人 | 观音金毛犼 | NP | 外部·观音 | 一次盗取+一次查询,两次 oracle |
| 59 | 七情迷没 | 七个同源目标须同时处理 | 七蜘蛛精同源 | NC* | 自求 | 约束互相牵制,不能逐个贪心求解 |
| 60 | 多目遭伤 | 百眼金光需单一克制物 | 毗蓝婆绣花针 | NP | 外部·毗蓝婆菩萨 | 精确名录查询(昴日星官之母) |
| 61 | 路阻狮驼 | 规模最大的敌对区域,需先做侦察与评估 | 小钻风情报、路径 | NH | 自求 | 先评估后行动,属优化而非判定 |
| 62 | 怪分三色 | 三个魔头需分别匹配三位主人 | 文殊/普贤/如来 | NC* | 外部·文殊普贤 | 三条约束耦合,须一次性整体满足 |
| 63 | 城里遇灾 | 满城皆妖,敌我状态大面积不可分辨 | 状态辨识 | PS | 自求 | 信息不完备下的多回合应对 |
| 64 | 请佛收魔 | 一次性收伏三魔 | 三位主人同时到场 | NP | 外部·文殊普贤如来 | 单次查询摊销到三个约束,神谕的批量效应 |
| 65 | 比丘救子 | 救援一千一百一十一个个体,最小化遗漏 | 城隍土地护持 | NH | 外部·城隍土地 | 大规模个体覆盖,属优化 |
| 66 | 辨认真邪 | 判别国丈真伪,证伪「白鹿」伪装 | 南极寿星 | coNP | 外部·寿星 | 证伪易、证成难;反例(白鹿原形)很短 |
| 67 | 松林救怪 | 输入被精心构造以骗过分类器 | 地涌夫人真身 | coNP | 自求 | 教科书式对抗样本;唐僧的判断器被利用 |
| 68 | 僧房卧病 | 行动力与时间资源受限 | 无 | M | 无 | 资源约束变化,非新问题 |
| 69 | 无底洞遭困 | 陷空山求脱,需锁定妖怪归属 | 李天王、哪吒牌位 | NP | 外部·李靖哪吒 | 牌位就是证书,一验即锁定「义父」关系 |
| 70 | 灭法国难行 | 国王誓杀万僧,求不流血的通关变换 | 夜剃满城头 | P | 自求 | 全篇最干净的一次多项式归约:把「说服国王」变换为「让国王落入自己的规则」 |
| 71 | 隐雾山遇魔 | 伪造证书消耗验证器 | 假人头、分瓣梅花计 | coNP | 自求 | 主动攻击验证器,而非提高问题难度 |
| 72 | 凤仙郡求雨 | 定位不可见的根因(三年前推倒供桌) | 米山、面山、金锁 | NP | 外部·玉帝/四天师 | 证书藏在历史状态里,当前观测不可见 |
阶段 V 工具、身份与收束(73–81)
| # | 难名 | 计算问题(形式化) | 证书 w | 类 | 证书来源 | 复杂度注记 |
|---|---|---|---|---|---|---|
| 73 | 失落兵器 | 三般兵器失窃,需遍历邻近妖洞 | 黄狮精 | NP | 自求 | 失物追查,属局部搜索 |
| 74 | 会庆钉钯 | 妖怪自曝线索,搜索空间坍缩 | 钉钯宴 | P | 自求 | 线索由对手泄露,验证步数骤降 |
| 75 | 竹节山遭难 | 九灵元圣一咬擒众,需查归属 | 太乙救苦天尊 | NP | 外部·太乙天尊 | 常规战力全部失效后的名录查询 |
| 76 | 玄英洞受苦 | 三犀牛假冒佛像受香油,须辨伪 | 四木禽星 | coNP | 自求 | 真伪判别+身份查询的复合 |
| 77 | 赶捉犀牛 | 按相克星宿精确查询 | 角木蛟、斗木獬等 | NP | 外部·四木禽星 | 名录精确到「哪一颗星」,非泛泛增援 |
| 78 | 天竺招婚 | 假公主抛绣球,须识真身 | 太阴星君、玉兔 | NP | 外部·太阴星君 | 又一件短证书,验证只需一次现身 |
| 79 | 铜台府监禁 | 被诬为盗,须证明「未曾作案」 | 寇员外还魂作证 | coNP | 外部·地府增寿 | 全篇 coNP 形状最标准的一难:反例易举,无罪难证 |
| 80 | 凌云渡脱胎 | 无底船、脱去凡胎 | 无 | M | 外部·接引佛祖 | 不可逆相变;问题域本身被替换,不是求解也不是验证 |
| 81 | 通天河遇鼋湿经书 | 经卷沾湿、晒经粘破,完整性校验失败 | 无 | M | 无 | 校验和失败与容错;「天地不全」即承认只存在近似解 |
| 固有类 | 条数 | 占比 | 结构含义 |
|---|---|---|---|
| NP(证书型) | 33 | 40.7% | 主体形态:解短、验证快、构造贵 |
| P(直接可解) | 11 | 13.6% | 扫描、格斗、招募、归约 |
| NH(优化/函数型) | 9 | 11.1% | 求最省代价方案,验证最优性本身难 |
| coNP(证伪/对抗型) | 9 | 11.1% | 伪装识别、证明「无」、验证器攻击 |
| M(元层级) | 9 | 11.1% | 初始化、增删求解器、相变、校验 |
| NC*(约束耦合型) | 5 | 6.2% | 常规策略全部失效,须换问题表示 |
| PS(博弈型) | 5 | 6.2% | 多回合量词交替 |
| 合计 | 81 | 100% | — |
另一个更关键的统计不在「类」这一列,而在「证书来源」:
| 证书来源 | 条数 | 占比 | 计算含义 |
|---|---|---|---|
| 外部·X(名录查询) | 37 | 45.7% | 一次或多次神谕调用,取回身份/克制物短证书 |
| 预置·X(事先交付) | 2 | 2.5% | 证书由设计者注入,团队只执行验证(第 8、15 难) |
| 自求 | 34 | 42.0% | 内部构造、线性扫描、归约、博弈 |
| 无 | 8 | 9.9% | 非求解型,属元层级 |
| 合计 | 81 | 100% | — |
合计 39 条(48.1%)的解不是被「解」出来的,是被「查」出来的。这个数字直接决定了下文的归类结论。
值得单独一提的是「成对结构」:13/14、28/31、37/38、39/40/41 等组,前半是本地搜索失败,后半是一次外部查询收束。原著把「搜索」与「神谕」拆成两难分别记账,等于在难簿里保留了算法调用日志。
这是本题真正要回答的部分。「八十一难属于 P 还是 NP」问得不够精确,因为答案随观察者而变。我把四个层次分开:
| 层次 | 候选归类 | 支持理由 | 反对理由 | 判断 |
|---|---|---|---|---|
| 单个难的结构 | NP(证书型) | 33/81 是短证书+快验证;妖怪「是谁的坐骑/童子」正是 witness | 忽略神谕、对抗样本与元层级 | 适用于条数最多的一类,不足以概括全体 |
| 取经全程(执行层,唐僧视角) | P | 难簿已把每条难的 witness 写好,团队只需逐条验证并走完轨迹 | 解释不了「难」从何而来 | 准确但反直觉:他们跑的是 verifier,不是 solver |
| 取经全程(算法层,孙悟空视角) | P^NP(Δ₂^P) | 多项式时间的本地操作,加上对 NP 名录的自适应查询;「打不过就请人」即 oracle call | 神谕本身非构造性,不能视为算法内部能力 | 推荐:最精确、解释力最强 |
| 难簿设计(观音/如来视角) | NP-Hard / PSPACE | 生成恰好 81 个可解、不可绕过、且总数合于九九之数的实例,是约束生成与可满足性设计 | 属设计问题(合成),不是判定问题 | 更高一层,与执行层不可混谈 |
| 第八十一难 | 近似/容错(非判定类) | 残缺经文被判为「应不全之奥妙」,主动放弃精确解 | — | 全篇的收束,也是对前四层的自我限制 |
我倾向于把 P^NP 作为整部《西游记》的主标签,理由不是它最响亮,而是它同时解释了三件否则互相矛盾的事:为什么妖怪总是打不过(本地搜索不够)、为什么总能过(有神谕)、以及为什么观音非要凑满八十一难(证书链的长度本身是规范的一部分,不是副产品)。
若只许用一个传统类名回答「八十一难属于哪一类」,我的答案是:它不是 NP-Complete,而是一条预置证书链上的多项式验证任务,由一台带 NP 神谕的机器执行。NP-Complete 强调的是「最难的那一个」;八十一难的构造恰恰相反——设计者刻意保证每一难都有解、且解在三界名录里可查。它的难点从来不在可满足性,而在验证轨迹必须走满。
这也解释了一个原著里的著名反常:孙悟空一个筋斗十万八千里,正好等于长安到灵山的距离,他却不能驮唐僧飞过去。若取经的目标是「到达灵山」,那是一个 P 问题,一个筋斗就解完了;但取经要的是走满八十一条证书,解本身不是交付物,验证记录才是。所有关于「为什么不直接飞过去」的疑问,本质上是把 verifier 误读成了 solver。
难簿不是事故记录,是 certificate。 第九十九回里,五方揭谛交上去的是一册逐条登记的簿子,观音「从头看了一遍」,数出八十,还不够。这个动作在计算上极其特殊:它在检查证书链的长度,而不是检查有没有打赢。观音补一难,等于给一个 SAT 实例补上最后一个 clause,使其满足「恰好 81」的计数约束。难不是路上碰到的,是被要求集齐的。
第四十六难是验证器危机,不是难度升级。 六耳猕猴与悟空形貌、本领、记忆全同,连紧箍咒与照妖镜都无法区分。这是全书唯一一次 witness 被完整复制的情形:不是找不到证书,而是两个候选证书对任何内部验证器都返回 1。最终只能由如来——更高层级的权威——给出判别。它对应的不是「更难的 NP 问题」,而是验证器自身的可靠性边界:一旦证书可复制,P 与 NP 的那套验证框架就先失效了。
第八十一难是一次校验和失败,而且拒绝修复。 经卷落水、晒时粘破数卷,唐僧懊悔,悟空答「盖天地不全,此经原是全全的,今沾破了,乃是应不全之奥妙也」。前八十难都在求一个完整解,最后一难交付的却是允许残缺的近似解,并把它写进教义。整套框架在此自我收束:不完备不是求解失败,是问题定义的一部分。把它硬归进任何判定类都会丢掉这层意思,所以我把它留在元层级。
- 渐近性:如第一节所述,81 个固定实例在渐近意义下皆为 O(1)。本文所有类标签均为结构类比,把「难」当作参数化问题族的模式,而非对有限集合作复杂性断言。
- NC*:星号表示叙事类比,不表示已构造多项式归约;任意 NP 问题可归约到它这一点,本文没有证明,也不主张。
- 神谕的技术含义:
外部·X对应一次「向三界名录查询并取回短证书」的调用。若把查询成本计为常数,整条取经路径落在 P^NP;若要求把神谕展开为内部搜索,则退回 NP/PSPACE 层级。结论对这一建模选择敏感,故已在表中保留原始来源列,便于改用其他口径重算。 - 版本异文:通行本系统(维基文库、人民文学出版社系统、百度百科所录)作「折从/落坑第六难」「收降八戒十二难」「金兜山遇怪三十九难」「稀柿衕秽阻五十五难」「凌云渡脱胎八十难」,且「夜被火烧第十难、失却袈裟十一难」。另有系统(如部分网络整理本)作「失却袈裟第十难、夜被火烧十一难」「不识人参十八难、五庄观中十九难」「山压大圣二十五难」「凤仙国求雨六十六难」等,条序偏移较大。本文采用前者八十条,第八十一难「通天河遇鼋湿经书」为观音命揭谛追补、不在难簿正文之内——这一点正是第六节第一段的依据。
- 难簿顺序 ≠ 正文回目顺序:难簿为五方揭谛按历难先后登记,与百回本正文的回目推进并非严格一一对应(部分相邻难合于同一段情节,如 13/14、37/38)。故本表不标回目,以免制造虚假的精确。
归类框架与判据为原创建构;难名与顺序据《西游记》第九十九回灾难簿。
