1随机算法的保证语言
闭卷重建随机算法的保证语言的对象、状态、事件、不变量与一个失败反例。
理论计算：自动机、可计算性与复杂性 · 小纸条
选一章打印。双面打印（按长边翻页）后沿虚线剪开，每张卡片正面题目、背面答案。
第 1 页 · 正面（题目）
2RP、coRP与BPP边界
闭卷重建RP、coRP与BPP边界的对象、状态、事件、不变量与一个失败反例。
3近似比与优化问题
闭卷重建近似比与优化问题的对象、状态、事件、不变量与一个失败反例。
4不可近似性与归约边界
闭卷重建不可近似性与归约边界的对象、状态、事件、不变量与一个失败反例。
5描述复杂性选讲
闭卷重建描述复杂性选讲的对象、状态、事件、不变量与一个失败反例。
6实验：顶点覆盖二近似
闭卷重建实验：顶点覆盖二近似的对象、状态、事件、不变量与一个失败反例。
7终章证明项目与口试
闭卷重建终章证明项目与口试的对象、状态、事件、不变量与一个失败反例。
第 1 页 · 背面（答案）
核心机制：RP有单边错误，coRP反向单边，BPP允许双边有界错误；重复可降低错误但增加时间；实验入口：用真值表画三类算法在是/否实例上的接受概率约束；边界：概率阈值是模型定义的一部分，不能把启发式平均表现直接归入BPP。
核心机制：随机算法需区分Las Vegas期望时间与Monte Carlo错误概率，并声明概率对随机币还是输入分布；实验入口：对重复独立试验计算错误概率放大，实际模拟估计与理论上界比较；边界：一次成功运行不能证明零错误；伪随机种子固定会改变实验解释。
核心机制：gap归约把来源问题的两种情形映成目标最优值间隔，从而排除某近似因子，结论依赖复杂度假设；实验入口：用抽象YES/NO阈值图说明gap保持，而不冒充完整PCP证明；边界：普通决策归约不能自动给近似下界；未证明的复杂度假设需明示。
核心机制：最小化算法解值不超过α倍最优值，最大化常用算法值至少最优值的1/α；必须限定可行解；实验入口：证明顶点覆盖二近似：极大匹配端点可行且匹配大小下界OPT；边界：实验结果接近最优不等于最坏情形近似保证；判定NP完全与优化近似需区分。
核心机制：按稳定次序构造极大匹配并取全部端点，输出覆盖大小与证书；实验入口：四图覆盖空图、路径、星形和不利例，另用小图穷举最优值核对比值；边界：极大匹配不是最大匹配，但端点构造仍有二近似证明；实现次序影响解不影响保证。
核心机制：描述复杂性用逻辑刻画复杂度类，例如有限有序结构上的存在二阶逻辑与NP联系，强调机器无关的表达能力视角；实验入口：把3-着色写成存在三个顶点集合并用一阶条件检查覆盖、互斥与邻接异色；边界：这是高阶选讲；公式语义依赖有限结构与编码，不能把逻辑可定义性等同易求解。
核心机制：项目从一个语言或优化问题出发，提交模型、引理链、构造/归约、代码证据、反例、复杂度和限制，并接受逐步口试；实验入口：选择自动机最小化、CFL非闭包、不可判定归约或NP完全归约之一，完成可复核档案；边界：代码搜索只是证据之一；最终主张必须由量词完整、方向正确的形式证明支撑。