I have never really understood this, from the time it was first introduced to me in my undergraduate education nearly 40 years ago. It seems to boil down to saying "all unsolvable problems are not in the set of solvable problems" which seems like a tautology. I don't get why "P != NP" is considered so profound.

I feel like I have not yet found the proper explanation. Or I'm just too dense to get it.

Not sure you're wanting an explanation, but it comes down more to equivalent algorithms than rigid categories. For example there is a P algo to sort a list of numbers, but not to solve a sudoku (NP). However there is a polynomial algo to check sudoku (spaces ^ 2 if you check every space against every other space for rule violation).

However, the reason all NP algos are part of the same category is because you can solve any problem in NP by switching the problem into another problem in the same category and solving that. For example, you can turn sudoku into a graph coloring problem, which is also NP. You can turn sorting (P) into something like balancing a tree, which is also P.

The major question is "is there any algorithm that would allow us to change some NP problems into P problems, solve it, then use it for the original problem". E.g. could we take graph coloring and turn it into sorting a list of numbers?

So basically, if there is any way to bridge the two, then it might mean every NP problem is actually solvable by a P algorithm, under some transformation. This would be immense because it would completely change the way we solve those algorithms and greatly reduce compute costs.

While this seems far-fetched, realize that there are some problems that seem extremely expensive if done the naiive way, but are actually solvable in P. For example, you _could_ write an exponential sorting algo (try every element in every position), but clever people found a way to make it efficient (P). So its possible we just need the right algo to completely change the landscape of computing.

However, as you say, its almost self-evidently true that P != NP, but has never been proven so (to do so, we need to prove that no such algorithm can exist). But clearly, solving an exponentially complex problem using a O(log n) algo would be remarkable.

To take a concrete example, currently the best algos to exhaustively check a board game like chess or go are exponential (NP). Its easy to verify the winner, but its exponential to enumerate every possible move (e.g. 80^turns states). If we found a polynomial way to solve this (even by converting to something simplified), then it would mean we could exhaustively search chess polynomial to the number of moves (e.g. turns^100). This changes it from "cannot be done in the lifespan of universe" to "its possible with a powerful computer in measurable time". We already use heuristics and estimates to explore the exponential space in efficient time, so if we had a polynomial algo chess, markets, optimization, and other NP problems would be extremely efficient to solve.