Question

EXP is the class of languages decidable in exponential time (i.e. in 2" steps for some k) Much like the relationship between P and time can be decided in exponential time (i.e., NP EXP), but it is an open question if all problems decidable in exponential time are verifiable in polynomial time (i.e., EXP NP), though this is not expected to be true. Formally, the EXP class can be defined similarly to how we define P: NP, all languages that are verifiable in polynomial EXP := | | DTIME 12" kEN Prove that NP CE Hint: Think about the size of certificate passed to the verifier of any NP-language, in terms of the size of input. Writing style tips: Remember that, when writing stacked exponents, e.g. a , the order of calculation is automaticallv assumed to be a(b)

Answer 1