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.
Oh no worries, I think I stumbled on this in a computer science crosspost.
While I do lean a bit in the academics, my area is mostly in ML / AI so not well read in pebbling games (although it sounds interesting).
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.