SU-CS254 JAN292025
Last edited: August 8, 2025Key Sequence
Notation
New Concepts
Important Results / Claims
Questions
Interesting Factoids
SU-CS254 MAR032025
Last edited: August 8, 2025Today: let’s smash and together. Recall:
Recall:
\(x \in L \implies \exists y, V\qty(x,y) = 1\), \(x \not \in L \implies \forall y V\qty(x,y) = 0\)
\(x \in L \implies \text{Pr}\qty [V\qty(x,r) = 1] \geq \frac{2}{3}, x \not\in L \implies \text{Pr}\qty [V\qty(x,r) = 0] \geq \frac{2}{3}\)
Consider a new quantifier:
SU-CS254B APR022025
Last edited: August 8, 2025SU-CS254B APR072025
Last edited: August 8, 2025Recall the relationship between time and space; in particular:
\begin{equation} \text{TIME}\qty(t\qty(n)) \subseteq \text{SPACE}\qty(t\qty(n)) \end{equation}
“space is more valuable than time.”
On time vs. space
\begin{equation} \text{TIME}\qty(\qty(n)) \subseteq \text{SPACE} \qty( \frac{t\qty(n)}{\log \qty(t\qty(n))}) \end{equation}
\begin{equation} \text{TIME}\qty(\qty(n)) \subseteq \text{SPACE}\qty(t\qty(n)) \end{equation}
that is: space is strictly more valuable than time. Oh, and also:
\begin{equation} \text{TIME}\qty(t\qty(n)) \subseteq \text{SPACE}\qty(\sqrt{t\qty(n) \log t\qty(n)}) \end{equation}
Key idea: let’s transform the previous thing into a graph problem!
Suppose \(M\) is the time \(T\) truing machine, and consider its configure at time \(t < T\). Key idea: we can tradeoff time for space! notably, we will solve the same problem using a different algorithm, not modify the original machine.