math

327 readers

4 users here now

Interesting news and discussion centered around Mathematics

founded 2 years ago

MODERATORS

goosethe

What's a concrete example of LIN ⊊ NLIN? (self.math)

submitted 4 days ago by CanadaPlus to c/math

6 comments fedilink hide all child comments

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

[–] jacksilver@lemmy.world 1 points 3 days ago (1 children)

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.

[–] CanadaPlus 2 points 3 days ago* (last edited 2 days ago) (1 children)

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?

[–] jacksilver@lemmy.world 1 points 2 days ago (1 children)

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

[–] CanadaPlus 1 points 2 days ago* (last edited 2 days 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.