I’ve read the old papers proving that fact, but honestly it seems like some of the terminology and notation has changed since the 70’s, and I roundly can’t make heads or tails of it. The other sources I can find are in textbooks that I don’t own.
Ideally, what I’m hoping for is a segment of pseudocode or some modern language that generates an n-character string from some kind of seed, which then cannot be recognised in linear time.
It’s of interest to me just because, coming from other areas of math where inverting a bijective function is routine, it’s highly unintuitive that you provably can’t sometimes in complexity theory.
Yeah, the first paper I read was pretty heavily reliant on them. As far as I can tell they’re laying the pebbles on the execution tree of a nondeterministic machine and then proving something with that.