2006 - b - b - question 7

[Yana Zhivin]

The question:

 

which of the following is true?

1. time(2^(2^n)) is contained in co-time(2^(2^n)))

2. time(2^n) is contained in time(2^(2^(2^n)))

3. time (2^(2^n)) is contained in time(2^n)

4. 1 and 2

5. 1 and 3

6. 2 and 3

 

the right answer according to the solution sheet is 4.

It is clear that 2 is true, but why is 1 true - isn't 1 only true for spaces?

 

And also,

 

Does anybody know where can i find answers for the open questions of this exam?

 

Thanks,

Yana.

[odedr]

1 is also true, because TIME is a class of deterministic machines
(i.e., "simple" algorithms) and such machines can invert their output.

More precisely, if L is in TIME(2^(2^n)) then there's a O(2^(2^n))-
time deterministic
machine M that solve L, and then the machine M' that runs M and
outputs the inverse
of what it says, solves \bar L, the complement of L, and runs in
(roughly) the same time.


-- Oded