edited by
428 views

1 Answer

0 votes
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.

Related questions

0 votes
0 votes
0 answers
1
0 votes
0 votes
1 answer
2
0 votes
0 votes
0 answers
4
commenter commenter asked Jun 13, 2019
353 views
I know that all NP problems can be reduced to Boolean Satisfiability SAT problem. But my question is whether SAT problem can be reduced to other NP complete problems like...