A problem in P can be solved in polynomial time - the computation required grows relatively slowly as the input size increases. Like sorting a list of numbers.
A problem in NP requires exponential time or greater, but a proposed solution can be verified quickly. For example, checking a completed Sudoku puzzle.
It is believed but unproven that all problems in NP are NOT in P.
Every single problem in P is in NP. What is believed but unproven is that some problems in NP are not in P.
I feel like I have not yet found the proper explanation. Or I'm just too dense to get it.
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.
- P means polynomial - NP means nondeterministic polynomial
Roughly polynomial (P) represents the upper bound of the cost to verify, and the polynomial characterization says that given a problem with a certain input (e.g. the input can be the number of training examples in ML training set or the number of constraints/conditions in a general problem— e.g. all the places you want to visit on your next trip, given many "wants" in a group)
When the cost is polynomial relative to the input size it means it can only be finitely larger than the input - that's a characteristic of the polynomial which is just a finite sum of powers of x (the input).
When the cost is nondeterministic polynomial, one way to think about it in what is called a nondeterministic Turing machine. The nondeterministic part refers to the "states" that the machines can transition to from any current state. When the transition can happen to more than one state, we say it's non-deterministic— and can imagine it's determined by some probability.
The general assumption is that polynomial (P) is easier than nondeterministic polnomial (NP). This isn't necessarily the case as there can be arbitrarily large finite numbers (making P solutions intractible)
The P vs NP problem is one of the main open problems and generally considered a crank magnet and general confusion. For a good (likely the best) resource see https://scottaaronson.blog/
This video explains in detail: https://www.youtube.com/watch?v=YX40hbAHx3s
In short, P means Polynomial time (i.e. markets can solve computation problems efficiently) and NP means Non-Deterministic Polynomial time (i.e. markets can verify solutions of computation problems efficiently but solutions are found by luck).
If P != NP, it means luck CANNOT be engineered and markets are competitive.
P complexity class
https://en.wikipedia.org/wiki/P_(complexity)
NP complexity class
https://en.wikipedia.org/wiki/NP_(complexity)
P vs NP question
one such class is the Polynomial class, or P, where the time to solution is some fixed exponent of N (like N^2, or 3).
the next big step is NP, which require a polynomial number of nondeterministic steps, whose solution can only be verified in polynomial time. usually solutions to NP problems are exponential in cost with respect to N (like 2^N), but thats not part of their definition.
problems in NP are generally identified by mapping them into a well known problem known to be in NP, where the mapping has to occur in polynomial time.
its an open question as to whether NP as a class can actually be solved in P time, but most people doubt that that is really the case.