Introduction to the
When we do combinatorial optimization, we need to solve various problems, which can be divided into P, NP, NPC and so on according to the complexity of the problems. Today I’m going to introduce you to these types of questions.
P problem
In computational complexity theory, P (also known as PTIME or DTIME) is the basic complexity type. It refers to all decision problems that can be solved in polynomial time using a deterministic Turing machine.
Here we give the definition of P, if a formula language L is of type P, then this is true if and only if there exists such a definite Turing machine M:
- For all inputs, M will run in polynomial time
- For all x’s in L, the output of M is 1
- For all x that is not in L, the M output is 0
Common P problems include decision versions of linear programming, computing the greatest common factor and finding the greatest match. In 2002, it was shown that the problem of determining whether a number is prime is also a P problem.
NP problem
In computational complexity theory, NP (Nondeterministic Polynomial Time) is mainly used to measure the complexity of classification decision problems. NP is a set of decision problems for which an answer of “yes” means that the instance can be validated successfully in polynomial time using a deterministic Turing machine.
NP is actually composed of two stages, the first stage consists of guessing the solution, which is generated in a non-deterministic way, and the second stage consists of deterministic algorithms, verifying whether guesses can solve the problem. NP= Nondeterministic + Polynomial.
According to the definitions of P and NP, we can find that all P problems are NP problems, because the definition of P is that all problems can be solved deterministically in polynomial time, while the definition of NP is that problems can be verified in polynomial time.
But NP contains more problems, and the most difficult problem in NP is called an NP-complete problem. An algorithm that solves such a problem in polynomial time can also solve any other NP problem in polynomial time.
Examples of NP problems
In computer science, many search optimization problems can be regarded as NP problems. The traveling salesman problem is a typical NP problem.
“Given a list of cities and the distance between each pair of cities, find the shortest path to visit each city once and return to the original city” is an NP problem in combinatorial optimization, which is important in theoretical computer science and operations research.
Some NP problems are difficult to solve
Because NP problem contains many very important problems in real life, people have paid great efforts to find polynomial time algorithm in NP. However, there are still many problems in NP that do not seem to be solvable in polynomial time. The question of whether these problems can be solved in polynomial time is one of the biggest unsolved questions in computer science.
An important concept introduced in this case is the NP-complete problem set (NP-complete), a subset of NP that can be informally described as the “hardest” problem in NP. If we say that a problem turns out to be an NPC problem, it means that there is no polynomial time algorithm to be found for the problem.
However, in practical applications, it is usually not necessary to spend a lot of computation to find an optimal solution, but a suboptimal solution can be found in polynomial time, which is sufficient for practical applications.
NPC problem
In computational complexity theory, a problem that satisfies the following conditions is an NPC problem:
- An uncertain Turing machine can be solved in polynomial time.
- A deterministic Turing machine can be solved in a large time complexity (EXPTIME or force search algorithm), and its solution can be verified in polynomial time.
- It can be used to simulate any other problem with similar solvable properties (other problems in NP can be transformed or reduced to this problem in polynomial time).
According to rule 3, since NPC problems are more complex forms of NP problems, if you can find a polynomial algorithm to solve some NP-complete problem, then all NP problems will be easily solved.
For example, a linear equation of one variable can be reduced to a quadratic equation of one variable, by changing the quadratic coefficient to 0. By continuous specification, we can obtain algorithms with higher complexity but wider application scope to replace algorithms with lower complexity but narrower application scope.
While it is possible to “quickly” verify a solution to the NPC problem, there is no known way to quickly find a solution. That is, as the size of the problem grows, the time required to solve the problem using any currently known algorithm increases rapidly.
No method for computing solutions to NP-complete problems has yet been discovered, but computer scientists and programmers still frequently encounter NP-complete problems. NP complete problems are usually solved by using heuristic methods and approximate algorithms.
NP-hard
In computational complexity theory, NP-hard is a description of a class of problems that are “at least as difficult as the most difficult problems in NP”. A simple example of the NP-hard problem is the subset sum problem.
If a known NPC problem can be traced to this problem, it is called an NP-hard problem.
So NPC problems must be NP-hard problems, but not all NP-hard problems are NPC problems.
P and NP problems
P and NP problems are the main unsolved problems in computer science. It talks about if a problem can be tested quickly, can it be solved quickly?
P means that a solution to the problem can be found in polynomial time, and NP means that a quick verification can be performed if a candidate answer is found.
In general, everyone tasks P! = NP, which means that although it cannot be solved in polynomial time, the answer can be verified in polynomial time.
According to whether P and NP are the same, we make the relation graph of P, NP, NPC and NP-hard respectively.
This article has been included in http://www.flydean.com/04-p-np-npc-problem/
The most popular interpretation, the most profound dry goods, the most concise tutorial, many you do not know the tips to wait for you to discover!
Welcome to pay attention to my public number: “procedures those things”, understand technology, more understand you!