了解多时间Reduction/NP-complete
Understanding Poly-time Reduction/NP-complete
你好，当问题 X 可以归结为 Y 时，我无法理解 X 和 Y 的关系。
图中的问题，我特别不明白为什么a和b不对，如果X不比Y难，那么Y至少和X一样难（？），那么如果X是 NP 完全的，难道 Y 不也是至少 NP 完全的吗？
谢谢
（问题来源：https://introcs.cs.princeton.edu/java/55intractability/）
这里举一反三或许有所帮助。与其考虑问题和可还原性，不如谈谈人以及他们的速度 运行.
让我们将 SO 定义为所有使用 Stack Overflow 的人，然后将某人定义为 SO-fast（如果他们可以的话） 运行 至少和使用 Stack Overflow 的人一样快。然后我们可以说某人 SO-complete 如果他们使用 Stack Overflow（他们在 SO）并且也可以 运行至少和 Stack Overflow 上的任何人一样快（他们 SO-快）。
现在，假设 X 可以 运行 不比 Y 快，并且 Y 是 SO-完全。这是否意味着 X 绝对 SO-快？可能不会。我们所知道的是，X 无法超越 运行 可以像 Stack Overflow 上的每个人一样快 运行 的人。也许这意味着 X 可以 运行 和 Y 一样快，因此也是 SO-快，但更有可能的是 X 没有那么快。那么，以此类推，你明白选项(a)为什么不正确了吗？
接下来，假设 X 可以 运行 不比 Y 快，并且 X 是 SO-complete。这是否意味着 Y 是 SO-完整的？答案是不。我假设 Usain Bolt 不是 Stack Overflow 用户，但我可以向你保证 Usain Bolt 可以超过 运行 Stack Overflow 上的任何人。这意味着 Usain Bolt 是 SO-fast，但不是 SO-complete。请记住，SO-完整性有两个组成部分：您必须速度快，但您还必须是 Stack Overflow 用户。知道你可以超越 运行 最快的 Stack Overflow 用户并不能说明你自己是否在 Stack Overflow 上。这是否解释了选项 (b) 不正确的原因？
希望对您有所帮助！
你好，当问题 X 可以归结为 Y 时，我无法理解 X 和 Y 的关系。
图中的问题，我特别不明白为什么a和b不对，如果X不比Y难，那么Y至少和X一样难（？），那么如果X是 NP 完全的，难道 Y 不也是至少 NP 完全的吗？
谢谢
（问题来源：https://introcs.cs.princeton.edu/java/55intractability/）
这里举一反三或许有所帮助。与其考虑问题和可还原性，不如谈谈人以及他们的速度 运行.
让我们将 SO 定义为所有使用 Stack Overflow 的人，然后将某人定义为 SO-fast（如果他们可以的话） 运行 至少和使用 Stack Overflow 的人一样快。然后我们可以说某人 SO-complete 如果他们使用 Stack Overflow（他们在 SO）并且也可以 运行至少和 Stack Overflow 上的任何人一样快（他们 SO-快）。
现在，假设 X 可以 运行 不比 Y 快，并且 Y 是 SO-完全。这是否意味着 X 绝对 SO-快？可能不会。我们所知道的是，X 无法超越 运行 可以像 Stack Overflow 上的每个人一样快 运行 的人。也许这意味着 X 可以 运行 和 Y 一样快，因此也是 SO-快，但更有可能的是 X 没有那么快。那么，以此类推，你明白选项(a)为什么不正确了吗？
接下来，假设 X 可以 运行 不比 Y 快，并且 X 是 SO-complete。这是否意味着 Y 是 SO-完整的？答案是不。我假设 Usain Bolt 不是 Stack Overflow 用户，但我可以向你保证 Usain Bolt 可以超过 运行 Stack Overflow 上的任何人。这意味着 Usain Bolt 是 SO-fast，但不是 SO-complete。请记住，SO-完整性有两个组成部分：您必须速度快，但您还必须是 Stack Overflow 用户。知道你可以超越 运行 最快的 Stack Overflow 用户并不能说明你自己是否在 Stack Overflow 上。这是否解释了选项 (b) 不正确的原因？
希望对您有所帮助！