3. EXP is the class of languages decidable in erponential time (i.e. in 2* steps for some k). time can be decided in exponential time (i.e., NP CEXP), but it is an open question if all problems decidable in exponential time are verifable in polynomial time (i.e., EXP S NP), though this is not expected to be true. Formally, the EXP class can be defined similarly to how we define P: EXP:-DTIME 2 keN Prove that NP CEXP 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, eg. a, the order of calculation is automatically assumed to be a)