More explanation about NP, NP-Hard and NPC# EE - 电子工程
r*r
1 楼
NP is the set of problems which can be verified in poly-time, and P is a subset
of NP, and whether it's a proper subset or not is currently the biggest open
problem in computer science.
An example of non-NP was given in my previous posts, like the famous
halting problem {: program will never terminate} does not belong to
NP, coz you cannot verify a solution in poly-time.
NP-hard is the basically the problems "harder than"(at least as hard as)
NP problems. In scicentific defition, if a p
of NP, and whether it's a proper subset or not is currently the biggest open
problem in computer science.
An example of non-NP was given in my previous posts, like the famous
halting problem {
NP, coz you cannot verify a solution in poly-time.
NP-hard is the basically the problems "harder than"(at least as hard as)
NP problems. In scicentific defition, if a p