In computational complexity theory

Computational complexity theory

Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...

, the complexity class

Complexity class

In computational complexity theory, a complexity class is a set of problems of related resource-based complexity. A typical complexity class has a definition of the form:...

 NP-equivalent is the set of function problem

Function problem

In computational complexity theory, a function problem is a computational problem where a single output is expected for every input, but the output is more complex than that of a decision problem, that is, it isn't just YES or NO...

s that are both NP-easy

NP-easy

In complexity theory, the complexity class NP-easy is the set of function problems that are solvable in polynomial time by a deterministic Turing machine with an oracle for some decision problem in NP....

 and NP-hard

NP-hard

NP-hard , in computational complexity theory, is a class of problems that are, informally, "at least as hard as the hardest problems in NP". A problem H is NP-hard if and only if there is an NP-complete problem L that is polynomial time Turing-reducible to H...

. NP-equivalent is the analogue of NP-complete

NP-complete

In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...

 for function problem

Function problem

In computational complexity theory, a function problem is a computational problem where a single output is expected for every input, but the output is more complex than that of a decision problem, that is, it isn't just YES or NO...

s.

For example, the problem FIND-SUBSET-SUM is in NP-equivalent. Given a set of integer

Integer

The integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...

s, FIND-SUBSET-SUM is the problem of finding some nonempty subset

Subset

In mathematics, especially in set theory, a set A is a subset of a set B if A is "contained" inside B. A and B may coincide. The relationship of one set being a subset of another is called inclusion or sometimes containment...

 of the integers that adds up to zero (or returning the empty set if there is no such subset). This optimization problem

Optimization problem

In mathematics and computer science, an optimization problem is the problem of finding the best solution from all feasible solutions. Optimization problems can be divided into two categories depending on whether the variables are continuous or discrete. An optimization problem with discrete...

 is similar to the decision problem

Decision problem

In computability theory and computational complexity theory, a decision problem is a question in some formal system with a yes-or-no answer, depending on the values of some input parameters. For example, the problem "given two numbers x and y, does x evenly divide y?" is a 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.