1多对一归约的方向
闭卷重建多对一归约的方向的对象、状态、事件、不变量与一个失败反例。
理论计算：自动机、可计算性与复杂性 · 小纸条
选一章打印。双面打印（按长边翻页）后沿虚线剪开，每张卡片正面题目、背面答案。
第 1 页 · 正面（题目）
2用接受问题证明新问题不可判定
闭卷重建用接受问题证明新问题不可判定的对象、状态、事件、不变量与一个失败反例。
3映射归约与图示证明
闭卷重建映射归约与图示证明的对象、状态、事件、不变量与一个失败反例。
4图灵归约与查询能力
闭卷重建图灵归约与查询能力的对象、状态、事件、不变量与一个失败反例。
5归约中的模板与陷阱
闭卷重建归约中的模板与陷阱的对象、状态、事件、不变量与一个失败反例。
6实验：有限映射归约验证器
闭卷重建实验：有限映射归约验证器的对象、状态、事件、不变量与一个失败反例。
7归约工作坊：从构造到双向证明
闭卷重建归约工作坊：从构造到双向证明的对象、状态、事件、不变量与一个失败反例。
第 1 页 · 背面（答案）
核心机制：从A_TM实例构造目标机器或语言，使接受事实精确对应目标性质；实验入口：先决定目标性质的一个正实例和负实例，再把M在w上的行为嵌入开关；边界：构造不能调用未知答案；包装机器只可模拟M而不能预知是否接受。
核心机制：A≤mB要求可计算函数f使x∈A当且仅当f(x)∈B；B可判定则A可判定，A不可判定则B不可判定；实验入口：为每个归约写输入、输出、可计算性和双向等价四栏；边界：方向写反会得到无效结论；只证明一个蕴含不足以建立多对一归约。
核心机制：图灵归约允许算法自适应询问预言机，通常比一次映射更强；结论需匹配所用归约类型；实验入口：比较一次SAT编码与多次成员查询的算法结构；边界：用图灵归约证明NP完全性通常不够，因为定义要求多项式时间多对一归约。
核心机制：归约器本身必须总停，生成合法目标实例，映射图中正例进正例、反例进反例；实验入口：画四象限归约图并逐项排除错误流向；边界：只说显然转换不够，编码长度和异常输入也需说明。
核心机制：在有限真值表模型检查候选映射是否对每个输入保持成员关系，并输出首个反例；实验入口：覆盖正确映射、正例失败、反例失败和非法目标索引；边界：有限验证器只验给定表，不能证明无限问题上的可计算归约存在。
核心机制：可靠模板是来源问题已知难、构造可计算、保持是非、规模受控；常见陷阱是方向反、偷用答案和只证半边；实验入口：审查三个错误证明，分别标出首个逻辑断点并给修补方案；边界：目标问题看起来更难不是证明；实例长得相似也不保证语义等价。
核心机制：完成一个A_TM到语言非空性的归约和一个3SAT到图问题的归约骨架，逐句标量词；实验入口：同伴只看接口和双向证明复现构造，并尝试空输入与极端实例；边界：若双向证明某一步引用目标问题求解器，说明构造循环依赖。