ami*_*mir 2 algorithm complexity-theory np-complete reduction computation-theory
我已经研究了很多关于减少的问题,但我有一个不好的问题:我从CLRS中得到这个:
"......通过"减少"解决问题A来解决问题B,我们使用B的"容易度"来证明A的"容易度"."
我从"Christos H. Papadimitriou的计算复杂性"中得出这个结论:
"......如果B减少到A,问题A至少和问题B一样难."
我对这两个概念感到困惑:当我们使用easyiness时,我们说问题X简化为问题Y,如果我们有Y的多项式时间算法,并且还原过程是在多项式时间内完成的,那么问题X在多项式时间内是可解的,X是比Y容易或至少不比Y更难.
但是当我们使用硬度时,我们说问题X减少到问题Y并且Y比X更容易或者至少不比X更难.
我真的很困惑,请帮帮我.特别感谢.
我想你可能错过了第一个引用"减少A到B",第二个引用说"将B减少到A".
如果X减少到Y,意味着Y可以用来求解X,那么X并不比Y更难.那是因为多项式 - 复杂度降低被认为是"自由的",所以通过将X减少到Y,我们找到了一种方法来解决X使用任何解决方案都有Y.
因此,在第一个引用中,如果A减少到B而B很容易,那意味着A很容易(严格来说,这并不难).
第二个引用使用逻辑矛盾:如果B减少到A而B很难,那么A必须很难(严格来说,这并不容易).证明:如果A很容易,则B很容易(如上所述,但A和B相反).B不容易,因此A并不容易.
你的陈述,"我们说问题X减少到问题Y和Y比X更容易,或者至少不比X更难"是错误的.这是可能的X减少到Y(也就是说,我们可以用y以解决X),即使ÿ其实是比X.更难因此,我们可以减少加(X)一些NP难问题的一个特例(Y),通过定义在多项式时间内构造NP-hard问题实例的方案,其解为两个输入数的和.这并不意味着加入是NP难的,只是因为我们为自己制造了不必要的困难.使用这种减少来执行添加是不明智的,因为有更好的方法来添加.好吧,假设P!= NP,那就更好了.