0

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

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

4

2 回答 2

2

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

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

希望这可以帮助!

于 2011-03-19T19:50:52.180 回答
-1

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

于 2011-03-19T18:03:21.493 回答