若取经的目标是「到达灵山」,那是一个 P 问题,一个筋斗就解完了;但取经要的是走满八十一条证书,解本身不是交付物,验证记录才是。


《西游记》第九十九回「九九数完魔灭尽 三三行满道归根」,五方揭谛呈上「灾难簿」,观音从头看过,见只有八十难,急传声道:「佛门中九九归真。圣僧受过八十难,还少一难,不得完成此数。」即命揭谛赶上金刚,再生一难。


01PART
一、先把话说准:这是结构类比,不是复杂性证明


任何一本计算复杂性教材都会先指出一件事:复杂性类是对无限问题族在输入规模 n→∞ 时的渐近刻画。八十一难是 81 个固定实例,严格地说,任何有限集合的时间上界都是 O(1),既不是 NP-Complete,也不是 P。若直接给每一难贴 P 或 NP 的标签而不作说明,这个框架从第一句起就不成立。

所以本文做的是另一件事:把「一难」看作参数化问题族的一个模式——n 是三界名录的规模、候选身份的个数、路径的长度、约束的条数;比较的也不是绝对耗时,而是三层成本之间的关系:

  1. 构造解(从表象找出脱难方案)要付多少搜索;
  2. 验证解(给定方案,施行并确认此难已解)要付多少代价;
  3. 获取外部信息(是否需要查询一个自己不持有的名录)是否构成独立的一步。

复杂性理论里最有生命力的那组区分,恰恰就是这三层:找到解与认出解,以及允许调用神谕时二者会发生什么。八十一难把这三层关系演了八十一遍,这才是它值得用 P / NP 来读的理由。

下文所有 NC* 标记都是隐喻性的,表示「在叙事结构上充当同类问题的通用 hardest case」,不构成 Cook–Levin 式的多项式归约证明。本文也不声称对 P ?= NP 有任何主张——那是尚未解决的数学问题,《西游记》既没有证明它,也没有暗示它。


02PART
二、映射公理与符号表


设一难为实例 x = (地点, 队伍状态, 妖魔表象, 可用资源, 时限)。 设脱难方案为证书 w(关键身份、克制物、法宝、救援者、路径选择)。 设验证器 V(x, w) 为「按 w 施行,此难是否解除」。

在原著里,V 几乎总是廉价的:喊一声名号、亮一件法宝、请一位主人,妖魔立刻现形。真正昂贵的是从 x 反推 w。因此绝大多数难的固有形状是 NP,而不是「打不过」——打不过是算力描述,不是问题结构描述。

记号计算含义西游判据代表难
P存在 poly(n) 的确定性求解算法不需外部信息,按确定动作序列即可脱身;含「规模大但线性」的情形稀柿衕秽阻、赛城扫塔、收降八戒
NP解长度 poly(n),验证 poly(n),构造靠搜索解是「它是谁/哪件法宝/谁是主人」这类短证书;猜中一验即明,反推需遍历名录黄风怪阻、无底洞遭困、天竺招婚
NC*隐喻性 NP-Complete多条约束互相牵制、须同时满足,且常规策略全部归约到同一个换表示动作金兜山遇怪、普天神难伏、诸天神遭困
NHNP-Hard(优化/函数型)目标不是「能否通过」,而是「代价最小的通过方案」;验证「已最优」本身困难难活人参、西梁国留婚、朱紫国行医
PSPSPACE(量词交替/博弈)与对手多回合交替出招,需维护整棵状态与策略树,不能只记当前步大赌输赢、莲花洞高悬、求取芭蕉扇
coNP补问题在 NP,证伪易、证成难难在证明「无」或识破高仿输入;反例短,正面证明长铜台府监禁、难辨猕猴、松林救怪
M元层级,非求解问题初始设定、验证器自检、求解器增删、状态相变、完整性校验金蝉遭贬、贬退心猿、凌云渡脱胎、湿经书

另设一维与复杂度类正交:证书来源——自求(团队内部构造)/外部·X(向三界名录查询所得)/预置·X(观音、如来事先交付)/无(该行不是求解型问题)。这一维是后文整体归类的关键证据。


03PART
三、逐难归类总表

阶段 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无校验和失败与容错;「天地不全」即承认只存在近似解

04PART
四、分布统计




固有类条数占比结构含义
NP(证书型)3340.7%主体形态:解短、验证快、构造贵
P(直接可解)1113.6%扫描、格斗、招募、归约
NH(优化/函数型)911.1%求最省代价方案,验证最优性本身难
coNP(证伪/对抗型)911.1%伪装识别、证明「无」、验证器攻击
M(元层级)911.1%初始化、增删求解器、相变、校验
NC*(约束耦合型)56.2%常规策略全部失效,须换问题表示
PS(博弈型)56.2%多回合量词交替
合计81100%—

另一个更关键的统计不在「类」这一列,而在「证书来源」:

证书来源条数占比计算含义
外部·X(名录查询)3745.7%一次或多次神谕调用,取回身份/克制物短证书
预置·X(事先交付)22.5%证书由设计者注入,团队只执行验证(第 8、15 难)
自求3442.0%内部构造、线性扫描、归约、博弈
无89.9%非求解型,属元层级
合计81100%—

合计 39 条(48.1%)的解不是被「解」出来的,是被「查」出来的。这个数字直接决定了下文的归类结论。

值得单独一提的是「成对结构」:13/14、28/31、37/38、39/40/41 等组,前半是本地搜索失败,后半是一次外部查询收束。原著把「搜索」与「神谕」拆成两难分别记账,等于在难簿里保留了算法调用日志。


05PART
五、整体该归到哪一类

这是本题真正要回答的部分。「八十一难属于 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。


06PART
六、难簿、复制的证书,与不肯修复的校验和


难簿不是事故记录,是 certificate。 第九十九回里,五方揭谛交上去的是一册逐条登记的簿子,观音「从头看了一遍」,数出八十,还不够。这个动作在计算上极其特殊:它在检查证书链的长度,而不是检查有没有打赢。观音补一难,等于给一个 SAT 实例补上最后一个 clause,使其满足「恰好 81」的计数约束。难不是路上碰到的,是被要求集齐的。

第四十六难是验证器危机,不是难度升级。 六耳猕猴与悟空形貌、本领、记忆全同,连紧箍咒与照妖镜都无法区分。这是全书唯一一次 witness 被完整复制的情形:不是找不到证书,而是两个候选证书对任何内部验证器都返回 1。最终只能由如来——更高层级的权威——给出判别。它对应的不是「更难的 NP 问题」,而是验证器自身的可靠性边界:一旦证书可复制,P 与 NP 的那套验证框架就先失效了。

第八十一难是一次校验和失败,而且拒绝修复。 经卷落水、晒时粘破数卷,唐僧懊悔,悟空答「盖天地不全,此经原是全全的,今沾破了,乃是应不全之奥妙也」。前八十难都在求一个完整解,最后一难交付的却是允许残缺的近似解,并把它写进教义。整套框架在此自我收束:不完备不是求解失败,是问题定义的一部分。把它硬归进任何判定类都会丢掉这层意思,所以我把它留在元层级。


07PART
七、边界与版本说明

  1. 渐近性:如第一节所述,81 个固定实例在渐近意义下皆为 O(1)。本文所有类标签均为结构类比,把「难」当作参数化问题族的模式,而非对有限集合作复杂性断言。
  2. NC*:星号表示叙事类比,不表示已构造多项式归约;任意 NP 问题可归约到它这一点,本文没有证明,也不主张。
  3. 神谕的技术含义:外部·X 对应一次「向三界名录查询并取回短证书」的调用。若把查询成本计为常数,整条取经路径落在 P^NP;若要求把神谕展开为内部搜索,则退回 NP/PSPACE 层级。结论对这一建模选择敏感,故已在表中保留原始来源列,便于改用其他口径重算。
  4. 版本异文:通行本系统(维基文库、人民文学出版社系统、百度百科所录)作「折从/落坑第六难」「收降八戒十二难」「金兜山遇怪三十九难」「稀柿衕秽阻五十五难」「凌云渡脱胎八十难」,且「夜被火烧第十难、失却袈裟十一难」。另有系统(如部分网络整理本)作「失却袈裟第十难、夜被火烧十一难」「不识人参十八难、五庄观中十九难」「山压大圣二十五难」「凤仙国求雨六十六难」等,条序偏移较大。本文采用前者八十条,第八十一难「通天河遇鼋湿经书」为观音命揭谛追补、不在难簿正文之内——这一点正是第六节第一段的依据。
  5. 难簿顺序 ≠ 正文回目顺序:难簿为五方揭谛按历难先后登记,与百回本正文的回目推进并非严格一一对应(部分相邻难合于同一段情节,如 13/14、37/38)。故本表不标回目,以免制造虚假的精确。

归类框架与判据为原创建构;难名与顺序据《西游记》第九十九回灾难簿。