A problem X is NP-complete if and only if
AX is in P
BX is in NP and has a known polynomial-time algorithm
CX reduces to some easy problem in P
DX is in NP AND every problem in NP polynomially reduces to X
Answer & Solution
Correct answer: D. X is in NP AND every problem in NP polynomially reduces to X
Two-part definition: (1) X ∈ NP (polynomial verifier exists), (2) X is NP-hard (every NP problem reduces to X in polynomial time). Together these make X 'the hardest in NP'. If X also had a polynomial-time algorithm (option B), then P = NP. NP-complete problems by definition reduce from EVERY NP problem, not to easy ones.
Related questions
An NP-hard problem differs from an NP-complete one because NP-hard problemsThe first problem proved to be NP-complete wasWhy does theoretical computer science draw the line at 'polynomial-time' for tractability?Which set inclusion is established (i.e., proven, not open)?The class NP is the set of decision problems for whichFloyd-Warshall detects the presence of a negative cycle byTopological sort is well-defined forThe running time and space of Floyd-Warshall on a graph with V vertices and E edges is