Finite Automata Deterministic Finite Automata, computability (in particular regular languages) and Non-deterministic Finite Automata (i.e. verified guessing) optimization and Learning DFA we were then able to characterize hardness with Streaming Algorithm and Communication Complexity Computability Theory turing machines, and Oracle Turing Machine, and things that are decidable vs. recognizable through mapping reductions, we are then able to make decidability and recognizablility claims for many languages we learned about the hierarchy of hard problems through the notion of SUPERHALT in Oracle Turing Machines We tied mathematics and computation together, and showed Godel’s Theorem about the Limitations of Mathematics We described the notion of information encoding though Kolomogorov Complexity Complexity Theory We described Time Complexity, P vs. NP, and NP-Completeness; nondeterminism came back fully. We then described SAT and 3SAT, which were NP-Complete We then using polynomial time mapping reduction to come up with many, many NP-Complete things, and saw a hierarchy of harder problems through the idea of Oracle Polynomial Time and NP^{NP^{{NP}^{\dots}}} Other Ideas if you assume you can’t factor (i.e. that factoring is super hard), for instance, you made a one-way function; this means… could get random instances in SAT which are hard zero-knowledge proofs, because you can check the factor but not do the factoring you could deterministically increase entropy: “randomness is weak”