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.

  • CanadaPlusOP
    link
    fedilink
    arrow-up
    1
    ·
    edit-2
    3 天前

    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.