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.
What’s a concrete example of LIN ⊊ NLIN?
Asked on several related communities. No answers.