1

这些问题如何落入 P、NP、NP-Hard 等...集合的挂毯中？我不知道是否存在任何此类问题，但引发我思考过程的是考虑旅行商问题的可判定性：

    Given a list of cities and the distances between each pair of cities, and a 
    Hamiltonian path P, is P the shortest Hamiltonian path?

我怀疑我们无法在多项式时间内验证 P 的“最短性”，其中这个决策问题甚至不在 NP 中。那么在这种情况下它落在哪里呢？

4

3 回答 3

0

这个问题在 co-NP 中。您可以将 NP 视为一类问题，如果答案是肯定的，那么我可以给您的少量信息会让您相信这一点。例如，问题

G 中是否存在成本最多为 k 的哈密顿循环？

在 NP 中，因为如果答案是肯定的，我可以给你循环，你可以检查它是否有效。想出那个循环很困难，但是一旦你有了哈密顿循环，就很容易用它来检查答案。

co-NP 课程由问题组成，如果答案是否定的，我可以提供少量信息让你相信这一点。在您的情况下，假设不，P 不是最短哈密顿路径。这意味着有一些较短的路径 P'。如果我给你 P'，你可以很容易地检查出 P 不是理想的。想出 P' 可能真的很难（事实上，它是 co-NP 难的！），但是一旦你有了它，就可以很简单地用它来确认答案是否定的。

希望这可以帮助！

于 2014-03-31T20:33:03.127 回答
0

给定整数 n 和 k，2^n - 1 是第 k 个梅森素数吗？

如果 p + 1 的完全分解已知，并且如果 p = 2^n - 1 则 p + 1 的完全分解是微不足道的，则可以证明 p 是 p 大小的质数时间多项式。

但是，这是 p 大小的多项式。2^n - 1 可以在时间上检查素数，它是 n 中的多项式。但是，这不是问题大小的多项式，它大致是 n 和 k 中的位数。它只会回答 2^n - 1 是否是梅森素数的问题。为了证明它是第 k 个梅森素数，我们必须检查 2^m - 1 for 1 <= m < n 并证明其中 k-1 个是素数。

目前，对于 k >= 44 和许多 8 位值 n，该问题的答案未知。

于 2014-04-01T22:44:40.523 回答
0

给定两个整数 n 和 m，是否正好有 m 个素数 p <= n？

这可以在大约 O (n^(2/3)) 内解决，并且可能稍微快一些，但问题大小当然不是 n 而是 log (n)，因此它需要 n 的次线性时间，但需要 n 的指数时间问题大小。这并不比你对 NP 问题的预期更糟。但是，我看不到任何可以让您更快检查的信息。

（实际上，有一种算法可以在大约 O (n^(2/3)) 步内确定质数 <= n 的数量，但是没有已知的算法可以比找到答案更快地检查答案。）

于 2014-03-31T21:32:56.237 回答