we can use P vs NP to generalise different categories of algorithms to understand how feasible they are to solve for a given problem

solving vs verifying

two key ways to look at the difficulty of the problem:

• solving = how hard is it to find or guess the correct answer?
• verifying = given a solution, how hard is it to verify that it is correct?

we can classify problems as either solvable in polynomial time (P) or non-polynomial time (NP)

‘hard’ problems

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 vs NP vs NP-Complete

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