Given two problems X and Y, Y is NP complete and X reduces
Given two problems X and Y, Y is NP complete and X reduces to Y in polynomial time. Which of the following is a valid statement ?
AX is NP hard
BX is NP complete
CX is an NP, but not necessarily NP complete
DIf X can be solved in polynomial time, so also can Y.
All DiscussionsClick here to write answer
Answer : X is NP complete
Explanation:
A decision problem C is NP-complete if:
i.) C is in NP, and
ii.) Every problem in NP is reducible to C in polynomial time.C can be shown to be in NP by demonstrating that a candidate solution to C can be verified in polynomial time.
Note that a problem satisfying condition 2 is said to be NP-hard, whether or not it satisfies condition 1.
Reference:https://en.wikipedia.org/wiki/NP-completeness
All Comments
Post your answers here:
Post
