归约的传递性
归约之间存在传递性。
定理4.如果 X \leq_p Y, Y \leq_p Z,,则 X \leq_p Z
通过上述归约,可以得到:
3-SAT \leq_p 独立集 \leq_p 顶点覆盖 \leq_p 集合覆盖

0
Posted in 算法设计与分析

Leave a Comment:

电子邮件地址不会被公开。