Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due
CS 262: Computational Complexity Homework 2
1. Show that if L = P, then PSPACE = EXP.
2. Define a coding κ to be a mapping from Σ to Σ. Note that κ need not be one-to-one. If x = σ1 . . . σn, where each σi ∈ Σ, then we define κ(x) = κ(σ1). . . κ(σn). If L is a language, then κ(L) is defined to be {κ(x)|x ∈ L}.
(a) Prove that NP is closed under codings. That is, show that if L ∈ NP and κ is a coding defined on the alphabet of L, then κ(L) ∈ NP.
(b) We expect that P is not closed under codings, but we can not prove this without establishing that P 6= NP. Instead, show that P is closed under codings if and only if P = NP.
3. Prove that if every unary language in NP is also in P, then EXP= NEXP. Recall that a language is unary if and only if it is a subset of 1∗ .
Note that the function 2(logk n) is not polynomial if k > 2. Here is an easier version of this problem to start on: prove that if every unary language in NP is also in P, then any language that is is in TIME(2kn) for some k is also in TIME(2cn) for some c. 1