川大cs sub 归来,题目重温中

tonychinUID: 169511

总体上比较顺利,就是似乎早上去得有点太早了,八点不到就到考场了.至于题目嘛,也不算很难,还是那样,考得很广.正在回忆题目,回忆出来就发布在我的blog上面啦

afxUID: 2106290

请问你的blog在哪里？

davidjackyUID: 135962

[CS SUB]NP-completeness 问题
最近好像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问题。

后天就考了，时间很紧张，总结一下这些供大家参考，应该有用的。

tonychinUID: 169511

谢谢楼上，已经把回忆题目发出来了，记得很模糊，非常不好意思