NP-easy

In computational complexity theory, a problem is said to be NP-easy if it is not harder than any problem in NP. More formally, a problem X is NP-easy if there exists a polynomial-time reduction from X to some problem Y in NP. This means that if we had a hypothetical oracle (or subroutine) that could solve Y in polynomial time, then we could use that oracle to solve X in polynomial time as well.

NP-easiness is a property relating a problem to the class NP. A problem can be NP-easy without being in NP itself. In fact, a problem can be harder than all problems in NP (such as being NP-hard) and still be NP-easy. This might seem counterintuitive, but the definition only requires a reduction to a problem in NP, not from one.

The concept of NP-easiness is often used in conjunction with NP-hardness. If a problem is both NP-hard and NP-easy, then it is NP-complete. This is because if a problem X is NP-hard, then every problem in NP can be reduced to X. If, in addition, X is NP-easy, then X can be reduced to a problem in NP. Combining these two facts implies that X is equivalent to the hardest problems in NP, thus making it NP-complete.

Note that some sources use the term "NP-hard" loosely to mean "at least as hard as the hardest problems in NP" and effectively treat "NP-hard" as synonymous with the combination of "NP-hard" and "NP-easy". However, it is important to maintain the distinction between the two terms for clarity and precision.