[Verse 1]
When we talk about space in computation land
It's memory that our machine needs on hand
PSPACE means polynomial space to play
While NPSPACE adds nondeterministic way
Logarithmic space is L so tight
NL adds nondeterminism to the fight
[Chorus]
Space complexity, how much room we need
L to NL to P indeed
PSPACE equals NPSPACE, Savitch proved it true
TQBF complete, and generalized games too
Memory matters in this hierarchy dance
From log space up to exponential expanse
[Verse 2]
Savitch's theorem changed the game we know
Showed that NPSPACE and PSPACE both can grow
To the same polynomial memory bound
Nondeterminism doesn't add space around
Square the space and simulate the guess
Deterministic paths through nondeterministic mess
[Chorus]
Space complexity, how much room we need
L to NL to P indeed
PSPACE equals NPSPACE, Savitch proved it true
TQBF complete, and generalized games too
Memory matters in this hierarchy dance
From log space up to exponential expanse
[Bridge]
True quantified boolean formulas reign
As PSPACE-complete, they cause the pain
For every x there exists a y
Such that phi is satisfied
Generalized chess and checkers play
Are PSPACE-complete in every way
[Verse 3]
The hierarchy climbs like steps so clear
L subset NL, the path is here
NL subset P, then P subset NP
NP subset PSPACE, as far as we can see
PSPACE subset EXPTIME at the top
This inclusion chain will never stop
[Chorus]
Space complexity, how much room we need
L to NL to P indeed
PSPACE equals NPSPACE, Savitch proved it true
TQBF complete, and generalized games too
Memory matters in this hierarchy dance
From log space up to exponential expanse
[Outro]
From logarithmic space so small and tight
To exponential time's infinite height
Space complexity shows us the way
How much memory our algorithms pay