SU-CS254 FEB262025
Last edited: August 8, 2025We are here to prove a theorem.
The number of satisfying assignments is a problem solvable in IP(k).
Consider some 3SAT formula:
\begin{equation} \phi\qty(x) = \qty(x_1 \vee x_3 \vee \neg x_9) \wedge \qty(\neg x_2 \vee \neg x_5 \vee x_{50}) \wedge \dots \end{equation}
where \(\phi\qty(x)\) has exactly \(k\) satisfying assignments. This expression has \(n\) variables and \(m\) clauses. Notice that: \(x_1 \vee x_3 \vee \neg x_{9}\) if and only if \(x_1 = 0, x_3 = 0, x_{9} = 1\). This has the following properties:
SU-CS254 JAN062025
Last edited: August 8, 2025SU-CS254 JAN082025
Last edited: August 8, 2025Notation
New Concepts
Important Results / Claims
- Turing Machine as a universal algorithm
- properties of turing machines
- Church-Turing thesis as local steps
- time hierarchy theorem
Why stuff is great
Questions
Scratch
Let \(L \in P\), and \(M\) be the polytime TM that decides \(L\). Define \(M’\) to be \(M\) with \(q_{\text{accept}}\) and \(q_{\text{reject}}\) swapped. Fact: \(M’\) decides \(\neg L\).
SU-CS254 JAN132025
Last edited: August 8, 2025Key Sequence
New Concepts
Important Results / Claims
- space complexity is tricky…
- “gold standard” for space complexity is \(O\qty(\log\qty(n))\)
- \(\text{TIME}\qty(t\qty(n)) \subseteq \text{SPACE}\qty(t\qty(n))\)
- \(\text{SPACE} \qty(s \qty(n)) \subseteq \text{TIME}\qty(2^{O\qty(s\qty(n))})\)
- space hierarchy theorem
- Space Time Hierachy