we can use P vs NP to generalise different categories of algorithms to understand how feasible they are to solve for a given problem
two key ways to look at the difficulty of the problem:
we can classify problems as either solvable in polynomial time (P) or non-polynomial time (NP)
problems that are ‘hard’ to solve often take ridiculous amount of time to solve
usually with time complexities of O(n!) or O(k^n) or O(n^n) (factorial or exponential problems)
basically unsolvable for large datasets — a computer would take billions of years to solve
algorithms required to solve ‘hard’ problems are a non-deterministic polynomial time problem
could only be solved in a reasonable amount of time by a computer that can either simulate many/all possibilities at the same time, or guess the correct answer perfectly immediately
P = polynomial
can be solved in polynomial time; can be verified in polynomial time
e.g.
O(1), O(log n), O(n), O(n^2), O(n^10), O(sqrt(n))
e.g.
BFS, binary search
NP = non-deterministic polynomial
can be solved in non-deterministic polynomial time; can be verified in polynomial time