1

There are two statements: If a decision problem A is polynomial-time reducible to a decision problem B (i.e., A≤ pB ), and B is NP-complete, then A must be NP-complete.

And:

If a decision problem B is polynomial-time reducible to a decision problem A (i.e., B≤ pA ), and B is NP-complete, then A must be NP-complete.

Which of the above statements are true?

Can you also give explanation?

Jay Patel
  • 1,266
  • 6
  • 20
  • 38

1 Answers1

4

the first statement is false because it means that by solving B and then applying some polynomial time algorithm you can solve A but maybe there is another way to solve A that doesn't require solving B and maybe it's only polynomial.

the second statement is true because it means that you can solve B by first solving A then apply some polynomial time algorithm to solve B but B is NP-complete so A has to be NP-complete

m7mdbadawy
  • 920
  • 2
  • 13
  • 17
  • In second case, A can be in NP-Hard also right? Then the statement becomes false. – Jay Patel Dec 04 '15 at 03:21
  • @JayPatel in the first statement A maybe NP-hard or maybe not which make the statement False because the first statment says "must be NP-hard" which is not the case but in the second statement A is NP-hard always so it's True – m7mdbadawy Dec 04 '15 at 03:39
  • The second statement is false, because you don't know if A belongs to NP. If so, then A it's NP-complete, otherwise you can't say it! – FonzTech Aug 21 '19 at 22:08
  • Second statement false. It should be Np Hard – kutlu May 19 '22 at 02:19