花梓
0

归约的传递性

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

0
Post Views: 210
Posted in 算法设计与分析

Leave a Comment:

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