1 第 11 章教材习题：题意释义与通用解题方法
本节不是逐题完整解答。 它为每个教材编号习题提供经页面核验的题意释义（Problem）、主题标签（Topic），以及本章层面的通用解题方法导引。本公开仓库不分发教材原图、转移表、边权与长表达式，因此具体数值、状态名与表达式需结合教材对应原页数据自行推导。同一类题的“方法导引”会重复出现，它说明的是解题思路，而不是该题的具体答案。
本章共收录 8 个教材编号习题。
1.1 习题 11.1.1
Source: textbook PDF p.344
Problem（教材题意释义）
对 TRUE-SAT、FALSE-SAT、DOUBLE-SAT、NEAR-TAUT 等问题判断是否属于 NP/coNP，写出补问题并判断 NP 完全性。
Topic
NP；SAT
方法导引（通用，非本题具体答案）
证明 NP 完全性分两步：先给多项式长度证书及多项式验证器，说明目标问题属于 NP；再从已知 NP 完全问题做多项式时间归约。 SAT/3SAT 归约要为每个变量和约束设计 gadget，并逐项证明“原实例可满足 ⇔ 新实例存在所需结构”。 2SAT 可建蕴含图：每个子句 (a∨b) 加 ¬a→b 与 ¬b→a；公式可满足当且仅当不存在变量 x 与 ¬x 位于同一强连通分量。
Common mistakes
- 跳过量词、边界条件或接受方式；
- 把“存在一种构造”误写成“任意构造都成立”；
- 图表题未先准确抄录源数据就直接计算。
1.2 习题 11.1.2
Source: textbook PDF p.344
Problem（教材题意释义）
假设存在多项式可计算双射 f，其逆不能多项式计算；证明由 f^{-1}(x)<y 定义的语言位于 (NP∩coNP)-P。
Topic
NP
方法导引（通用，非本题具体答案）
证明 NP 完全性分两步：先给多项式长度证书及多项式验证器，说明目标问题属于 NP；再从已知 NP 完全问题做多项式时间归约。 SAT/3SAT 归约要为每个变量和约束设计 gadget，并逐项证明“原实例可满足 ⇔ 新实例存在所需结构”。 2SAT 可建蕴含图：每个子句 (a∨b) 加 ¬a→b 与 ¬b→a；公式可满足当且仅当不存在变量 x 与 ¬x 位于同一强连通分量。
Common mistakes
- 跳过量词、边界条件或接受方式；
- 把“存在一种构造”误写成“任意构造都成立”；
- 图表题未先准确抄录源数据就直接计算。
1.3 习题 11.3.1
Source: textbook PDF p.354
Problem（教材题意释义）
补全 QBF/PSPACE 完全性证明中四种公式构造情形：组合、全称量词、否定、括号。
Topic
PSPACE；QBF
方法导引（通用，非本题具体答案）
成员性通常通过深度优先搜索证明：只保存当前配置/递归栈而不保存整棵指数大小搜索树，因此空间是多项式。 PSPACE-hardness 从 QBF 归约；存在量词对应当前玩家/存在分支选择，全称量词对应必须验证两个分支，子公式递归求值。 对博弈问题，把量词交替编码成双方轮流选择；对正则表达式全称性，把指数大小 DFA 的状态集合按需生成并在多项式空间中搜索反例。
Common mistakes
- 跳过量词、边界条件或接受方式；
- 把“存在一种构造”误写成“任意构造都成立”；
- 图表题未先准确抄录源数据就直接计算。
1.4 习题 11.3.2
Source: textbook PDF p.355
Problem（教材题意释义）
证明“给定正则表达式 E，是否 L(E)=Σ*”为 PSPACE 完全问题。
Topic
正则表达式；PSPACE
方法导引（通用，非本题具体答案）
成员性通常通过深度优先搜索证明：只保存当前配置/递归栈而不保存整棵指数大小搜索树，因此空间是多项式。 PSPACE-hardness 从 QBF 归约；存在量词对应当前玩家/存在分支选择，全称量词对应必须验证两个分支，子公式递归求值。 对博弈问题，把量词交替编码成双方轮流选择；对正则表达式全称性，把指数大小 DFA 的状态集合按需生成并在多项式空间中搜索反例。
Common mistakes
- 跳过量词、边界条件或接受方式；
- 把“存在一种构造”误写成“任意构造都成立”；
- 图表题未先准确抄录源数据就直接计算。
1.5 习题 11.3.3
Source: textbook PDF p.355
Problem（教材题意释义）
分析 SHORT/CUT 两人选点路径游戏，证明“SHORT 是否必胜”PSPACE 完全。
Topic
PSPACE
方法导引（通用，非本题具体答案）
成员性通常通过深度优先搜索证明：只保存当前配置/递归栈而不保存整棵指数大小搜索树，因此空间是多项式。 PSPACE-hardness 从 QBF 归约；存在量词对应当前玩家/存在分支选择，全称量词对应必须验证两个分支，子公式递归求值。 对博弈问题，把量词交替编码成双方轮流选择；对正则表达式全称性，把指数大小 DFA 的状态集合按需生成并在多项式空间中搜索反例。
Common mistakes
- 跳过量词、边界条件或接受方式；
- 把“存在一种构造”误写成“任意构造都成立”；
- 图表题未先准确抄录源数据就直接计算。
1.6 习题 11.5.1
Source: textbook PDF p.369
Problem（教材题意释义）
模 13 计算 11+9、9-11、5×8、5/8、5^8。
Topic
模 13
方法导引（通用，非本题具体答案）
所有算术都在模 13（或题定素数 p）下进行，每一步立即取模。除法 a/b 解释为 a·b^{-1}，逆元可用扩展欧几里得或费马小定理求。 大幂用二进制快速幂：把指数写成二进制，连续平方并仅乘入对应为 1 的幂次。二次剩余通过枚举 1,…,(p-1)/2 的平方即可；x 与 p-x 平方相同且除此之外无重复，因此非零二次剩余恰有 (p-1)/2 个。
Common mistakes
- 跳过量词、边界条件或接受方式；
- 把“存在一种构造”误写成“任意构造都成立”；
- 图表题未先准确抄录源数据就直接计算。
1.7 习题 11.5.2
Source: textbook PDF p.369
Problem（教材题意释义）
验证教材在素性测试中使用的同余等式：先二进制展开 560，再用重复平方计算 x^560 mod 561，挑若干 x 检验。
Topic
按教材定义构造 + 正确性证明
方法导引（通用，非本题具体答案）
所有算术都在模 13（或题定素数 p）下进行，每一步立即取模。除法 a/b 解释为 a·b^{-1}，逆元可用扩展欧几里得或费马小定理求。 大幂用二进制快速幂：把指数写成二进制，连续平方并仅乘入对应为 1 的幂次。二次剩余通过枚举 1,…,(p-1)/2 的平方即可；x 与 p-x 平方相同且除此之外无重复，因此非零二次剩余恰有 (p-1)/2 个。
Common mistakes
- 跳过量词、边界条件或接受方式；
- 把“存在一种构造”误写成“任意构造都成立”；
- 图表题未先准确抄录源数据就直接计算。
1.8 习题 11.5.3
Source: textbook PDF p.369
Problem（教材题意释义）
列出模 7、模 13 的二次剩余，并证明素数 p 时非零二次剩余恰有 (p-1)/2 个。
Topic
模 13；二次剩余
方法导引（通用，非本题具体答案）
所有算术都在模 13（或题定素数 p）下进行，每一步立即取模。除法 a/b 解释为 a·b^{-1}，逆元可用扩展欧几里得或费马小定理求。 大幂用二进制快速幂：把指数写成二进制，连续平方并仅乘入对应为 1 的幂次。二次剩余通过枚举 1,…,(p-1)/2 的平方即可；x 与 p-x 平方相同且除此之外无重复，因此非零二次剩余恰有 (p-1)/2 个。
Common mistakes
- 跳过量词、边界条件或接受方式；
- 把“存在一种构造”误写成“任意构造都成立”；
- 图表题未先准确抄录源数据就直接计算。