Problem 1

Define the language

$$A_{TM}^k = \left\{ \langle M,w \rangle : M \textrm{ is a TM with at most } k \textrm{ states and } M \textrm{ accepts } w \right\}.$$

Prove that for some $k \geq 1$, the language $A_{TM}^k$ is undecidable.

Problem 2

Consider two undirected graphs $H$ and $G$. Say that $H$ injects into $G$ if there is an injective map $f : V(H) \to V(G)$ such that $\{x,y\} \in E(H) \iff \{f(x),f(y)\} \in E(G)$. Here, $V(H), V(G)$ and $E(H), E(G)$ denote the vertex and edge sets of $H$ and $G$, respectively.

Consider the language

$$\mathrm{INJECTS} = \left\{ \langle H,G\rangle : H \textrm{ and } G \textrm{ are undirected graphs and } H \textrm{ injects into } G \right\}.$$

Show that $\mathrm{INJECTS}$ is NP-complete.

Problem 3 (old)

Recall the classes $\mathsf{EXPTIME} = \bigcup_{k \geq 1} \mathrm{TIME}(2^{n^k})$ and $\mathsf{NEXPTIME} = \bigcup_{k \geq 1} \mathrm{NTIME}(2^{n^k})$. Show that $\mathsf{EXPTIME} \neq \mathsf{NEXPTIME} \implies \mathsf{P} \neq \mathsf{NP}$.

Problem 3 (new)

Define the complexity class $\mathsf{E} = \mathrm{TIME}(2^{O(n)})$. Prove that $\mathsf{E} \neq \mathsf{NP}$.