选择
难近似计算的问题？
不存在伪多项式解法的问题
简答
1.证明一个npc，nphard问题能用多项式时间求解 iff np = p
2.证明渐进近似比的两种定义方式等价
3.异步k-邻居算法改为单向发送msg的时间复杂度，如何改进
4. max((c*/c, c/c*) <= p(n), |(c* - c)/c*| <= q(n) 求证 q(n) <= p(n) -1
算法
1.异步图的flooding，收敛算法
2.给出vertex cover的近似算法，求近似比
