What is a list of NP problems

NP-complete problems

Problem reduction

The process of problem reduction plays a decisive role in classifying problems in complexity classes. We will first clarify it with the example and consider the Hamilton problem and the traveling salesman problem (in a decision variant).

The Hamilton problem gives an (undirected and unweighted) graph with its nodes and edges. It has to be decided whether there is a Hamilton cycle - i.e. a round trip through the graph in which each node occurs exactly once - only start and destination nodes appear exactly twice.

In the traveling salesman problem, there is an (undirected and weighted) graph with its nodes and weighted edges as well as a weight limit. It has to be decided whether there is a round trip through the graph (in which each node occurs exactly once - only start and destination nodes appear exactly twice) so that the sum of the weights along the round trip is less than or equal to the weight limit.

The Hamilton problem can be reduced (reduced) to the problem of the traveling salesman. To do this, every concrete Hamilton problem is converted into a corresponding traveling salesman problem. The following example is intended to illustrate the conversion.

Hamilton problem: is there a Hamilton cycle in graph?

A weighted graph is now constructed for the unweighted graph by adopting the nodes and edges of G, weighting the edges of G with the weight 1 and adding all possible edges between nodes of G and weighting them with the weight 2.

Problem of the traveling salesman: Is there a round trip in Graph, the total weight of which is less than or equal to the number of nodes in the graph?

Note that the graph is constructed in such a way that a Hamilton circle in a round trip corresponds to with the total weight.

An algorithm for solving the Hamilton problem can now be constructed directly from an algorithm for solving the traveling salesman's problem.

We assume that there is an algorithm that processes a weighted graph and a weight limit and decides whether there is the desired round trip:

ALGORITHM exists round trip traveling salesman Transfer: weighted graph, weight limit # ... Return: True / False

From this we develop an algorithm to solve the Hamilton problem:

For the graph given above, the result gives, because gives the result.

The following figure illustrates the principle of problem-solving through problem reduction.

Polynomial problem reduction

With a polynomial problem reduction, the effort to convert the problem (and to convert the solution) must be polynomial.

We write when the problem is polynomially reducible to the problem.

Example: The Hamilton problem can be polynomially reducible to the traveling salesman problem. The problem reduction shown above obviously has the required property that the problem and solution conversion can be done with polynomial effort. By the way: You can also show the other way around that the traveling salesman problem can be polynomially reducible to the Hamilton problem.

Polynomial problem reductions are used for complexity arguments. The following statement should be shown.

p ≤ p 'and p' ∈ P ⇒ p ∈ P

In words: if the problem is polynomially reducible and if one has polynomial complexity, then the problem also has polynomial complexity.

The argument goes as follows: From an algorithm with polynomial complexity for solving the problem, an algorithm with polynomial complexity can be generated for solving the problem. You just have to combine the algorithm with the conversion algorithms (as in the example above). In the argumentation one also uses that the successive execution of algorithms with polynomial complexity leads to an algorithm with polynomial complexity.

NP-complete problems

A problem is called NP-complete if and only if it lies in the complexity class (i.e. can be solved with a nondeterministic algorithm with polynomial complexity) and if every problem can be reduced to polynomial.

NP-complete problems play a central role in clarifying the question. If it is possible to solve an NP-complete problem with an algorithm with polynomial complexity, then the statement is proven. Because NP-completeness means that every problem can be reduced to polynomial. A polynomial algorithm for each can then be generated from a polynomial algorithm for.

To clarify the question, one concentrates on solving NP-complete problems.

There are now a large number of problems that have been proven to be NP-complete. These problems also include the Hamilton problem and the traveling salesman problem.

All attempts to solve an NP-complete problem with a polynomial algorithm have so far failed. The NP-complete problems thus turn out to be and are considered to be problems that are difficult to solve.

Because of the many unsuccessful attempts to find a polynomial solution algorithm for an NP-complete problem, one suspects that the question has to be answered negatively.