NP-equivalent

NP- equivalence is a term used in complexity theory within computer science. It provides a statement of principle about whether search problems with an increasing number of paths to be searched or objects are still virtually solvable, or whether the required time or memory overhead grows rapidly in macroscopic dimensions.

Formally, a search problem NP- equivalent if there is NP- easy and NP-hard. This is exactly the case when the associated decision problem is NP -complete. An NP- equivalent problem is then exactly solvable in polynomial time if P = NP.

• Complexity Theory