NP-complete

In computer science, we describe a problem to be NP -complete (complete for the class of problems that can not be deterministically solved in polynomial time ) if it is one of the most difficult problems in the NP class, so both is in NP, and NP- is difficult. This means colloquially that it probably can not be solved efficiently.

Formally, NP- completeness is only for decision problems defined (possible solutions only "yes" or "no") while speaking with other types of problems of NP- equivalence ( for example in search problems or optimization problems ). Colloquially, this distinction is often not carried out, so that you can more generally of "NP - complete problems " speaks, regardless of whether a decision problem or not. This is possible, since various types of problem can be converted into each other ( sequential reducible ) are.

A decision problem is NP- complete if it

  • In the complexity class NP is: A deterministic working computer needs only a polynomial amount of time to decide whether a proposed solution of an associated search problem is actually a solution and
  • Belongs to the NP- hard problems: All other problems whose solutions can be deterministically checked in polynomial time, can be attributed to the problem so that this feedback takes on a deterministic computer at most polynomial time. One speaks of a Polynomialzeitreduktion.

The class of all NP -complete problems is denoted by NP -C. The properties of these and other classes are explored in complexity theory, a branch of theoretical computer science.

An important property of NP-complete problems is that they probably can not be solved efficiently, so that takes its solution on real computers a long time. In practice, this property has no effect in each case is negative, that is, there is for many NP- complete problems solution procedures to ensure they are in an acceptable time solvable for orders of magnitude occur in practice.

Many emerging and important in practice problems are NP-complete, making NP- completeness to a central concept of computer science. This meaning is further amplified by the so-called P- NP problem:

Since the introduction of the NP- completeness by Cook completeness was developed into a general concept for any complexity classes.

History

The notion of NP- completeness was introduced in 1971 by Stephen A. Cook in his today so-called set of Cook. In it he showed that SAT is NP-complete, and thus there is a problem that meets the definition of NP-completeness. Today there are much simpler constructive proof for the existence of such problems, however, the languages ​​used for this purpose are very artificial. So Cook's merit is also to have proved this for a very interesting language.

Building on the work of Cook Richard Karp was able to present another groundbreaking work in 1972, which helped the theory of NP-completeness to even greater popularity. Karp's merit is to have used the technique of Polynomialzeitreduktion consistently to prove the NP- completeness for an additional 21 popular problems.

Definition

One problem (more precisely, a decision problem ) L is called NP-complete if and only if:

  • L is in the class NP, ie and
  • L is NP-hard, that is.

The latter condition means that any problem can be reduced in NP by a Polynomialzeitreduktion on L.

Proof of NP- completeness

The proof of the first property for a given problem is easy in most cases. Man " advises " a solution and shows that you can verify in polynomial time whether the solution is really true. The rates of the (correct) solution, the non-determinism is again.

The proof of the second property which is only referred to with NP-hard (or by wrong back-translation from English ' NP -hard ' with NP- hard), is more difficult. In particular, it presents problems to show a statement for any problems in NP. Therefore, usually one takes a similar problem, for which the NP- completeness is already known, and reduces it to the one problem for which the property of the NP-hardness is to be shown. From the transitivity of Polynomialzeitreduktionen then follows that all other problems are also NP reducible to the problem under consideration.

The above definition requires, strictly speaking, a proof of existence. It 's not immediately obvious that such problems exist at all. But it can be easy to construct such a problem. However, such a contrived problem is hardly relevant in practice. However, Cook was able to show that the satisfiability problem of propositional logic is NP-complete, and thus has provided evidence for a relevant practical problem. This evidence could, in contrast to other problems of course not be as shown above via the transitivity of Polynomialzeitreduktionen and had to be carried out directly.

NP- equivalence

NP- completeness is only defined for decision problems, ie, for such problems, which can be traced back to the word problem of a formal language, ie for which only either Yes or No is the answer of the question. For optimization problems and search problems, there is the name of NP- equivalence.

Approximation

Problems that are in NP, can be further subdivided in complexity, depending on how well they can be solved approximatively. The graph - coloring problem is for example only very poorly approximated, while other problems can be approximated using so-called approximation schemes any good.

Strong NP- completeness

An NP -complete problem ie strongly NP- complete if it will still be NP-complete if one is restricted to those input instances that contain only those numbers ( as a numerical parameter ), whose size is restricted polynomial with respect to the input length ( such a problem is always in NP again ). Or in other words: if you modified the problem is that all numeric parameters are in the input in Unärsystem, it remains NP -complete. For strongly NP- complete problems there, assuming NP not equal to P no pseudopolynomial algorithms. These are algorithms whose running time is polynomial if the size of all occurring in the input numbers is polynomially bounded in the input length.

An example of a problem for which there is a pseudopolynomieller algorithm, the knapsack problem. By algorithms based on the principle of dynamic programming can be a duration which is limited can be obtained. The computation time is thus polynomially if the number ( the limit for the maximum allowable value in use) in relation to the input length is only polynomially large. Such NP -complete problems, a pseudopolynomial algorithm, also called weakly NP-complete.

Swell

610323
de