Computational Complexity HT25, Common proof themes

• Course - Computational Complexity HT25^U

Diagonalisation

• Notes - Computational Complexity HT25, Diagonalisation^U
• Notes - Computational Complexity HT25, Basic definitions^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

Padding arguments

• Shows that if one complexity class is a subset of another, then this result can be “powered up” to larger complexity classes
• Notes - Computational Complexity HT25, Non-deterministic Turing machines^U
• Notes - Computational Complexity HT25, Padding arguments^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

Tableaus / locality of computation

• 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, 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

Recursion / meet-in-the-middle / dynamic programming

• 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

Error reduction

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

Crossing sequences

• 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})$

Counting arguments

• Notes - Computational Complexity HT25, Circuits^U
  • Most functions require exponentially large circuits
  • There exists a Boolean function computable by circuits of size $n^{k+2}$ but not by circuits of size $n^k$
• Notes - Computational Complexity HT25, Crossing sequences^U
  • The crossing sequences need to be long enough so that you can distinguish $x0^m x^R$ from $x0^m y^R$.