in Algorithms
1,709 views
0 votes
0 votes
Q)We wish to show that problem B is NP-complete. Which of the following facts is sufficient to establish this.

 A)There is a polynomial time reduction from B to SAT.

 B)There is a polynomial time reduction from SAT to B

C) There is a polynomial time reduction from B to SAT, and B has a checking algorithm.

 D)There is a polynomial time reduction from SAT to B, and B has a checking algorithm.

I think option is B

Can anyone explain what is the answer??
in Algorithms
1.7k views

4 Comments

The correct answer is option D
0
0
@Nick ,could u please explain why B is wrong ?
0
0
We need a reduction from an NP-complete problem to B and evidence that B belongs to NP.
0
0

Please log in or register to answer this question.

Related questions

1 vote
1 vote
0 answers
2