Reduce归约 证明原理

一、归约

Reducing A(已知的） to B（要证明的）

思想： 我们现在遇到了个问题，可以把它转化到一个某个已解决的问题上，而不是一定要直接解决这个问题 概念描述： 设计一个函数f(x)，把问题A的输入A_input转换成问题B的一个输入B_input=f(x)，这样就能用问题B的解法来求解。（输出真或假） A可以被归约到B。

难点：转换函数f(x)的设计必须要保证问题B的输出结果和相应的问题A上的答案保持一致。  

可视化归约

即A{1,2,3},{2,4},{3,4},{4,5}}。可以看出，B集合的并集恰好等于A集合，那么问题的解是：SETCOVER={{1,2,3},{4,5}}。