Preliminary knowledge

Polynomial time complexity and non-polynomial time

Time complexity

Time complexity is not a measure of how long it takes a program to solve a problem, but rather how fast the time it takes a program to solve a problem grows as the size of the problem increases.

That is, the efficiency with which a program handles a particular piece of data is not measured by how good the program is, but by whether it runs the same time, or hundreds of times slower, or tens of thousands of times slower when the data is hundreds of times larger.

No matter how big the data is, the program takes the same amount of time to process, so let’s say this program is good, O(1)O(1)O(1) time complexity, also known as constant complexity;

As the size of the data increases, so the time it takes to find the maximum number of n numbers is O(n)O(n)O(n), linear,

The time complexity of bubble sort, insert sort, etc. is O(n2)O(n^2)O(n2).

There are also exhaustive algorithms where the time required increases geometrically, and that’s the exponential complexity of O(an)O(a^n)O(an), or even O(n!). O(n!) O(n!) The factorial complexity of.

Polynomial time complexity

As O (1), O (ln ⁡ (n)), O (na) O (1), O (\ ln (n)), O (n ^ a) O (1), O (ln (n)), O (na) and so on, we call it the polynomial time complexity, because it is the size of the n in the position of the base;

Nonpolynomial degree of time

The other one is like O(an)O(a^n)O(an) and O(n!). O(n!) O(n!) And so on, it is a non-polynomial level of time complexity, its complexity computers are often unable to withstand.

When we are solving a problem, the algorithm we choose usually needs to be polynomial complexity. Non-polynomial complexity takes too much time and often times out, unless the data size is very small.

P problem vs. NP problem

P problem

Problems that can be solved in polynomial time.

For example, calculating the sum of consecutive integers from 1 to 1000: this problem is relatively simple, and can be done programmatically or using the Gauss summation formula in a finite acceptable time. It is a Class P problem.

NP problem

A complex problem in which the answer cannot be found in polynomial time, but can be verified in polynomial time. A problem that can be verified in polynomial time to produce a correct solution.

For example, counting the sum of all the atoms on earth: this problem is very difficult or even unsolvable, but now there is an answer of 300, which is obviously wrong, so it is easy to verify but not easy to solve, this kind of NP problem.

The relation between P problem and NP problem

If a problem is a P problem, then there is no doubt that we can verify it in polynomial time.

Class P is a class of problems that can be solved and verified in polynomial time, while class NP is a class of problems that can be verified in polynomial time but can not be solved in polynomial time.


P ⊆ N P P \subseteq NP

NP -complete (NPC)

This problem needs to satisfy two conditions:

  • It’s an NP problem
  • All other NP problems can be reduced to it

In other words, once this problem is solved, then all NP problems are solved.

Reducibility: is to transform a problem into another problem, so that the solution of the second problem to solve the first problem the first problem. This idea is similar to that in mathematical proof, if a proof is difficult to start from the original proposition, then according to the original proposition and its negation proposition are equivalent, the original proposition is converted into negation proposition to solve, and the extremely simple solution or the entry point of the conclusion will be obtained. For example, if you want to find your way in a city, if you have a map, you reduce the problem of finding your way to the map problem.

At the same time, reduction has another important property: transitivity. That is, if problem A is reducible to problem B, and problem B is reducible to problem C, then problem A must be reducible to problem C.

NP – Hard problem

It satisfies the second part of the NPC problem definition but does not have to satisfy the first. All NP problems can be reduced to it, but it is not necessarily an NP problem.

The NP-hard problem is also difficult to find an algorithm for polynomials, but it is not included in our study because it is not necessarily an NP problem. Even if NPC problems find polynomial-level algorithms, nP-hard problems may still fail to produce polynomial-level algorithms.

In fact, since NP-Hard has relaxed the constraints, it is likely to be more time complex and harder to solve than all NPC problems.

A typical example of NPC vs. NP-hard – the traveling salesman problem

Traveling Salesman Problem (TSP) is a commodity Salesman who has to sell goods in several cities. The Salesman starts from one city and needs to go through all cities before returning to the starting point.

There are two versions of the travel salesman problem:

  1. In a graph, what is the shortest path of a closed loop that traverses all nodes but the starting point repeatedly? (How to choose the route to make the total journey shortest) — this is the optimal solution problem

  2. In a graph, a closed loop is formed by traversing all nodes except the starting point repeatedly. Is there a loop whose path length is less than or equal to a certain value? How should the route be chosen so that the total distance traveled is less than or equal to a certain value

For problem 1, there is no way to make a deterministic Turing machine verify the answer in polynomial time, so problem 1 is not NP problem, and therefore not NPC problem, but Hamilton loop problem can be reduced to TSP problem, and Hamilton loop problem is NP problem, so it is NP-hard problem.

For problem 2, a deterministic Turing machine can be made to verify the answer in polynomial time, so problem 2 is NP problem, and Hamilton loop problem can be reduced to TSP problem, and Hamilton loop problem is NP problem, so problem 2 is NP-hard problem, and it is also NPC problem.

The connection between the four

The four kinds of problems are represented as sets, and their relationship diagram is shown below.

Description:

  1. P problems are NP problems, NPC problems are NP problems.
  2. NPC problem belongs to NP hard problem at the same time, which is the intersection of NP and NP hard.

PS: No one has yet come up with a proof that the NPC problem can be solved in polynomial time, making it a well-known unsolved problem in mathematics. The Clay Mathematics Institute (CMI) in Cambridge is offering a $1m prize to anyone who can prove that P=NP or P≠NP.

conclusion

Having said all that, I personally think the reason why we should judge what kind of problem a problem is is that it helps us to make an effective judgment of the difficulty of the problem before committing to such a problem. If a problem is NP hard, it is well known that we may not be able to find the optimal solution, sometimes hold the suboptimal solution (in fact, since it is an engineering problem, we are better to use a much smaller cost to seek the suboptimal solution than to search for the optimal solution). If a problem is not even NP, which means I have trouble verifying it in polynomial time, how can I solve it? There is little need to study such questions.