NP-equivalent

In computational complexity theory, the complexity class NP-equivalent is the set of function problems that are both NP-easy and NP-hard.[1] NP-equivalent is the analogue of NP-complete for function problems.

For example, the problem FIND-SUBSET-SUM is in NP-equivalent. Given a set of integers, FIND-SUBSET-SUM 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 SUBSET-SUM. Given a set of integers, SUBSET-SUM is the problem of finding whether there exists a subset summing to zero. SUBSET-SUM is NP-complete.

To show that FIND-SUBSET-SUM is NP-equivalent, we must show that it is both NP-hard and NP-easy.

Clearly it is NP-hard. If we had a black box that solved FIND-SUBSET-SUM in unit time, then it would be easy to solve SUBSET-SUM. Simply ask the black box to find the subset that sums to zero, then check whether it returned a nonempty set.

It is also NP-easy. If we had a black box that solved SUBSET-SUM in unit time, then we could use it to solve FIND-SUBSET-SUM. If it returns false, we immediately return the empty set. Otherwise, we visit each element in order and remove it provided that SUBSET-SUM 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 FIND-SUBSET-SUM(set S)
    if not(SUBSET-SUM(S))
        return {}
    for each x in S
        if SUBSET-SUM(S – {x})
            S := S – {x}
    return S

Another well-known NP-equivalent problem is the traveling salesman problem.

Notes

Garey & Johnson (1979), p. 117, 120.

gollark: ++choose mandelbrot "golf/maths language" "smalltalk language" cry game "other projects" music sleep "new projects"

gollark: Greetings, apioform.

gollark: Besides, it's quick sort, as it runs in less than 1 second for my test input.

gollark: Plus, I even use that clever XOR swap algorithm from Wikipedia for maximum performance.

gollark: As any Haskell programmer knows, "if it compiles, it runs".

References

Garey, Michael R.; Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, ISBN 0-7167-1045-5.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Garey & Johnson (1979), p. 117, 120.