np

那么 3CNF亦可以。 也就是说：最大团不会比 3CNF容易。 •已知最大团问题是一个 NPC问题，试证明顶点覆盖问题也是 NPC问题 –首先易证顶点覆盖是一个 NP问题。 –为最大团的图 G构造一个图 G’ –然后欲证图 G有一个大小为 k的团当且仅当图G’ 有一个大小为 |V|k的顶点覆盖 –多项式规约说明：顶点覆盖不会比最大团问题容易。 –如果最大团是 NPC，顶点覆盖也是 NPC。

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

e that is a truth assignment satisfying []xF . For each1 2( )l s t   , the assignment satisfies following subformulas: ,0,1,2,3,4,5,6,7,8,9llllllllllzzzzzzzzzz           