algorithm - 这是一个NP问题吗？

Question

我最近阅读了有关NP和P的文章。那么寻找给定单词组合的问题是NP问题吗？例如，给定单词anto，结果可以是 anot,toan 等。据我所知，只要我们可以在多项式时间内检查问题的解决方案，就意味着它属于 NP。那么组合问题属于NP吗？

这只是为了知道我是否已经很好地理解了NP和P。

Answer 1

这个问题不在 NP 中，因为 NP 由决策问题组成，这些问题有是或否的答案。然而，这个问题可以很容易地变成一个决策问题，将其改写为“给定一组字母、一本字典和该字典中的一些单词，是否存在那些在字典中但不在字典中的字母的字谜？到目前为止我们的单词列表？”

这个问题绝对可以在多项式时间内解决（因此是非确定性多项式时间），因为您可以遍历字典检查每个可能的单词，这需要字典和输入单词大小的时间多项式。但是，这在 P 或 NP 中都没有，因为您没有问是/否问题。

希望这可以帮助！

Answer 2

AFAIK 我知道 NP 是一个决策问题，因为该问题没有解决方案。剩下的通常是贪心算法或遗传算法，它们可能会在多项式时间内找到一个好的解决方案。蛮力是不切实际的，甚至不确定它是否找到了最佳解决方案。