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(n^k) for some integer k
and EXP of all problems decidable in at most exponential time O(2^{n^k}) 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 L∈P.
Finally, for some fixed O⊆{0,1}*, the relativized class P^O is defined via oracle programs BF^O; similarly for NP^O and EXP^O.

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

Show A∈EXP and P^O⊆ NP^O⊆ EXP^O.
For every L∈EXP prove: NP^L⊆EXP.
Prove EXP⊆P^A.
Conclude P^A = NP^A.

Exercise #6:

Let H⊆{0,1}* denote the Halting Problem.

Suppose A⊆{0,1}* is
- undecidable and
- semi-decidable, and that
- H is not decidable by BF^A.
Describe in words why such A would be considered both strictly easier than H and strictly more difficult than ∅?
Suppose A,B⊆{0,1}* are semi-decidable, but neither A decidable by BF^B, nor B decidable by BF^A.
Prove that both A and B are strictly easier than H and strictly more difficult than ∅.
Suppose that to every program P^? there exists an input x=x(P) satisfying: P^A accepts x ⇔ x∈B.
Conclude that B is not decidable by BF^A.