Homework 4

Distributed on Monday, September 22.
Please bring your solutions to the lecture on Monday, September 29.

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 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.