0

I am studying NP and I can't understand how can I solve the below questions. I would like to know the strategy that I should use to be able to solve this kind of problems.

The question is:

Assume A and B are specific decision problems and that f is a polynomial-time function for reducing A to B. Which statement is true and which is false?

  1. if A →f B and A ∈ P, then B ∈ P
  2. if A →f B and B ∈ NP, then A ∈ P
  3. if A →f B and A ∈ NPC, then B ∈ NPH
  4. if A →f B and B ∈ NPC, then A ∈ NPC
  5. if A →f B and B →f A, then A, B ∈ NPC
  6. if A →f B and B ∈ NPC, then B →f A
  7. if A →f B and A ∈ NPC, then B ∈ NPC
  8. if A →f B and A ∈ NPH, then B ∈ NPC

Thanks in advance.

Khaled Omar
  • 27
  • 2
  • Pivot to https://cstheory.stackexchange.com/ https://math.stackexchange.com/ – Cyker Jul 16 '18 at 23:44
  • Please don't cross-post on multiple sites. @Cyker, if you're going to suggest another site, in the future could I ask you to please let the poster know not to post on multiple sites? You can suggest they delete this copy before posting elsewhere. Thank you. (That said, this question is not likely to be well received on either of those sites in its current form, and it is totally off-topic on cstheory.) – D.W. Jul 17 '18 at 02:06
  • @D.W. This question is clearly not a fit for SO which is about programming questions. By *pivot* I mean *change your direction and have a look at other places to see if those are a better fit*. It doesn't mean I encourage cross-post. But if the poster caused problems elsewhere, I'd be happy to leave these misplaced questions to forum moderators. – Cyker Jul 17 '18 at 02:28
  • I think it is similar to this question https://stackoverflow.com/questions/34079628/reduction-of-a-to-b-true-or-false – Khaled Omar Jul 17 '18 at 17:07

2 Answers2

0

  • A → B and A ∈ P, then B ∈ P => TRUE

  • A → B and B ∈ NP, then A ∈ P => FALSE

  • A → B and A ∈ NP-C, then B ∈ NP-H => TRUE

  • A → B and B ∈ NP-C, then A ∈ NP-C => TRUE

  • A → B and B ∈ NP-C, then B → A => TRUE

  • A → B and A ∈ NP-C, then B ∈ NP-C => FALSE

  • A → B and A ∈ NP-H, then B ∈ NP-C => FALSE

If A can be reduced A -> B in O(n) time and A is NP-C you couldn't guarantee that A is NP-C because B is NP-Hard (could be NP-C but you don't know).

Otherwise, if A can be reduced A->B in O(n) time and B is NP-C you can guarantee that A is NP-C.

When you apply a reduction in polynomial time it means that you are reducing into the same class of complexity.

I hope this helps you!

Iván Greve
  • 1
0
  • if A →f B and A ∈ P, then B ∈ P False
  • if A →f B and B ∈ NP, then A ∈ P False
  • if A →f B and A ∈ NPC, then B ∈ NPH True
  • if A →f B and B ∈ NPC, then A ∈ NPC False
  • if A →f B and B →f A, then A, B ∈ NPC False
  • if A →f B and B ∈ NPC, then B →f A False
  • if A →f B and A ∈ NPC, then B ∈ NPC False
  • if A →f B and A ∈ NPH, then B ∈ NPC False
kutlu
  • 74
  • 9
  • if A →f B and b ∈ P, then A ∈ P this is correct but not first one. Also If you say B is NPC, A can be problem from NP and you should proof all problems in NP reducible to B. Because, NPC is both NP and NPH. NPH requires this. – kutlu May 18 '22 at 22:08