我想总结一下关于复杂性的一些问题。它们中的哪一个可以在多时间内解决？
I） 求给定图的最大亚完全图=集团问题
II） 在
n对象中选择一些元素，其中值和权重使得所选元素的权重之和不会更大比特定界限和值的总和是最大III） 求图的所有循环
IV） 找到一条访问每个顶点一次的路径=确定一个图是哈密顿
我认为IV是NP完全的哈密顿路径，III是NP硬和NP完全的，II是NP完全，I是NP完全。因此0在poly时间内求解。
谁能更清楚地告诉我这些问题的NP难和NP完全？我说得对吗？
正如您所指出的，第（1）、（2）和（4）部分都是著名的NP难题（最大团、背包和哈密顿路径）。然而，这些问题不属于NP，因为NP由决策问题（答案是"是"或"否"的问题）组成，而这些问题不是决策问题。
第（3）部分更加细致入微。这个问题是一个计数问题-目标是确定存在多少某种类型的对象-而不是一个决策问题，所以它不可能是NP问题。据我所知，还不知道这个问题有多难。众所周知，如果它可以在多项式时间内解决，那么P=NP（详见此链接），具体的证明表明它也是NP难的。
如果p≠NP，那么这些都不能在多项式时间内求解。如果这些问题中的任何一个可以在多项式时间内求解，那么P=NP。它们都是NP难的。
希望这能有所帮助！
因为有人问我关于推荐人的问题，我发布了我的评论作为答案：
II） 在n个对象中选择一些元素，其中值和权重使得所选元素的权重之和不会更大比特定界限和值的总和是最大
这是一个背包问题，如果权重不是输入大小的一部分，即解仅是n的多项式，则它是多时间的。
它在O(n * W)中运行，其中W是允许的最大重量。当然，如果W与n相关，例如如果W = 2^n，则这可以不是多项式。
你可以在这里阅读：
http://en.wikipedia.org/wiki/Knapsack_problem#Dynamic_programming_in_advance_algorithm
http://www.personal.kent.edu/~rmuhamma/Agorithms/MyAgorithms/Dynamic/knapsackdyn.htm