computational complexity theory In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and explores the relationships between these classifications. A computational problem ...

, the

complexity class In computational complexity theory, a complexity class is a set (mathematics), set of computational problems "of related resource-based computational complexity, complexity". The two most commonly analyzed resources are time complexity, time and s ...

NP-equivalent is the set of

function problem In computational complexity theory, a function problem is a computational problem where a single output (of a total function) is expected for every input, but the output is more complex than that of a decision problem. For function problems, the ou ...

s that are both NP-easy and

NP-hard In computational complexity theory, a computational problem ''H'' is called NP-hard if, for every problem ''L'' which can be solved in non-deterministic polynomial-time, there is a polynomial-time reduction from ''L'' to ''H''. That is, assumi ...

. NP-equivalent is the analogue of

NP-complete In computational complexity theory, NP-complete problems are the hardest of the problems to which ''solutions'' can be verified ''quickly''. Somewhat more precisely, a problem is NP-complete when: # It is a decision problem, meaning that for any ...

for

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

integer An integer is the number zero (0), a positive natural number (1, 2, 3, ...), or the negation of a positive natural number (−1, −2, −3, ...). The negations or additive inverses of the positive natural numbers are referred to as negative in ...

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

subset In mathematics, a Set (mathematics), set ''A'' is a subset of a set ''B'' if all Element (mathematics), elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they a ...

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

optimization problem In mathematics, engineering, computer science and economics Economics () is a behavioral science that studies the Production (economics), production, distribution (economics), distribution, and Consumption (economics), consumption of goo ...

is similar to the

decision problem In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question on a set of input values. An example of a decision problem is deciding whether a given natura ...

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 In science, computing, and engineering, a black box is a system which can be viewed in terms of its inputs and outputs (or transfer characteristics), without any knowledge of its internal workings. Its implementation is "opaque" (black). The te ...

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 – ) S := S – return S Another well-known NP-equivalent problem is the

traveling salesman problem In the theory of computational complexity, the travelling salesman problem (TSP) asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exac ...

Clarification

In this context ''NP'' stands for ''

nondeterministic polynomial time In computational complexity theory, NP (nondeterministic polynomial time) is a complexity class used to classify decision problems. NP is the set of decision problems for which the problem instances, where the answer is "yes", have proofs ve ...

''.
There are also NP-equivalence classes of

Boolean function In mathematics, a Boolean function is a function whose arguments and result assume values from a two-element set (usually , or ). Alternative names are switching function, used especially in older computer science literature, and truth functi ...

s, where ''NP'' stands for ''negation'' and ''permutation''. See e.g. the sequence in the

OEIS The On-Line Encyclopedia of Integer Sequences (OEIS) is an online database of integer sequences. It was created and maintained by Neil Sloane while researching at AT&T Labs. He transferred the intellectual property and hosting of the OEIS to th ...

. Often used in the context of NPN-equivalence classes. (E.g. i
A New Pairwise NPN Boolean Matching Algorithm...
)

Notes

References

* . {{DEFAULTSORT:Np-Equivalent Complexity classes