# Homework 4

Distributed on Monday, September 22.

### Exercise #5:

Remember the complexity classes
P of all problems L⊆{0,1}* decidable by an appropriate BF program in at most polynomial time O(nk) for some integer k
and EXP of all problems decidable in at most exponential time O(2nk) for some k.
Moreover NP consists of all problems of the form   { x∈{0,1}* | ∃ y∈{0,1}p(|x|) : ⟨x,y⟩∈L }   for some polynomial p and LP.
Finally, for some fixed O⊆{0,1}*, the relativized class PO is defined via oracle programs BFO; similarly for NPO and EXPO.

Now consider the problem   A = {P,x,T| program P accepts input x within T steps }. Remember that T is encoded in binary.

1. Show AEXP and PONPOEXPO.
2. For every LEXP prove: NPLEXP.
3. Prove EXPPA.
4. Conclude PA = NPA.

### Exercise #6:

Let H⊆{0,1}* denote the Halting Problem.
1. Suppose A⊆{0,1}* is
• undecidable and
• semi-decidable, and that
• H is not decidable by BFA.
Describe in words why such A would be considered both strictly easier than H and strictly more difficult than ∅?
2. Suppose A,B⊆{0,1}* are semi-decidable, but neither A decidable by BFB, nor B decidable by BFA.
Prove that both A and B are strictly easier than H and strictly more difficult than ∅.
3. Suppose that to every program P? there exists an input x=x(P) satisfying:     PA accepts x   ⇔   xB.
Conclude that B is not decidable by BFA.