What is NP problem, what is the NPC problem? First explain the difference between the complexity of the problem and the complexity of the algorithm, the following is considered Time complexity. The complexity of the algorithm refers to the implementation of a specific algorithm for solving the problem.
This is the nature of the algorithm; the complexity of the problem refers to the complexity of this problem itself, is the nature of the problem. For example, for sorting problems, if we can only compare each other through elements
To determine the mutual position between the elements, without other additional available information, the complexity of the sorting problem is O (NLGN), but there are many sorting algorithms, and the bubbling method is O (n ^ 2), rapid ordering
In all cases, the complexity of the sorting problem is the complexity of the algorithm in all the algorithms to solve this problem. The complexity of the problem is impossible to enumerate various possible algorithms
It is generally estimated a value in advance and then theoretically proves. In order to study the complexity of the problem, we must abstain problems, in order to simplify the problem, we only consider a simple problem, judgment, that is, a problem, only need
A question of YES or NO. Any general optimization problem can be converted to a series of judgment issues, such as the shortest path from A to B, can be converted to:
Is the path to 1? Is there a path from A to B having a length of 2? . . . Is there a path from A to B? If you have answered Yes when you ask K, you can stop ask, we can say
The shortest path of A to B is k. If a complexity of a judgment problem is a multi-item function of the size N of the problem, we say that this deterministic problem that can be solved in a polynomial time belongs to P.
Class issue. The P class problem is a collection of all complexity of polynomial time. However, some problems have difficulty finding the algorithm of the polynomial time (perhaps not existed at all), such as finding the Hamilton loop problem in the unidirectional picture, but we find that if you give us
An answer to the question, we can judge whether this answer is correct during the polynomial time. For example, for the Hamilton loop problem, give an arbitrary loop, we are easy to judge him.
Is it a Hamilton circuit (just see if all the vertices can be in the loop). This problem that can be verified in a polynomial time is called NP issues. Show
However, all P-class issues are NP issues, but now the problem is whether P is equal to NP? This issue has not been resolved. Note that NP issues are not necessarily a problem, such as
Simple array sorting problem is a P-class problem, but P belongs to NP, so it is also an NP problem, can you say that he is hard to solve?
Just said, now I don't know if there is P = NP or P <> NP, but later people find there a series of special NP issues, the special nature of this problem makes many people believe that P <> np, only
But now I can't prove it. Such special NP issues are NP full problems (NPC issues, C represents "Complete). There is an amazing nature in the NPC problem, that is, if an NPC
There is a multi-term time algorithm, and all NP issues can be solved within a polynomial time, that is, P = NP is established! ! This is because each NPC problem can be transformed within a polynomial time.
Any NP problem. For example, the Hamilton loop question saying earlier is an NPC issue. The history of NPC issues not long ago, Cook found the first NPC issue in 1971, after which
There are also many NPC issues, and now there may already have more than 3,000. Therefore, we generally think that NPC issues are difficult to solve, because he is unlikely to have a multi-purpose time.
Law (if there is a polynomial time algorithm, it is incredible if all NP issues are present, which is too incredible, but it is not impossible). Similar to Hamilton loop / path problems, goods, group issues, minimum side coverage (attention and path coverage), and so on are NPC issues, so they are difficult to solve.
