Nptel Daa week-8 Q-4

Question

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??

Comments

I think both B and D should be the answer..

SAT ≤_p B means problem B is at least as hard as SATISFIABILITY problem ... Since SAT is hard problem , So, Problem B should also be hard or we can say SAT problem is NP-Complete , So , problem B should also be NP-Complete... 

Actually , there are 2 ways to show reduction from one problem to another in polynomial time..

1) A ≤_p B , If we know problem B is easy then Problem A should also be easy

2) A ≤_p B ,if we know problem A is hard then problem B should also be hard....

According to me , option D is also correct because Problem B has a verification algorithm means we have a number and we have to verify the solution is correct or not ...So, decision problem B is NP ..So, we have Non-deterministic machine which can solve problem B in polynomial time...

Problem B is said to be NP-complete iff :-

1) Problem B is in NP

2) every problem in NP can be reduced to Problem B in polynomial time...

Since ,SAT is NPC problem  ..so , every problem in NP can be reduced to SAT ..and here it is given that  SAT ≤_p B ..So, we can say that all problems in NP can also be reduced to problem B..So , here , we proved both part ie. B is in NP and  every problem in NP can be reduced to Problem B in polynomial time...So, B should also be NPC...Please correct me if I m wrong..

---

question is not complete I think
@ Nick Nikhil
do u want answer for 2 SAT or 3SAT?

---

Question is right..SAT was the 1st NPC problem..There is a polynomial time reduction from SAT to 3-SAT ..since SAT is hard(NPC problem) , So , 3-SAT is also hard (NPC Problem)  ...

---

ok
yes B) should be ans
Nice explanation here http://drona.csa.iisc.ernet.in/~chandan/courses/complexity15/notes/lec3.pdf

---

@Srestha , Is D true ?

---

what is meaning of checking algo?

---

I think it means verification algorithms..

---

    ....

---

@ankit

I think verification algorithm used to chk numbers https://cs.stackexchange.com/questions/12969/how-to-show-that-problems-are-in-np

how do u chk here verification algo?

---

@srestha,  verification algorithm is used to show that a problem is in NP.. In this Algo,  we have a solution,  then we have to verify this  solution in polynomial time.. We can solve the problem in polynomial time by Non-deterministic machine because it works in parallel.. and verify the solution in polynomial time..
For example vertex cover problem is in NP..
Now, if we have a graph and a number 3 and we have to know whether we can cover the whole graph with 3 vertices or not..

---

yes, but this question is a reduction problem

how to apply here?

---

Problem B is said to be NP-complete iff :-

1) Problem B is in NP

2) every problem in NP can be reduced to Problem B in polynomial time...

Since   we have verification algo for B.. So it is in NP.. So we have proved 1st part.. 

For 2nd part   

Since ,SAT is NPC problem  ..so , every problem in NP can be reduced to SAT ..and here it is given that  SAT ≤_p B ..So, we can say that all problems in NP can also be reduced to problem B..So , here , we proved both part ie. B is in NP and  every problem in NP can be reduced to Problem B in polynomial time...So, B should also be NPC...

---

Thanks for the comments.

I am confused between option B and D but only one option will be considered as a correct answer.

Some times I feel like option B will be the answer for that question but Option D also the similar and additionally B has checking algorithm ..!!

---

@Nick , what is the given answer ?

---

Answer to this question is yet to be revealed on 04-04-2018 23:59

I am eagerly waiting for the correct option and explanation

---

Similar type question was asked in previous year

Suppose SAT reduces to a problem C. To claim that C is NPcomplete, we additionally need to show that:

A)There is a checking algorithm for C
B) Every instance of C maps to an instance of SAT
C)very instance of SAT maps to an instance of C
D) C does not have an efficient algorithm.

Correct answer: (a) There is a checking algorithm for C

The reduction establishes NP-hardness. We have to show that C is in NP, for which a checking algorithm suffices.

 

I think from this question and solution we can correctly pick the option either B or D

---

@Nick , Complexity Theory is not in gate syllabus..So in which exam , it was asked previous year ?

---

Online courses  NPTEL

---

The correct answer is option D

---

@Nick ,could u please explain why B is wrong ?

---

We need a reduction from an NP-complete problem to B and evidence that B belongs to NP.