Quiz 05 (March, 1st)

Statistics

There were 3 problems, each worth 10 points.

Problem 1

Given: A is mapping reducible to B, which is mapping reducible to C. What can you conclude about the decidability og A and/or C if
  1. B is known to be decidable,
  2. B is known to be undecidable?

Solution

If B is decidable then anything that reduces to it is decidable, so A would be decidable. On the other hand a decidable set can reduce to both decidable and undecidable sets so we cannot conclude anything about C.

If B is undecidable then anything it reduces to has to be undecidable as well. Thus, C is undecidable. However, as we noticed above, if something reduces to an undecidable set B then it does not necessarily mean that it itself is undecidable.

Problem 2

Formally define the meaning of f(n) = o(g(n))

Solution

We say that f(n) = o(g(n)) if the limit, when n approaches infinity, of f(n)/g(n) is equal to zero. Equivalently, f(n) is in o(g(n)) if for any constant c > 0 there exists an integer n_0 such that for each n > n_0 we have that cf(n) <= g(n).

Problem 3

Formally define what is meant by TIME(t(n)).

Solution

TIME(t(n)) is a class of languages such that L belongs to TIME(t(n)) if and only if there is Turing machine that decides L and for any string x, this machine halts with O(t(|x|)) steps.
April, 5th