DEV Community

Discussion on: What is NP hardness?

ahferroin7 profile image
Austin S. Hemmelgarn

Yes, the 'nondeterministic' in the name of NP refers to a nondeterministic Turing machine (NTM). Problems that are in NP can be solved in polynomial time on an NTM. This also includes problems in P, which are solvable in polynomial time on a deterministic Turing machine.

NP complete problems are, formally, problems in NP for which every other problem in NP is reducible to that problem in polynomial time. In other words, if an algorithm is found for solving an NP complete problem, you can use that algorithm to solve any other problem in NP by combining it with another algorithm that translates from the problem to be solved to the NP-complete problem (and probably make a very large amount of money by doing so, as many important optimization problems are in NP).