## DEV Community is a community of 862,249 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

# Discussion on: What is NP hardness?

## Replies for: I'll try. If somebody see a mistake (or a better way to explain that), please let a comment :) P are problems which can be solved in Polynomial ti...

Austin S. Hemmelgarn

Adding to this, an NP-hard problem is a problem that is known to be at least as difficult to solve as the most difficult to solve problems in the NP complexity class.

A good example of this is traveling salesman problem is a good example of such a problem, at least when what you care about is optimization of the route. Additionally, it also has an NP-complete version (given a length L, determine if a given graph has a tour that is no longer than L, known as the decision version of the traveling salesman problem).

Pacharapol Withayasakpunt • Edited on

I see. There is also NP completeness.

However, I am not sure what `non-deterministic` means. (Non-deterministic Turing Machine? -- found YouTube, but will take some time to watch.)

A common misconception is that the NP in "NP-hard" stands for "non-polynomial" when in fact it stands for "non-deterministic polynomial acceptable problems".[4] It is suspected that there are no polynomial-time algorithms for NP-hard problems, but that has not been proven.[5] Moreover, the class P, in which all problems can be solved in polynomial time, is contained in the NP class.[6]

So, how to prove something is NP complete? Or, even NP in the first place?