JewKiller 3000 posted:

you can ignore the mystical non-determinism stuff and think about it like this. a problem in P can be solved in polynomial time. a problem in NP can be checked in polynomial time, i.e. if i give you an already computed answer, you can check in polynomial time whether this answer is in fact correct.

so why does anyone think these classes are related? well basically computing is a young field so there was a ton of low hanging fruit, problems that seemed hard were solvable efficiently (in P) with simple strategies like greedy algorithms and memoization. for example dijkstra's shortest path algorithm, it's like the most obvious approach, an undergrad can prove it correct... you too could have an algorithm named after you if you had the foresight to be a computer science professor in the 1960s!

but there were still some problems where no known technique worked better in general than the brute-force strategy of enumerating all possible answers and checking each one. at first these problems were discovered independently, but researchers came to realize that they were all hard in the same fundamental way, and that any general polynomial time solution to one of them would work for all of them, so all of NP would be in P. that's what the NP-complete stuff is about

so there's a bunch of problems that a bunch of different smart people all thought they could solve efficiently, but none of them could do it, so it seems obvious that P != NP right? except nobody has been able to prove it, and they don't even really know how to go about attempting to prove it. math is hard