We're learning Complexity in our CS class and one of the topics is NP and P complexity. I know that NP stands for Non-deterministic Polynomial time and P stands for Polynomial time. Now I'm trying to grasp what these mean.
What does "Non-deterministic Polynomial" mean? I'm pretty sure that it relates to the run-time of a problem but I'm not a 100% sure. I've reads Wikipedia articles and some other blogs but they're explanation is at a higher level than what we did, so if the answer can be "dumbed down" a little bit.
Dumbed down version: If you have both a problem and a solution and you can check if the solution is right in polynomial time, it's in NP. If you have only a problem and you can find the right solution in polynomial time, it's in P. P is a subset of NP.
If you really want to understand what it means, you need some basics in automata theory and find out what deterministic and non-deterministic Turing machines are. That's not a thing someone can really dumb down for you easily.