Shulou(Shulou.com)06/03 Report--

This article mainly introduces "what are the problems of P, NP and NPC". In daily operation, I believe many people have doubts about what the problems of P, NP and NPC are. The editor consulted all kinds of materials and sorted out simple and easy-to-use methods of operation. I hope it will be helpful to answer the questions of "what are the problems of P, NP and NPC?" Next, please follow the editor to study!

P problem

In computational complexity theory, P (also known as PTIME or DTIME) is the basic type of complexity. It refers to all the 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 a P type, then it is true if and only if there is such a definite Turing machine M:

For all inputs, M runs in polynomial time

For all x in L, the output of M is 1

The output of all xrem M that is not in L is 0

Common P problems include the decision version of linear programming, calculating the maximum common factor and finding the maximum match. In 2002, it was proved that the problem of determining whether a number is a prime number is also a P problem.

NP problem

In the computational complexity theory, NP (nondeterministic polynomial time) uncertainty polynomial time is mainly used to measure the complexity of classification decision problems. NP is a set of decision questions, and for these examples, if the answer is "yes", then the instance can be verified successfully in polynomial time using a deterministic Turing machine.

NP actually consists of two phases, the first stage includes guessing about the solution, which is generated in a non-deterministic manner, and the second stage includes deterministic algorithms to verify whether guessing can solve the problem. In other words, 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 in polynomial time, while the definition of NP is that the problem can be verified in polynomial time.

But NP contains more problems, among which the most difficult problem in NP is called NP-complete problem. The algorithm for solving this kind of problem in polynomial time can also solve any other NP problem in polynomial time.

An example of NP problem

In computer science, many search optimization problems can be regarded as NP problems. The traveling Salesman problem is a typical NP problem.

"give a list of cities and the distance between each pair of cities, and find the shortest way to visit each city once and return to the original city." this is a NP problem in combinatorial optimization, which is very important in theoretical computer science and operational research.

Some NP problems are difficult to solve

Because the NP problem contains many important problems in real life, people have made great efforts to find the polynomial time algorithm in NP. However, there are still many problems in NP, which can not be solved in polynomial time. Whether these problems can be solved in polynomial time is one of the biggest unsolved problems in computer science.

In this case, an important concept is introduced, which is the NP complete decision problem set (NP-complete), which is a subset of NP and can be informally described as the "most difficult" problem in NP. If we say that a problem is proved to be a NPC problem, it means that we cannot find a polynomial time algorithm for this problem.

However, in practical applications, it usually does not take a lot of calculation to find an optimal solution, but a suboptimal solution can be found in polynomial time, which is enough for practical applications.

NPC problem

In the computational complexity theory, the problem that satisfies the following conditions is the NPC problem:

An uncertain Turing machine can be solved in polynomial time.

The deterministic Turing machine can be solved in large time complexity (EXPTIME or brute force search algorithm), and its solution can be verified in polynomial time.

It can be used to simulate any other problem with similar solvability (other problems in NP can be converted or reduced to this problem in polynomial time).

According to Rule 3, because the NPC problem is a more complex form of the NP problem, if you can find a polynomial algorithm to solve a NP-complete problem, then all NP problems can be easily solved.

For example, a univariate quadratic equation can be reduced to a univariate quadratic equation by changing the quadratic coefficient to 0. Through continuous specification, we can get algorithms with higher complexity but wider application range to replace the algorithms for a class of problems with low complexity but small scope of application.

Although the solution to the NPC problem can be verified "quickly", there is no known way to find the solution quickly. That is, as the size of the problem grows, the time required to solve the problem using any currently known algorithm increases rapidly.

No solution to the NP complete problem has been found yet, but computer scientists and programmers still often encounter NP complete problems. The complete problem of NP is usually solved by using heuristic methods and approximate algorithms.

NP-hard

In the theory of computational complexity, NP-hard is a description of a class of problems, which are "at least as difficult as the most difficult problems in NP". A simple example of a NP-hard problem is a subset and a problem.

If a known NPC problem can be reduced to this problem, then the problem is called the NP-hard problem.

So the NPC problem must be a NP-Hard problem, but not all NP-Hard problems are NPC problems.

P and NP problem

P and NP problems are the main unsolved problems in computer science. It talks about whether a problem can be solved quickly if it can be verified quickly.

P means that the solution to the problem can be found in polynomial time, while NP means that if a candidate answer is found, it can be verified quickly.

Under normal circumstances, everyone's task is P! = NP, that is, 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 diagrams of P, NP, NPC and NP-Hard, respectively.

At this point, the study of "what are the problems of P, NP and NPC" is over. I hope to be able to solve your doubts. The collocation of theory and practice can better help you learn, go and try it! If you want to continue to learn more related knowledge, please continue to follow the website, the editor will continue to work hard to bring you more practical articles!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.