这是一个NP问题吗？
我最近阅读了有关 NP 和 P。那么寻找给定单词的组合问题是一个NP问题吗？例如，给定单词anto，结果可以是anot、toan等。据我所知，每当我们可以在多项式时间内检查问题的解决方案时，就意味着它属于 NP 范畴。那么组合问题属于NP问题吗？
这只是为了知道我是否已经很好地理解了NP和P。
I recently read articles about NP and P. So the problem of finding the combinations of the given word is an NP problem? For example, the given word anto, the result can be anot,toan and so on. As I came to know, whenever we can check the solution for the problem in a polynomial time then it means that it comes under NP. So the problem of combination comes under NP?
This is just to know whether I have understood NP and P very well.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
这个问题不在 NP 中，因为 NP 由决策问题组成，这些问题有是或否的答案。然而，这个问题可以很容易地变成一个决策问题，将其重新表述为“给定一组字母、一本字典以及该字典中的一些单词，是否存在字典中但不在字典中的这些字母的字谜”到目前为止我们拥有的单词列表？”
这个问题肯定可以在多项式时间内解决（因此是非确定性多项式时间），因为您可以遍历字典检查每个可能的单词，这需要字典和输入单词大小的多项式时间。然而，这在 P 或 NP 中都不成立，因为你没有问是/否问题。
希望这有帮助！
This problem is not in NP because NP consists of decision problems, problems which have a yes or no answer. However, this problem can easily be made into a decision problem by rephrasing it as "given a collection of letters, a dictionary, and some number of words out of that dictionary, is there an anagram of those letters that's in the dictionary but not in the list of words we have so far?"
This problem is definitely solvable in polynomial time (and therefore nondeterministic polynomial time) because you can just iterate across the dictionary checking each possible word, which takes time polynomial in the size of the dictionary and input word. However, that doesn't make it in either P or NP, since you aren't asking a yes/no question.
Hope this helps!
AFAIK我知道NP是一个决策问题，因为这个问题没有解决方案。剩下的通常是贪心算法或遗传算法，它们可能会在多项式时间内找到一个好的解决方案。暴力破解是不切实际的，甚至不确定是否能找到最优解。
AFAIK I know NP is a decision problem because there isn't a solution to the problem. What's left is often a greedy algorithm or genetic algorithm that may find a good solution in polynominal time. A brute-force is impratical and it is not even sure if it find the optimal solution.