algorithm - 使用下面给出的信息找到问题 PP1 和 PP2 的类别

Question

假设 P1、P2、...、Pn 是 NP 类问题。PP1 和PP2 是未知问题（即，我们不知道它们属于P 类还是NP 类）。如果“P1, P2,...., Pn”问题可以在多项式时间内归结为 PP1，那么 PP1 可以归结为 PP2，PP2 可以在多项式时间内归结为另一个 NP 问题。以明确的理由指定 PP1 和 PP2 类？

这是我的一次算法考试中提出的问题。我认为这两个问题的答案都是 NP-hard，我想到的逻辑是，由于所有 P1、P2、....、Pn 都是 NP 问题，并且使用 NP-hard 的定义，我们可以推导出 PP1是 NP-Hard。在此之后寻找 PP2 的类，因为 PP1 可以简化为 PP2。因此，我们可以说 PP2 也是 NP-Hard。

问题的下一点提到 PP2 可以进一步简化为 NP 问题，但我认为这些信息对于查找 PP2 类没有用。让我们假设减少 PP2 后的问题是一些“X”问题。这个“X”问题将是 NP-Complete，因为它是 NP-hard 和 NP。

我的老师说PP1是NP-Hard，PP2是NP-Complete。请澄清我的疑问。

标签： algorithmnpnp-complete