7
submitted 2 weeks ago by [email protected] to c/[email protected]

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
[-] [email protected] 2 points 1 week ago

I'm not familiar with that notation, what is LIN and NLIN?

[-] [email protected] 3 points 1 week ago* (last edited 1 week ago)

Complexity classes, specifically the ones for algorithms taking asymptotically linear time in the size of their input. One is deterministic, the other nondeterministic.

Other famous classes like L, P or EXP are trivially in their nondeterministic equivalents, but it's unknown if they're strict subsets. In the case of P it's one of the Clay problems. LIN is the main (only?) case where the answer is known, and it's positive.

An example of a problem that's in NP, but we've kind of bet our civilisation on not being in P, is finding a string with a given hash value. It's a function, it gives the same answer every time, but it's preimages are (we think) completely intractable. What I've described as a possible concrete example is a kind of linear-time version of a hash algorithm. That's less useful, but apparently the (linear-time) irreversibility can be proven in that case.

[-] [email protected] 1 points 1 week ago

Thanks for the explanation!

I'm familiar with O() notation, but hadnt seen LIN before, which would be O(1). But that may be because I stick more to the papers written for computer scientists and don't go too deep into mathematic papers.

[-] [email protected] 2 points 1 week ago* (last edited 1 week ago)

Ah sorry, I had no idea, you could have been a topologist who doesn't like computers or something.

LIN is unusual to hear about, probably because it's pretty well understood. Are you more of a coder, or an actual, academic computer scientist? If the latter, what do you know about pebbling games on nondeterministic machines?

[-] [email protected] 1 points 1 week ago

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

[-] [email protected] 1 points 1 week ago* (last edited 1 week 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.

this post was submitted on 25 Jun 2025
7 points (88.9% liked)

math

325 readers
7 users here now

Interesting news and discussion centered around Mathematics

founded 2 years ago
MODERATORS