here we talk about implies ....not reducible plz check i think right or wrong

The Gateway to Computer Science Excellence

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.

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.

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,741 questions

57,251 answers

198,045 comments

104,670 users