Q. Two persons X and Y have been asked to show that a certain problem p is NP-complete. X shows a polynomial time reduction from the 3-SAT problem to p and Y shows a polynomial time reduction from p to 3-SAT. From these reduction it can be inferred that (Solved)
1. P is NP-complete
2. P is NP-hard but not NP-complete
3. P is in NP but not NP-complete
4. P is neither NP-hard nor in NP
- a. P is NP-complete