space hierarchy theorem AND time hierarchy theorem - 2023 Chicago Open

Question

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]

Back to bonuses

Summary


2023 Chicago Open	08/05/2023	Y	9	5.56	44%	0%	11%

Data


The anti-STOON-dahl cabal (the tall Keyal et al.)	BHSU	0	10	10
Don't be Afraid, the Clown's Afraid Too	The Catastrophic Implosion of Packet Sub	0	10	10
Hang et al., Robert Browning	Evans Hall destruction awaiters	0	0	0
I would prefer not to	Quasicrystal Silence	10	0	10
Team Name Think Detail	remembrance of lost time	0	0	0
I prefer really not to speak. If I speak I’m in big trouble	Romanos IV Diogenes’ Macaroni Grill	0	10	10
Saint Peter Andre 3000	In Search of Things Past	0	0	0
Teach Us to Outgrow Our Ladness	[moderator voice] yes that is so tenpointscore! is your team feeling bonuspilled?	0	10	10
The Canadians	The Plague (anime)" was redirected to: "Oran High School Host Club	0	0	0