完全性
第9章np完全性理论与近似算法
成。 ||w)( 2nO 在算法的第二阶段中，非确定性地选择 V的一个 k元子集 V’V。 算法的第三阶段是确定性地检查 V’的团性质。 若 V’是一个团则接受输入，否则拒绝输入。 这显然可以在 时间内完成。 因此，整个算法的时间复杂性为。 )( 4nO)( 4nO非确定性算法在多项式时间内接受语言 CLIQUE， 故 CLIQUE∈NP。 16 多项式时间验证 VP={L|L∈∑* ， ∑