The Gateway to Computer Science Excellence
0 votes
126 views

in Algorithms by Junior (681 points)
edited by | 126 views

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.
by Active (4.1k points)
0
here we talk about implies ....not reducible  plz check i think right or wrong
0
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

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,741 questions
57,251 answers
198,045 comments
104,670 users