[CS]NP-completeness 问题

tonychinUID: 169511

最近好像NP-completeness是个热点，定义：

NP-complete: A decision problem is NP-complete if it is in NP and in NP-hard.

以下几个是NP-complete问题：

The Boolean satisfiability problem (SAT)
The knapsack problem
The Hamiltonian cycle problem
The Travelling salesman problem
The Subgraph isomorphism problem
The Subset sum problem
The Clique problem
The Vertex cover problem
The smallest problem
Finding the longest simple path
Finding all the spanning trees

当然，SAT问题和MAX SAT问题也是NP-complete问题

最短路径问题是P问题，也就是有权图中两点最短路径问题，以及线性规划linear programming问题。

后天就考了，时间很紧张，总结一下这些供大家参考，应该有用的。
欢迎大家到我的blog交流：http://blog.gter.net/blog.asp?name=TONYCHIN

AutoseaUID: 192045

调度问题和点着色也是NPC

这个网页列出了很多NPC问题，可以参考一下：
http://www.csc.liv.ac.uk/~ped/te ... 2/annotated_np.html