Question

Show that a problem is \(N P\) -easy if and only if it reduces to an \(N P\) -complete problem.

Short answer

A problem is NP-Easy if it reduces to an NP-complete problem and vice-versa. This is because by definition, an NP-easy problem can be reduced to any problem in NP including NP-Complete problems. Feasibly, if a problem is reducible to an NP-Complete problem, it is essentially an NP-Easy problem due to the fact that it can be deduced in polynomial time.

Step-by-step solution

Understanding of NP-Easy and NP-Completeness

Start by understanding the terms. NP-Easy are problems that can be reduced to any problem in NP in polynomial time. NP-Complete problems are those that are in NP and any problem in NP can be reduced to them in polynomial time. Therefore, for a problem to be NP-Easy it means it can be reduced to an NP-complete problem.

Reduction to NP-Complete implies NP-Easiness

If a problem reduces to an NP-Complete problem in polynomial time, then by definition of NP-Easy, it is an NP-Easy.

NP-Easiness implies Reduction to an NP-Complete Problem

Conversely, if a problem is NP-Easy then by definition it can be reduced to any problem in the NP in polynomial time. Since NP-Complete problems are in NP, then the problem can be reduced to an NP-Complete problem. This shows the equivalence.