• 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.
Advertisements