41
submitted 6 days ago* (last edited 6 days ago) by sopularity_fax@sopuli.xyz to c/asklemmy@lemmy.ml

🔪Take another stab at it 🔪

you are viewing a single comment's thread
view the rest of the comments
[-] CanadaPlus@lemmy.sdf.org 3 points 5 days ago

What's a concrete example of LIN ⊊ NLIN?

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.

Asked on several related communities. No answers.

this post was submitted on 27 Sep 2025
41 points (100.0% liked)

Asklemmy

50734 readers
1298 users here now

A loosely moderated place to ask open-ended questions

Search asklemmy 🔍

If your post meets the following criteria, it's welcome here!

  1. Open-ended question
  2. Not offensive: at this point, we do not have the bandwidth to moderate overtly political discussions. Assume best intent and be excellent to each other.
  3. Not regarding using or support for Lemmy: context, see the list of support communities and tools for finding communities below
  4. Not ad nauseam inducing: please make sure it is a question that would be new to most members
  5. An actual topic of discussion

Looking for support?

Looking for a community?

~Icon~ ~by~ ~@Double_A@discuss.tchncs.de~

founded 6 years ago
MODERATORS