Complete vs. NP

2018-06-14 00:31:51

If a problem A known to be NP-Complete can be reduced to another problem B in polynomial time then B is (A) NP-Complete (B) NP-hard

Nothing is given about problem B whether it is in NP or not. I'm confused because in Hopcraft and Ullman book there is theorem given if a NP-complete problem P1 can be reduced to problem P2 in polynomial time then P2 is NP-complete. But it also required for a problem to be NP-Complete that it should belong to NP class. Guys help in understanding this concept.

If A can be reduced to B in polynomial time all you know is that B is harder then A. In your case, if A is NP-complete, B is NP-hard.

If B also happens to be in NP then B will be NP-complete (since NP-complete means being both in NP and being NP-hard at the same time).

However, nothing stops you from reducing A to a problem that is not in NP. For example, it is trivial to reduce any problem in NP to the halting problem - a problem that is undecideable in addition to being NP-hard:

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

Since problem A can be reduced to problem B in polynomial time, any solution to problem B can be used to find a solution to A. Or more simply, solving A cannot be harder than solving B. Since we know A is NP-complete, which class of problems is at least as hard as NP-complete problems?

For reference you might also want to take a look at the wikipedia articles on NP-Hard (specifically the 2nd sentence), NP-Complete. and Reduction.

If A is NP-Complete, then it is also necessarily NP. This in turns means that every potential solution for A can be verified in polynomial time, which implies that the same is true for B (since A is reducible to B in polynomial time). Hence B is NP; it doesn't have to be stated as separate condition.

链接地址: http://www.djcxy.com/p/39932.html

上一篇: 什么是Non

下一篇: 完成与NP