Computational Complexity HT25, Problem sheets

Created: April 30, 2025 | Updated: May 19, 2025 | About these notes

  • [[Problem Sheet - Computational Complexity HT25, I]]?
    1. Count is a computable function if the language is decidable
    2. Decidability has a witness characterisation like $\mathsf{NP}$
    3. Is $\mathsf{INTERSECT}$ or $\mathsf{FINITE}$ r.e.-complete?
    4. Is the language of all strings containing $2^n$ ones in $\mathsf{DTIME}$.
    5. $\mathsf{PAL}$ cannot be decided in time $o(n^2)$ on a 1-tape TM. ⭐️
    6. A language is regular iff $L \in \mathsf{DSPACE}(O(1))$ ⭐️
  • [[Problem Sheet - Computational Complexity HT25, II]]?
    1. If $\mathsf{DTIME}(T(n)) \subseteq \mathsf{DSPACE}(S(n))$, then $\mathsf{DTIME}(T(2^n)) \subseteq \mathsf{DSPACE}(S(2^n))$. ⭐️
    2. Show $\mathsf{DSPACE}(n) \ne \mathsf P$, does it follow $\mathsf{DSPACE}(n) \subsetneq P$? ⭐️
    3. Languages in $\mathsf{DSPACE}(s)$ can be recognised by a family of two-way deterministic finite automata with at most $2^{cs(n)}$ states ⭐️
    4. Every tally language in $\mathsf{NP}$ is in $\mathsf P$ iff $\mathsf{NE} = \mathsf{E}$. ⭐️
    5. Every language in $\mathsf{NTIME}(n^2)$ is decidable in $O(n^2)$ by a 3-tape non-deterministic Turing machine
    6. Show that the language of palindromes is not in $\mathsf{NTISP}(n^{1.1}, n^{0.1})$. ⭐️
  • [[Problem Sheet - Computational Complexity HT25, III]]?
    1. Show that $\mathsf{NSPACE}(n) \subsetneq \mathsf{NSPACE}(n^{1.1})$ using only results proved in lectures ⭐️
    2. Show that the language of pairs of DTMs and inputs where the DTM takes at most $ \vert x \vert ^2$ time is not in $\mathsf{DTIME}(n)$.
    3. Prove unconditionally that there is a language that is $\mathsf{NP}$-hard but not $\mathsf{NP}$-complete
    4. $\mathsf{CNF} _ 2 \in \mathsf P$, but $\mathsf{CNF} _ 3$ is $\mathsf{NP}$-complete
  • [[Problem Sheet - Computational Complexity HT25, IV]]?
    1. Show $\mathsf{QUADRATIC}\text{-}\mathsf{EQUATIONS}$ is $\mathsf{NP}$-hard
    2. Show that if $\mathsf P = \mathsf{NP}$, then there is a polynomial time algorithm which outputs a complete list of prime factors of $n$
    3. Prove $\Pi _ 2\text{-}\mathsf{SAT}$ is $\Pi^p _ 2$-complete
    4. Show $\mathsf{P}^\mathsf{NP} \subseteq \Sigma^p _ 2 \cap \Pi^p _ 2$.
    5. Show that $\mathsf P = \mathsf{NP}$, then $\Sigma^p _ {i} = \mathsf P$ for every $i$.
  • [[Problem Sheet - Computational Complexity HT25, V]]?
    1. $\mathsf{MAJORITY}$ has circuits of size $O(n\log n)$.
    2. There is a Boolean function with polynomial-size formulas but without a polynomial-size CNF
    3. For each integer $k$, there is a Boolean function computable by circuits of size $n^{k+2}$ but not by circuits of size $n^k$. ⭐️
    4. Show that $\mathsf P _ \mathsf{/poly}$ is precisely the class of languages recognisable by Turing machines with polynomially sized advice
    5. If there are a sequence of polynomial-size circuits that compute $\mathsf{SAT}$, then there is a sequence of polynomially size circuits that actually tell you the satisfying assignments
    6. If $\mathsf{NP}$ has polynomial size circuits, then $\Sigma^p _ 2 = \Pi^p _ 2$. ⭐️
  • [[Problem Sheet - Computational Complexity HT25, VI]]?
    1. Simulating a 50-50 coin with a biased coin
    2. Every problem $L \in\mathsf{RP}$ polynomial time $m$-reduces to Dense-Circuit-SAT.
    3. $\mathsf{ZPP} = \mathsf{RP} \cap \mathsf{coRP}$ ⭐️
    4. If $\mathsf{NP} \subseteq \mathsf{BPP}$, then $\mathsf{NP} = \mathsf{RP}$.
    5. $\mathsf{NP} \subseteq \mathsf{PP}$
    6. Weird question


Related posts