NP problem
In computational complexity theory, NP (Nondeterministic Polynomial Time) is a kind of complexity class used to classify the deterministic problems. A set of deterministic problems whose answers are “yes” can be verified by deterministic Turing machines in polynomial time is called NP.
The equivalent definition of NP is a set of deterministic problems that can be solved by nondeterministic Turing machines in polynomial time. This definition is the basis of the abbreviation NP; “Uncertain polynomial time.” The two definitions are equivalent because algorithms based on Turing machines consist of two stages, the first of which consists of guessing about a solution, which is generated in a nondeterministic manner, while the second consists of deterministic algorithms, which verify that guessing can solve the problem.
Divergent understanding of NP problems
P problem: a problem that can be solved in polynomial time
NP problems: Nondeterministic Turing machines can solve problems in polynomial time
Np-complete problems: Can completely simulate the complexity class (that is, all NP) problems, NP-complete problems are both NP problems and NP hard problems.
NP hard problems: 1) NP complete problems. 2) More difficult than NP-complete problems
NP problems are interrelated
Resources: [1] zhuanlan.zhihu.com/p/73953567 [2] en.wikipedia.org/wiki/NP_ (co…