Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

If A is NP-complete and if there is a reduction from A to B, does it imply that B is also NP-complete? [closed]

Suppose that A, B, and C are decision problems. Suppose also that A is polynomial-time reducible to B and that B is polynomial-time reducible to C. If both A and C are NP-complete, then does it imply that B is also NP-complete?

I know that, if A is NP-complete and it is polynomial-time reducible to B, then B is NP-hard. However, in order for a problem to be NP-complete, it must meet (1) it's in NP, and (2) it's NP-hard.

I have no idea how to prove the first requirement of NP-complete.

like image 358
hugoinperson Avatar asked Nov 30 '25 20:11

hugoinperson


1 Answers

If A is NP-complete and it is polynomial time reducible to B, then B is NP-hard.

If B is polynomial time reducible to C and C is NP-complete, then B is in NP.

A problem in NP which is in NP-hard is NP-complete.

Another way to show B is NP-complete is to notice that any two NP-complete problems (e.g A and C) are polynomially reducible to each other, and thus B is equivalent (two-way polynomially reducible) to any NP-complete problem.

like image 103
n. 1.8e9-where's-my-share m. Avatar answered Dec 03 '25 17:12

n. 1.8e9-where's-my-share m.



Donate For Us

If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!