# 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^{nk})
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}.