- In the first page of the exam, article #7 says we should quote any theorem or claim used in class. That sounds totally excessive. Could you be more specific? For instance, I assume that saying "$A\le_m A_{TM}$ and thus $A$ is $\mathcal{RE}$" would be alright, and we wouldn't have to actually cite that "For any $A,B\subseteq\Sigma^*$, if $B\in\mathcal{RE}$ and $A\le_m B$ then $A\in\mathcal{RE}$" and that $A_{TM}\in\mathcal{RE}$. Is this true?
- Can we use in the exam, without proof, theorems proved in the appendices? e.g. $\mathrm{SubsetSum}\in\mathcal{NPC}$. If not, does that mean we've not allowed to use $\mathrm{Partition}\in\mathcal{NPC}$ without proof? (It was proven in recitation using $\mathrm{SubsetSum}\in\mathcal{NPC}$). Same goes for $\mathrm{UHAMCYCLE}\in\mathcal{NPC}$.
- In lecture 12, slide 42 (proving $\mathrm{SAT}\in\mathcal{NPC}$) the last article assumes wlg. that $M(w)$ halts after EXACTLY $t(|w|)$ steps. I don't see why that's needed, and also I'm not sure how that's even possible. Did you mean
*up to*$t(|w|)$? - In lecture 4, slides 23–25 we've seen that $All_{PDA}=\{\langle M\rangle:\ M\text{ is a PDA}\wedge\mathcal{L}(M)=\Sigma^*\}\notin\mathcal{RE}$ if $|\Sigma|>1$. Is that also true for $|\Sigma|=1$? How do you prove it?
- Just out of curiosity. Do you know if the question whether $\mathcal{P}=\mathcal{NP}$ is $\mathcal{R}$, $\mathcal{RE}$ or $co\mathcal{RE}$? Namely, do we know if there's an algorithm that would eventually halt if $\mathcal{P}=\mathcal{NP}$ or $\mathcal{P}\ne\mathcal{NP}$ (regardlessly of input)?

Thanks!