UGC NET CS 2014 Dec – paper-3
November 7, 2023
Computer-Networks
November 7, 2023
UGC NET CS 2014 Dec – paper-3
November 7, 2023
Computer-Networks
November 7, 2023

Question 9590 – P-NP

Ram and Shyam have been asked to show that a certain problem Π is NP-complete. Ram shows a polynomial time reduction from the 3-SAT problem to Π, and Shyam shows a polynomial time reduction from Π to 3-SAT. Which of the following can be inferred from these reductions?

Correct Answer: C

Question 1 Explanation: 
Note: As per Present syllabus, it is not required.
A
Π is NP-hard but not NP-complete
B
Π is in NP, but is not NP-complete
C
Π is NP-complete
D
Π is neither NP-hard, nor in NP
0 0 votes
Article Rating
Subscribe
Notify of
0 Comments
Inline Feedbacks
View all comments
0
Would love your thoughts, please comment.x
()
x
error: Alert: Content selection is disabled!!