1NP的验证器定义
闭卷重建NP的验证器定义的对象、状态、事件、不变量与一个失败反例。
理论计算：自动机、可计算性与复杂性 · 小纸条
选一章打印。双面打印（按长边翻页）后沿虚线剪开，每张卡片正面题目、背面答案。
第 1 页 · 正面（题目）
2非确定机与验证器等价
闭卷重建非确定机与验证器等价的对象、状态、事件、不变量与一个失败反例。
3Cook–Levin思想
闭卷重建Cook–Levin思想的对象、状态、事件、不变量与一个失败反例。
4证明NP完全的两步
闭卷重建证明NP完全的两步的对象、状态、事件、不变量与一个失败反例。
5SAT、3SAT与图问题链
闭卷重建SAT、3SAT与图问题链的对象、状态、事件、不变量与一个失败反例。
6实验：SAT证书验证器
闭卷重建实验：SAT证书验证器的对象、状态、事件、不变量与一个失败反例。
7实验：顶点覆盖证书验证
闭卷重建实验：顶点覆盖证书验证的对象、状态、事件、不变量与一个失败反例。
第 1 页 · 背面（答案）
核心机制：非确定多项式时间分支可编码为证书，验证器的证书猜测可由非确定分支模拟；实验入口：双向构造并标出时间与证书长度的多项式界；边界：存在接受分支即可接受，不是多数分支；分支数指数并不违背每分支多项式时间。
核心机制：语言在NP中当且仅当是实例与多项式长证书关系的多项式时间投影，证书长度和验证时间都须多项式；实验入口：为Hamilton路径写证书格式、长度、逐边验证和拒绝条件；边界：NP不是非多项式，也不要求找到证书的算法已知高效。
核心机制：先证明目标在NP，再从已知NP完全问题做多项式时间多对一归约，并证明双向和规模；实验入口：用3SAT到顶点覆盖骨架标每个变量、子句组件和k；边界：只证明NP难不等于NP完全；从目标归约到SAT方向错误。
核心机制：把多项式时间计算表格的局部一致性编码为布尔约束，使可接受计算与可满足赋值对应；实验入口：画时间×纸带位置表，列唯一符号、初始行、转移窗口与接受条件；边界：课程可选讲证明骨架，但不能只说任何程序都能转SAT而省略局部约束。
核心机制：读取CNF和变量赋值，逐子句检查至少一个文字为真并输出首个失败子句；实验入口：覆盖满足、首句失败、负文字和空子句；边界：验证给定赋值是多项式工作，不等于多项式时间找到赋值。
核心机制：标准归约链把SAT/3SAT连接到独立集、团、顶点覆盖、Hamilton问题等，组件负责排除不一致选择；实验入口：为一个两子句公式画图组件并从满足赋值恢复图解，再反向恢复；边界：组件图好看不是证明，必须覆盖跨组件边与阈值恰好性。
核心机制：读取无向图、k和候选顶点集，检查大小限制与每条边覆盖；实验入口：覆盖合法证书、漏边、超k和重复顶点；边界：验证器必须拒绝重复计数与非法顶点；成功只说明该实例有相应证书。