Log In
0 votes

in Algorithms
edited by

1 Answer

0 votes
For 3rd point,

B problem is NP and A is NPC problem as given in question.

We know all NP problems are reducible to NPC problems.

So B --> A

Now if there exist a Polynomial time Algo for A ...hence A is decidable.

Then from B-->A we say B cannot harder than A and A is decidable ==> Hence B is also decidable i.e there exist a P time algorithm for it.
here we talk about implies ....not reducible  plz check i think right or wrong
option 3rd : Ptime for A ==> Ptime for B

Implication is false when LHS is True and RHS is false but in above answer we proved if there exist a Ptime algo for A [LHS true] then there do exist a P time algo for B [Hence RHS is also true].

So the given implication is true.

Related questions