In computational complexity theory, the complexity class NPequivalent is the set of function problems that are both NPeasy and NPhard.^{[1]} NPequivalent is the analogue of NPcomplete for function problems.
For example, the problem FINDSUBSETSUM is in NPequivalent. Given a set of integers, FINDSUBSETSUM is the problem of finding some nonempty subset of the integers that adds up to zero (or returning the empty set if there is no such subset). This optimization problem is similar to the decision problem SUBSETSUM. Given a set of integers, SUBSETSUM is the problem of finding whether there exists a subset summing to zero. SUBSETSUM is NPcomplete.
To show that FINDSUBSETSUM is NPequivalent, we must show that it is both NPhard and NPeasy.
Clearly it is NPhard. If we had a black box that solved FINDSUBSETSUM in unit time, then it would be easy to solve SUBSETSUM. Simply ask the black box to find the subset that sums to zero, then check whether it returned a nonempty set.
It is also NPeasy. If we had a black box that solved SUBSETSUM in unit time, then we could use it to solve FINDSUBSETSUM. If it returns false, we immediately return the empty set. Otherwise, we visit each element in order and remove it provided that SUBSETSUM would still return true after we remove it. Once we've visited every element, we will no longer be able to remove any element without changing the answer from true to false; at this point the remaining subset of the original elements must sum to zero. This requires us to note that later removals of elements do not alter the fact that removal of an earlier element changed the answer from true to false. In pseudocode:
function FINDSUBSETSUM(set S)
if not(SUBSETSUM(S))
return {}
for each x in S
if SUBSETSUM(S  {x})
S := S  {x}
return S
Another wellknown NPequivalent problem is the traveling salesman problem.
Notes
References
Full article ▸
