Notes - Computational Complexity HT25, Common proof themes

[[Notes - Computational Complexity HT25, Properties of languages]]^U
- Diagonal argument to show that there are undecidable languages in RE
- (Alternatively, this may be proved by noting that the set of decidable languages is countable but the set of recursively enumerable languages is uncountable; but most proofs that the set of recursively enumerable languages is uncountable relies on a diagonalisation argument).
[[Notes - Computational Complexity HT25, Hierarchy theorems]]^U
- Diagonal argument to prove the time and space hierarchy theorem

Shows that if some complexity classes are equal, then this result can be “powered up” to larger complexity classes
[[Notes - Computational Complexity HT25, Nondeterminism]]^U
- Proves $\mathsf P = \mathsf{NP}$ implies $\mathsf{EXP} = \mathsf{NEXP}$
From problem sheets / exams:
- If $\mathsf{DTIME}(T(n)) \subseteq \mathsf{DSPACE}(S(n))$, then $\mathsf{DTIME}(T(2^n)) \subseteq \mathsf{DSPACE}(S(2^n))$ (problem sheet)
- Show $\mathsf{DSPACE}(n) \ne \mathsf P$, does it follow $\mathsf{DSPACE}(n) \subsetneq P$, via contradicting the space hierarchy theorem (problem sheet)
- Every tally language in $\mathsf{NP}$ is in $\mathsf{P}$ iff $\mathsf{NE} = \mathsf{E}$ (problem sheet)
- $\mathsf{NSPACE}(n) \subsetneq \mathsf{NSPACE}(n^{1.1})$ using a padding argument and a deterministic space hierarchy theorem

[[Notes - Computational Complexity HT25, Cook-Levin theorem]]^U
- Shows $\mathsf{SAT}$ is $\mathsf{NP}$-complete by considering propositional formulas corresponding to potential accepting configurations
[[Notes - Computational Complexity HT25, Boolean circuits]]^U
- Proves that $\mathsf P \subseteq \mathsf P _ {/\mathsf{poly} }$ by converting every machine in $\mathsf P$ to a boolean circuit
[[Notes - Computational Complexity HT25, PSPACE-completeness]]^U
- Proves that $\mathsf{TQBF}$ is $\mathsf{PSPACE}$-hard by formalising the existence of an accepting tableau using a totally quantified Boolean formula

[[Notes - Computational Complexity HT25, Savitch’s theorem]]^U
- Proves that $\mathsf{NSPACE}(S) \subseteq \mathsf{DSPACE}(S^2)$ by recursively defining a $\mathbf{CanYield}$ subroutine
[[Notes - Computational Complexity HT25, Sublinear space classes]]^U
- Shows that $\mathsf{PATH}$ can be decided in depth $O((\log n)^2)$ by recursively defining a $\mathbf{Reach}$ subroutine (in an exam question)
[[Notes - Computational Complexity HT25, PSPACE-completeness]]^U
- Proves that $\mathsf{TQBF}$ is $\mathsf{PSPACE}$-hard by formalising the existence of an accepting tableau using a totally quantified Boolean formula, by recursively defining a set formulas that encode $\mathbf{Reach}$ in the configuration graph

[[Notes - Computational Complexity HT25, Randomness and probabilistic computation]]^U
- Shows that RP and BPP have very robust definitions in terms of their error using the Chernoff bound

From problem sheets:
- Proves that $\mathsf{PAL}$ cannot be decided in time $o(n^2)$ on a 1-tape TM (in a problem sheet)
- Proves that PAL is not in $\mathsf{NTISP}(n^{1.1}, n^{0.1})$