As you likely noticed, bubble sort is not a particularly efficient way of ordering something. Still, it gets the job done faster than laying out all the possible combinations of numbers until you find the one that happens to be in the right order. As a result, it counts as "easy," despite its relative inefficiency. In a massively over-simplistic sense, you can think of P problems as anything for which we have a better approach than trial-and-error for solving them.
On the other hand, some problems are more challenging for computers to solve: cryptographic techniques like finding prime factors, playing games like sudoku, solving math/logic questions like the traveling salesman problem, and even finding the right configuration of packing boxes in your trunk, are all "hard" in CS terms. In other words, we don't have an efficient algorithm to solve them. In the case of sudoku, while it might be easy to do the puzzle in your Sunday paper, imagine trying to solve a billion square grid. The good news is that no matter how many years or lifetimes it took to complete the puzzle, once you were done, checking it was all correct would be nearly effortless for your computer. Sudoku and the like are "NP" problems, which annoyingly doesn't mean "not polynomial," and instead stands for non-deterministic polynomial time. What unites these problems is that no computer we have ever built can solve them in polynomial time. In fact, many of them take an exponential amount of time to figure out—so instead of n^2 (polynomial) time, they might take 2^n (exponential) time, which, if you remember back to high school math, means they can get big fast. However, as in the sudoku example, once any NP problem is solved, checking it's correct is a breeze.
The debate of P vs. NP, which may sound ridiculous, is whether the two classes are actually different. Are NP problems just P problems for which we haven't discovered a better algorithm? While almost every mathematician and computer scientist believes the P≠NP, they haven't been able to prove that there's something fundamentally different about the problem posed by sudoku versus sorting a list of letters alphabetically. On the one hand, as I said earlier, this is crazy. If there turned out to indeed be no difference between these classes of problems, many of the unsolved math problems in the world would disappear. There's actually a whole class of problems called NP-complete that, if any one of them were solved, would unlock all the others.
If P were equal to NP, there would still be unanswered questions in the universe, but in mathematics, at least, we'd be able to point powerful computers at many of them, and they'd fall away. This seems so obviously impossible that it's kind of amazing to imagine some of the smartest people on our planet being willing to entertain it. But I guess that's what you do if you're a theoretical computer scientist. Or if you just need an escape from the news. (NRB)
https://whyisthisinteresting.substack.com/p/the-p-vs-np-edition