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?

1 Answer 1

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

4
  • In second case, A can be in NP-Hard also right? Then the statement becomes false.
    – Jay Patel
    Dec 4, 2015 at 3: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 4, 2015 at 3: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, 2019 at 22:08
  • Second statement false. It should be Np Hard
    – kutlu
    May 19, 2022 at 2:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.