I am struggling to understand what are nondeterministic polynomial-time problems and NP-complete problems. I understand what polynomial-time solvable problems are, and saw in Wikipedia about NP problems. After reading about this I tried to think about some example problems. As I understand it, depth-first search in an undirected is NP-complete, since each decisions can be made nondeterministically (i.e if I made the wrong decision, I could instead try some other choice) if the graph is large (cit an be polynomial if graph size is small.)
Can anyone briefly explain all these NP terms with simple examples without using much maths?