NP equivalence

NP equivalence is a term from complexity theory in computer science . It provides a basic statement as to whether search problems can still be practically solved with an increasing number of paths or objects to be searched, or whether the required time or memory expenditure increases rapidly in macrocosmic dimensions.

Formally, a search problem is NP -equivalent if it is NP-easy and NP-difficult . This is the case if and only if the associated decision problem is NP-complete . An NP-equivalent problem is solvable in polynomial time if and only if P = NP .