Suggest edit — CS154 Final Summary

Title

Name

Note

---
title: "CS154 Final Summary"
type: concept
related: [Turing Machinea, Deterministic Finite Automata, Streaming Algorithms, Computability, Np Complete]
source: https://www.jemoka.com/posts/kbhcs154_final_ummary/
confidence: high
status: active
---

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&rsquo;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&rsquo;t factor (i.e. that factoring is super hard), for instance, you made a one-way function; this means&hellip; 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: &ldquo;randomness is weak&rdquo;