Question

discuss EXPTIME, its canonical problems, and its relations to other classes. This one is a little more free-form, so you'll have to figure out what to write about. Or you can focus on 2 classes with a subset/superset relation, describe them and their canonical problems, and prove the subset/superset relation.

Answer 1

Any problem in NP is in EXPTIME because you can either use exponential time to try all possible certificates or to enumerate all possible computation paths of a nondeterministic machine.

More formally, there are two main definitions of NP. One is that a language LL is in NP iff there is a relation RR such that

• there is a polynomial pp such that, for all (x,y)∈R(x,y)∈R, |y|≤p(|x|)|y|≤p(|x|),
• given the string x#yx#y, we can determine in time polynomial in |x#y||x#y| whether (x,y)∈R(x,y)∈R, and
• L={x∣(x,y)∈R}L={x∣(x,y)∈R}.

So, if we have exponential time and we want to know if x∈Lx∈L, we can just try all |Σ|p(n)|Σ|p(n) possible values for~yy and see if (x,y)∈R(x,y)∈R for any of those. That takes time 2O(p(n))2O(p(n)), so L∈L∈EXPTIME.

Alternatively, we can define NP as the set of languages decided by polynomial time nondeterministic Turing machines. In this case, suppose that LL is decided by machine MM in time p(n)p(n) for some polynomial pp, for inputs of length nn. Then MM makes at most p(|x|)p(|x|) nondeterministic choices while determining if x∈Lx∈L. By examining MM's transition function, we can find a constant kk such that MM has at most kk nondeterministic choices at each step of the computation (independent of the input), so it has at most kp(|x|)=2O(p(|x|))kp(|x|)=2O(p(|x|)) different sequences of nondeterministic choices while reading input xx. Given exponential time, we can simulate each of these possibilities one after another and see if any of them accepts.