Complexity Classes
The Computational Zoo is far more subtle and complex than I thought it was.
It contains P, NP (+complete), EXP, NP-hard, CO-NP (+complete), PSPACE, BPP, BQP, EXPSPACE, 2-EXP, halting problem, decidable, etc!
Big Oh Notation
TODO
NP-Hard and NP-Complete
If \(P=NP\), then the world would be a profoundly different place than we usually assume it to be. There would be no special value in 'creative leaps', no fundamental gap between solving a problem and recognising the solution once it's found. Everyone that could appreciate a symphony would be Mozart, everyone who could follow a step-by-step argument would be Gauss"-Scott Aaronson