Misplaced Pages

#233766

59-535: A simple example of an NP-hard problem is the subset sum problem . Informally, if H is NP-hard, then it is at least as difficult to solve as the problems in NP . However, the opposite direction is not true: some problems are undecidable , and therefore even more difficult to solve than all problems in NP, but they are probably not NP-hard (unless P=NP). A decision problem H is NP-hard when for every problem L in NP, there

118-441: A graph isomorphism exists between two graphs. Two graphs are isomorphic if one can be transformed into the other simply by renaming vertices . Consider these two problems: The Subgraph Isomorphism problem is NP-complete. The graph isomorphism problem is suspected to be neither in P nor NP-complete, though it is in NP. This is an example of a problem that is thought to be hard , but is not thought to be NP-complete. This class

177-414: A binary tree: each level in the tree corresponds to an input number; the left branch corresponds to excluding the number from the set, and the right branch corresponds to including the number (hence the name Inclusion-Exclusion). The memory required is O ( n ) {\displaystyle O(n)} . The run-time can be improved by several heuristics: In 1974, Horowitz and Sahni published

236-419: A different level. All NP-complete problems are also NP-hard (see List of NP-complete problems ). For example, the optimization problem of finding the least-cost cyclic route through all nodes of a weighted graph—commonly known as the travelling salesman problem —is NP-hard. The subset sum problem is another example: given a set of integers, does any non-empty subset of them add up to zero? That

295-508: A faster exponential-time algorithm, which runs in time O ( 2 n / 2 ⋅ ( n / 2 ) ) {\displaystyle O(2^{n/2}\cdot (n/2))} , but requires much more space - O ( 2 n / 2 ) {\displaystyle O(2^{n/2})} . The algorithm splits arbitrarily the n elements into two sets of n / 2 {\displaystyle n/2} each. For each of these two sets, it stores

354-473: A list of the sums of all 2 n / 2 {\displaystyle 2^{n/2}} possible subsets of its elements. Each of these two lists is then sorted. Using even the fastest comparison sorting algorithm, Mergesort for this step would take time O ( 2 n / 2 n ) {\displaystyle O(2^{n/2}n)} . However, given a sorted list of sums for k {\displaystyle k} elements,

413-402: A nondeterministic Turing machine to perform the whole search. " Complete " refers to the property of being able to simulate everything in the same complexity class . More precisely, each input to the problem should be associated with a set of solutions of polynomial length, the validity of each of which can be tested quickly (in polynomial time ), such that the output for any input is "yes" if

472-428: A polynomial time algorithm, all problems in NP do. The set of NP-complete problems is often denoted by NP-C or NPC . Although a solution to an NP-complete problem can be verified "quickly", there is no known way to find a solution quickly. That is, the time required to solve the problem using any currently known algorithm increases rapidly as the size of the problem grows. As a consequence, determining whether it

531-414: A problem is NP-complete when: The name "NP-complete" is short for "nondeterministic polynomial-time complete". In this name, "nondeterministic" refers to nondeterministic Turing machines , a way of mathematically formalizing the idea of a brute-force search algorithm. Polynomial time refers to an amount of time that is considered "quick" for a deterministic algorithm to check a single solution, or for

590-647: A simple recursion highly scalable in SIMD machines having O ( N ( m − x min ) / p ) {\displaystyle O(N(m-x_{\min })/p)} time and O ( N + m − x min ) {\displaystyle O(N+m-x_{\min })} space, where p is the number of processing elements, m = min ( s , ∑ x i − s ) {\displaystyle m=\min(s,\sum x_{i}-s)} and x min {\displaystyle x_{\min }}

649-400: A subroutine that solves Y {\displaystyle \scriptstyle Y} in polynomial time, one could write a program that calls this subroutine and solves X {\displaystyle \scriptstyle X} in polynomial time. This contrasts with many-one reducibility, which has the restriction that the program can only call the subroutine once, and the return value of

SECTION 10

#1732787930234

708-405: A subset whose sum is at most T , and subject to that, as close as possible to T . It is NP-hard, but there are several algorithms that can solve it reasonably quickly in practice. SSP is a special case of the knapsack problem and of the multiple subset sum problem. The run-time complexity of SSP depends on two parameters: As both n and L grow large, SSP is NP-hard. The complexity of

767-401: Is NP-complete if: C {\displaystyle \scriptstyle C} can be shown to be in NP by demonstrating that a candidate solution to C {\displaystyle \scriptstyle C} can be verified in polynomial time. Note that a problem satisfying condition 2 is said to be NP-hard , whether or not it satisfies condition 1. A consequence of this definition

826-482: Is NP-complete is first to prove that it is in NP, and then to reduce some known NP-complete problem to it. Therefore, it is useful to know a variety of NP-complete problems. The list below contains some well-known problems that are NP-complete when expressed as decision problems. To the right is a diagram of some of the problems and the reductions typically used to prove their NP-completeness. In this diagram, problems are reduced from bottom to top. Note that this diagram

885-414: Is a cycle or is bipartite is very easy (in L ), but finding a maximum bipartite or a maximum cycle subgraph is NP-complete. A solution of the knapsack problem within any fixed percentage of the optimal solution can be computed in polynomial time, but finding the optimal solution is NP-complete. An interesting example is the graph isomorphism problem , the graph theory problem of determining whether

944-500: Is a decision problem and happens to be NP-complete. There are decision problems that are NP-hard but not NP-complete such as the halting problem . That is the problem which asks "given a program and its input, will it run forever?" That is a yes / no question and so is a decision problem. It is easy to prove that the halting problem is NP-hard but not NP-complete. For example, the Boolean satisfiability problem can be reduced to

1003-535: Is a decision problem in computer science . In its most general formulation, there is a multiset S {\displaystyle S} of integers and a target-sum T {\displaystyle T} , and the question is to decide whether any subset of the integers sum to precisely T {\displaystyle T} . The problem is known to be NP-complete . Moreover, some restricted variants of it are NP-complete too, for example: SSP can also be regarded as an optimization problem : find

1062-929: Is a polynomial-time many-one reduction from L to H . Another definition is to require that there be a polynomial-time reduction from an NP-complete problem G to H . As any problem L in NP reduces in polynomial time to G , L reduces in turn to H in polynomial time so this new definition implies the previous one. It does not restrict the class NP-hard to decision problems, and it also includes search problems or optimization problems . If P ≠ NP, then NP-hard problems could not be solved in polynomial time. Some NP-hard optimization problems can be polynomial-time approximated up to some constant approximation ratio (in particular, those in APX ) or even up to any approximation ratio (those in PTAS or FPTAS ). There are many classes of approximability, each one enabling approximation up to

1121-511: Is a many-one reduction that can be computed with only a logarithmic amount of space. Since every computation that can be done in logarithmic space can also be done in polynomial time it follows that if there is a logarithmic-space many-one reduction then there is also a polynomial-time many-one reduction. This type of reduction is more refined than the more usual polynomial-time many-one reductions and it allows us to distinguish more classes such as P-complete . Whether under these types of reductions

1180-404: Is at most N C , so the time required is O ( N 2 C ) {\displaystyle O(N^{2}C)} . This solution does not count as polynomial time in complexity theory because B − A {\displaystyle B-A} is not polynomial in the size of the problem, which is the number of bits used to represent it. This algorithm is polynomial in

1239-481: Is at most linear in the number of states. The number of states is at most N times the number of different possible sums. Let A be the sum of the negative values and B the sum of the positive values; the number of different possible sums is at most B - A , so the total runtime is in O ( N ( B − A ) ) {\displaystyle O(N(B-A))} . For example, if all input values are positive and bounded by some constant C , then B

SECTION 20

#1732787930234

1298-407: Is called NP-Intermediate problems and exists if and only if P≠NP. At present, all known algorithms for NP-complete problems require time that is superpolynomial in the input size. The vertex cover problem has O ( 1.2738 k + n k ) {\displaystyle O(1.2738^{k}+nk)} for some k > 0 {\displaystyle k>0} and it

1357-508: Is called the P versus NP problem . But if any NP-complete problem can be solved quickly, then every problem in NP can, because the definition of an NP-complete problem states that every problem in NP must be quickly reducible to every NP-complete problem (that is, it can be reduced in polynomial time). Because of this, it is often said that NP-complete problems are harder or more difficult than NP problems in general. A decision problem C {\displaystyle \scriptstyle C}

1416-575: Is for the version of the problem where the target sum is not necessarily zero, as otherwise the problem would be trivial). In 2015, Koiliaris and Xu found a deterministic O ~ ( T N ) {\displaystyle {\tilde {O}}(T{\sqrt {N}})} algorithm for the subset sum problem where T is the sum we need to find. In 2017, Bringmann found a randomized O ~ ( T + N ) {\displaystyle {\tilde {O}}(T+N)} time algorithm. In 2014, Curtis and Sanches found

1475-440: Is known, however, that AC reductions define a strictly smaller class than polynomial-time reductions. According to Donald Knuth , the name "NP-complete" was popularized by Alfred Aho , John Hopcroft and Jeffrey Ullman in their celebrated textbook "The Design and Analysis of Computer Algorithms". He reports that they introduced the change in the galley proofs for the book (from "polynomially-complete"), in accordance with

1534-483: Is less than T/2 and it would fit in the set. Such a sum greater than T/2 is obviously more than OPT/2. The following algorithm attains, for every ϵ > 0 {\displaystyle \epsilon >0} , an approximation ratio of ( 1 − ϵ ) {\displaystyle (1-\epsilon )} . Its run time is polynomial in n and 1 / ϵ {\displaystyle 1/\epsilon } . Recall that n

1593-411: Is misleading as a description of the mathematical relationship between these problems, as there exists a polynomial-time reduction between any two NP-complete problems; but it indicates where demonstrating this polynomial-time reduction has been easiest. There is often only a small difference between a problem in P and an NP-complete problem. For example, the 3-satisfiability problem, a restriction of

1652-751: Is not obvious. The Cook–Levin theorem states that the Boolean satisfiability problem is NP-complete, thus establishing that such problems do exist. In 1972, Richard Karp proved that several other problems were also NP-complete (see Karp's 21 NP-complete problems ); thus, there is a class of NP-complete problems (besides the Boolean satisfiability problem). Since the original results, thousands of other problems have been shown to be NP-complete by reductions from other problems previously shown to be NP-complete; many of these problems are collected in Garey & Johnson (1979) . The easiest way to prove that some new problem

1711-477: Is possible to solve these problems quickly, called the P versus NP problem , is one of the fundamental unsolved problems in computer science today. While a method for computing the solutions to NP-complete problems quickly remains undiscovered, computer scientists and programmers still frequently encounter NP-complete problems. NP-complete problems are often addressed by using heuristic methods and approximation algorithms . NP-complete problems are in NP ,

1770-406: Is that if we had a polynomial time algorithm (on a UTM , or any other Turing-equivalent abstract machine ) for C {\displaystyle \scriptstyle C} , we could solve all problems in NP in polynomial time. The concept of NP-completeness was introduced in 1971 (see Cook–Levin theorem ), though the term NP-complete was introduced later. At the 1971 STOC conference, there

1829-458: Is the lowest integer. This is the best theoretical parallel complexity known so far. A comparison of practical results and the solution of hard instances of the SSP is discussed by Curtis and Sanches. Suppose all inputs are positive. An approximation algorithm to SSP aims to find a subset of S with a sum of at most T and at least r times the optimal sum, where r is a number in (0,1) called

NP-hardness - Misplaced Pages Continue

1888-472: Is the number of inputs and T is the upper bound to the subset sum. Note that without the trimming step (the inner "for each" loop), the list L would contain the sums of all 2 n {\displaystyle 2^{n}} subsets of inputs. The trimming step does two things: These properties together guarantee that the list L contains no more than n / ϵ {\displaystyle n/\epsilon } elements; therefore

1947-409: Is unknown whether there are any faster algorithms. The following techniques can be applied to solve computational problems in general, and they often give rise to substantially faster algorithms: One example of a heuristic algorithm is a suboptimal O ( n log ⁡ n ) {\displaystyle O(n\log n)} greedy coloring algorithm used for graph coloring during

2006-400: The approximation ratio . The following very simple algorithm has an approximation ratio of 1/2: When this algorithm terminates, either all inputs are in the subset (which is obviously optimal), or there is an input that does not fit. The first such input is smaller than all previous inputs that are in the subset and the sum of inputs in the subset is more than T /2 otherwise the input also

2065-426: The register allocation phase of some compilers, a technique called graph-coloring global register allocation . Each vertex is a variable, edges are drawn between variables which are being used at the same time, and colors indicate the register assigned to each variable. Because most RISC machines have a fairly large number of general-purpose registers, even a heuristic approach is effective for this application. In

2124-461: The Boolean satisfiability problem, remains NP-complete, whereas the slightly more restricted 2-satisfiability problem is in P (specifically, it is NL-complete ), but the slightly more general max. 2-sat. problem is again NP-complete. Determining whether a graph can be colored with 2 colors is in P, but with 3 colors is NP-complete, even when restricted to planar graphs . Determining if a graph

2183-556: The HS algorithm is practical for up to about 50 integers, and the SS algorithm is practical for up to 100 integers. In 2010, Howgrave-Graham and Joux presented a probabilistic algorithm that runs faster than all previous ones - in time O ( 2 0.337 n ) {\displaystyle O(2^{0.337n})} using space O ( 2 0.256 n ) {\displaystyle O(2^{0.256n})} . It solves only

2242-453: The best known algorithms is exponential in the smaller of the two parameters n and L . The problem is NP-hard even when all input integers are positive (and the target-sum T is a part of the input). This can be proved by a direct reduction from 3SAT . It can also be proved by reduction from 3-dimensional matching (3DM): The following variants are also known to be NP-hard: The analogous counting problem #SSP, which asks to enumerate

2301-574: The decision problem, cannot prove there is no solution for a given sum, and does not return the subset sum closest to T . The techniques of Howgrave-Graham and Joux were subsequently extended bringing the time complexity to O ( 2 0.291 n ) {\displaystyle O(2^{0.291n})} . A more recent generalization lowered the time complexity to O ( 2 0.283 n ) {\displaystyle O(2^{0.283n})} . SSP can be solved in pseudo-polynomial time using dynamic programming . Suppose we have

2360-527: The definition of NP-complete changes is still an open problem. All currently known NP-complete problems are NP-complete under log space reductions. All currently known NP-complete problems remain NP-complete even under much weaker reductions such as A C 0 {\displaystyle AC_{0}} reductions and N C 0 {\displaystyle NC_{0}} reductions. Some NP-Complete problems such as SAT are known to be complete even under polylogarithmic time projections. It

2419-403: The definition of NP-complete given above, the term reduction was used in the technical meaning of a polynomial-time many-one reduction . Another type of reduction is polynomial-time Turing reduction . A problem X {\displaystyle \scriptstyle X} is polynomial-time Turing-reducible to a problem Y {\displaystyle \scriptstyle Y} if, given

NP-hardness - Misplaced Pages Continue

2478-454: The elements into 4 sets of n /4 elements each, and generate subsets of n /2 element pairs dynamically using a min heap , which yields the above time and space complexities since this can be done in O ( k 2 log ⁡ ( k ) ) {\displaystyle O(k^{2}\log(k))} and space O ( k ) {\displaystyle O(k)} given 4 lists of length k. Due to space requirements,

2537-448: The following sequence of elements in an instance: We define a state as a pair ( i , s ) of integers. This state represents the fact that Each state ( i , s ) has two next states: Starting from the initial state (0, 0), it is possible to use any graph search algorithm (e.g. BFS ) to search the state ( N , T ). If the state is found, then by backtracking we can find a subset with a sum of exactly T . The run-time of this algorithm

2596-510: The halting problem by transforming it to the description of a Turing machine that tries all truth value assignments and when it finds one that satisfies the formula it halts and otherwise it goes into an infinite loop. It is also easy to see that the halting problem is not in NP since all problems in NP are decidable in a finite number of operations, but the halting problem, in general, is undecidable . There are also NP-hard problems that are neither NP-complete nor Undecidable . For instance,

2655-477: The language of true quantified Boolean formulas is decidable in polynomial space , but not in non-deterministic polynomial time (unless NP = PSPACE ). NP-hard problems do not have to be elements of the complexity class NP. As NP plays a central role in computational complexity , it is used as the basis of several classes: NP-hard problems are often tackled with rules-based languages in areas including: Subset sum problem The subset sum problem (SSP)

2714-435: The list can be expanded to two sorted lists with the introduction of a ( k + 1 {\displaystyle k+1} )th element, and these two sorted lists can be merged in time O ( 2 k ) {\displaystyle O(2^{k})} . Thus, each list can be generated in sorted form in time O ( 2 n / 2 ) {\displaystyle O(2^{n/2})} . Given

2773-635: The number of subsets summing to the target, is #P-complete . There are several ways to solve SSP in time exponential in n . The most naïve algorithm would be to cycle through all subsets of n numbers and, for every one of them, check if the subset sums to the right number. The running time is of order O ( 2 n ⋅ n ) {\displaystyle O(2^{n}\cdot n)} , since there are 2 n {\displaystyle 2^{n}} subsets and, to check each subset, we need to sum at most n elements. The algorithm can be implemented by depth-first search of

2832-642: The numbers can be specified with at most P bits, then solving the problem approximately with ϵ = 2 − P {\displaystyle \epsilon =2^{-P}} is equivalent to solving it exactly. Then, the polynomial time algorithm for approximate subset sum becomes an exact algorithm with running time polynomial in n and 2 P {\displaystyle 2^{P}} (i.e., exponential in P ). Kellerer, Mansini, Pferschy and Speranza and Kellerer, Pferschy and Pisinger present other FPTASes for subset sum. NP-completeness In computational complexity theory ,

2891-436: The other. This is known as "the question of whether P=NP". Nobody has yet been able to determine conclusively whether NP-complete problems are in fact solvable in polynomial time, making this one of the great unsolved problems of mathematics . The Clay Mathematics Institute is offering a US$ 1 million reward ( Millennium Prize ) to anyone who has a formal proof that P=NP or that P≠NP. The existence of NP-complete problems

2950-479: The results of a poll he had conducted of the theoretical computer science community. Other suggestions made in the poll included " Herculean ", "formidable", Steiglitz 's "hard-boiled" in honor of Cook, and Shen Lin's acronym "PET", which stood for "probably exponential time", but depending on which way the P versus NP problem went, could stand for "provably exponential time" or "previously exponential time". The following misconceptions are frequent. Viewing

3009-412: The returned solution is at least OPT − ϵ T {\displaystyle {\text{OPT}}-\epsilon T} which is at least ( 1 − ϵ ) OPT {\displaystyle (1-\epsilon ){\text{OPT}}} . The above algorithm provides an exact solution to SSP in the case that the input numbers are small (and non-negative). If any sum of

SECTION 50

#1732787930234

3068-546: The run-time is polynomial in n / ϵ {\displaystyle n/\epsilon } . When the algorithm ends, if the optimal sum is in L , then it is returned and we are done. Otherwise, it must have been removed in a previous trimming step. Each trimming step introduces an additive error of at most ϵ T / n {\displaystyle \epsilon T/n} , so n steps together introduce an error of at most ϵ T {\displaystyle \epsilon T} . Therefore,

3127-429: The set of all decision problems whose solutions can be verified in polynomial time; NP may be equivalently defined as the set of decision problems that can be solved in polynomial time on a non-deterministic Turing machine . A problem p in NP is NP-complete if every other problem in NP can be transformed (or reduced) into p in polynomial time. It is not known whether every problem in NP can be quickly solved—this

3186-458: The solution set is non-empty and "no" if it is empty. The complexity class of problems of this form is called NP , an abbreviation for "nondeterministic polynomial time". A problem is said to be NP-hard if everything in NP can be transformed in polynomial time into it even though it may not be in NP. A problem is NP-complete if it is both in NP and NP-hard. The NP-complete problems represent the hardest problems in NP. If some NP-complete problem has

3245-405: The subroutine must be the return value of the program. If one defines the analogue to NP-complete with Turing reductions instead of many-one reductions, the resulting set of problems won't be smaller than NP-complete; it is an open question whether it will be any larger. Another type of reduction that is also often used to define NP-completeness is the logarithmic-space many-one reduction which

3304-851: The sum of the current element in the first array and the current element in the second array is more than T , the algorithm moves to the next element in the first array. If it is less than T , the algorithm moves to the next element in the second array. If two elements that sum to T are found, it stops. (The sub-problem for two elements sum is known as two-sum. ) In 1981, Schroeppel and Shamir presented an algorithm based on Horowitz and Sanhi, that requires similar runtime - O ( 2 n / 2 ⋅ ( n / 4 ) ) {\displaystyle O(2^{n/2}\cdot (n/4))} , much less space - O ( 2 n / 4 ) {\displaystyle O(2^{n/4})} . Rather than generating and storing all subsets of n /2 elements in advance, they partition

3363-430: The two sorted lists, the algorithm can check if an element of the first array and an element of the second array sum up to T in time O ( 2 n / 2 ) {\displaystyle O(2^{n/2})} . To do that, the algorithm passes through the first array in decreasing order (starting at the largest element) and the second array in increasing order (starting at the smallest element). Whenever

3422-567: The values of A and B , which are exponential in their numbers of bits. However, Subset Sum encoded in unary is in P, since then the size of the encoding is linear in B-A. Hence, Subset Sum is only weakly NP-Complete. For the case that each x i {\displaystyle x_{i}} is positive and bounded by a fixed constant C , in 1999, Pisinger found a linear time algorithm having time complexity O ( N C ) {\displaystyle O(NC)} (note that this

3481-422: Was a fierce debate between the computer scientists about whether NP-complete problems could be solved in polynomial time on a deterministic Turing machine . John Hopcroft brought everyone at the conference to a consensus that the question of whether NP-complete problems are solvable in polynomial time should be put off to be solved at some later date, since nobody had any formal proofs for their claims one way or

#233766