• Let U be a unary language (it consists of strings of the form $1^i$). Show that if U is NP-Complete, then P = NP.
• Construct a decidable language in P/poly that is NOT in P
• If P = NP, then there’s a language in EXP that requires exponential circuits. For this problem you’ll need the result
$EXP \subseteq P/poly \Rightarrow EXP = \Sigma^p_2$. Note the paradoxical nature of the result: an upper bound (P = NP) implies a lower bound. For the definition of $\Sigma^p_2$, see this chapter.