7
What's a concrete example of LIN ⊊ NLIN?
(lemmy.sdf.org)
you are viewing a single comment's thread
view the rest of the comments
view the rest of the comments
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
I'm not familiar with that notation, what is LIN and NLIN?
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.
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.
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?
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.