np

不可解问题：停机问题

p:可以在多项式时间求解的问题

np:可以在多项式时间验证的问题

p属于np,因为可解一定可验证。

np里最难的问题npc

reduction归约

假设有两个问题X和Y，存在一个多项式时间内的算法f，使得：

• 可以把x的输入转化为y的输入，即\(y_i=f(x_i)\)
• 该算法保证两个问题转化前后的答案相同，即\(x_i \in X\ \ iff\ \ y_i \in Y\)

Y更难，因为如果可以多项式时间解决Y,那么就可以解决X,即为\(X\leq _pY\)

travelling salesman problem 旅行商问题

给定一个边带权重的的完全图（任意两点都有边相连）和一个整数k，求是否存在一个简单环路，使得经历每个点有且仅有一次，并且路径<=k

vertex cover problem顶点覆盖

最大团问题

随机算法

面试策略

• 非随机算法：记录一个最好的，从前往后依次面试，当有更好的时，雇佣他并更新最大值
  • 最坏情况：全部都被雇佣
• 随机算法：对所有面试者进行随机算法，使得最好的人出现在前i个位置的概率为1/i