NP-Complete与NP-hard

Question

如果已知为NP-Complete的问题A可以在多项式时间内减少到另一个问题B那么B是(A)NP-Complete(B)NP-hard

没有关于问题B的任何内容,无论是否在NP中.我很困惑因为在Hopcraft和Ullman的书中有定理,如果NP完全问题P1可以在多项式时间内减少到问题P2,那么P2是NP完全的.但它也需要一个问题是NP-Complete它应该属于NP类.伙计们帮助理解这个概念.

Answer 1

如果A在多项式时间内可以简化为B,那么你知道B比A更难.在你的情况下,如果A是NP完全的,B是NP难的.

如果B也恰好在NP中,那么B将是NP完全的(因为NP完全意味着同时在NP中并且是NP-硬).

但是,没有什么可以阻止你将A减少到NP中不存在的问题.例如,将NP中的任何问题减少到停止问题是微不足道的 - 除了NP难以外,这个问题是不可判定的:

Construct the following program:
    Test all possible solutions for A.
    If one of them is successful halt and otherwise enter an infinite loop.
A has a solution if-and-only if that program halts