These two theorems establish elementary separation results for complexity classes. Intuitively, that means these two theorems state that a Turing machine with more resources can solve more problems, for each of two kinds of resources. For 10 points each:
[10h] Name these two closely related theorems, the slightly simpler of which states that strictly more functions can be computed in space f(n) (“f of n”) than in space asymptotically dominated by f(n).
ANSWER: space hierarchy theorem AND time hierarchy theorem [prompt on hierarchy theorems]
[10e] The space hierarchy theorem can be proven using this technique, which is also used in common proofs that some languages are uncomputable as well as that the real numbers are uncountable.
ANSWER: diagonalization [accept Cantor’s diagonal argument]
[10m] Since by the hierarchy theorems E·X·P·SPACE and E·X·P·TIME are strict supersets of P·SPACE and P, a language that is complete in both has the Cobham-Edwards form of this property, since it can’t be decided in polynomial time or space.
ANSWER: intractability [or intractable]
<Eric Bobrow, Other Science - Computer Science>