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.

you are viewing a single comment's thread
view the rest of the comments
[–] 1 point 1 year ago (1 child)

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).

  • source
  • parent
  • hideshow 1 child comment
  • [–] [S] 1 point 1 year ago

    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.

  • source
  • parent