假设给定一个组合优化问题 A。让我们假设 WLOG 问题是团问题。
我如何证明如果 clique 是 NP 完全的，那么 clique 的决策版本是 NP 完全的，其中决策版本当然是以下问题 B：是否存在大小等于 k 的 clique？
我想我有直觉，但不确定它是否足以证明：
第一步：
如果给定一组大小为 k 的顶点 C，我可以在多项式时间内验证是否存在大小为 k 的团（假设 B 的答案是肯定的，即存在大小为 k 的团）。因此，B 在 NP 中。
第二步：将A简化为B。
- 由于 A 要求最大大小的集团，我们可以将问题分解为多个部分，B1：是否存在大小为 1 的集团？，...，BN：是否存在大小为 N 的集团？
- 如果 A 是可解的，假设有一个大小为 k* 的团，那么每个 Bk, k=1,...,N 都可以通过比较 k 和 k* 轻松回答
- 如果所有Bks都是可解的，我们可以知道最大 clique 大小是多少。
我真的不确定这是一个减少，尽管它是在多项式时间内。也许是因为一个问题被分解成许多问题。此外，我不确定我应该使用上面的“全部”这个词。
谢谢您的帮助！:)