Streaming Algorithms, Communication Complexity

turing machine

get hyped: turing machine

• Church-Turing thesis
• decidable predicate and predicate recognizability
• universal turing machine
• there are non-recognizable languages
• L is decidable IFF L and not L are both recognizable
• Mapping Reduction
  • halting problem
• computable function

Rice’s Theorem, Oracle Reduction, Self-Reference and the Recursion Theorem

mathematics

Time Complexity + Non-deterministic Turing Machines

P vs. NP, polynomial time mapping reduction

NP-Complete, Cook-Levin Theorem, and coNP

owo a chart!

Properties of NP Completeness

for \(NP\) complete \(A\), \(B\), is \(A\ \text{op}\ B\) np complete?

Properties of P and NP

for \(P\) or \(NP\) \(A\), \(B\), is \(A\ \text{op}\ B\) np complete?