chris.upliftinglemma.net
Chris Bouchard • they/them
Software Developer and Budgie Concierge
https://sr.ht/~chrisbouchard
https://github.com/chrisbouchard
107 posts
38 followers
140 following
Regular Contributor
Active Commenter
comment in response to
post
Every day we stray further from Jaw's light.
comment in response to
post
Could you share an example? I'm unclear whether you mean problems where we don't know *what* complexity class they're in (though I don't know if someone would say "not in P" in that case), or problems that are believed to be "hard" but in a different way than NP-hard.
comment in response to
post
I realized I didn't directly answer the question. Of course the answer is that it depends.
If you're talking to a complexity specialist, "not in P" means "∉ P." E.g., undecidable or not a decision problem.
For anyone else, there's a very good chance it means "NP-hard" because they assume P≠NP.
comment in response to
post
E.g., it may be that the runtimes of NP problems are bounded by polynomials with terms like n^100 or 10^(10^100). Technically polynomial, but so large a bound that the "efficient" solution might never find a solution in the lifetime of the universe.
comment in response to
post
And lastly, for all of this, "polynomial" means "eventually bounded by a polynomial of the input size." So even if it's true that P=NP, there's no guarantee it's *useful.*
comment in response to
post
Or another way to think of NP is that, if someone says they have a solution to a particular instance of the problem, you can check their answer in polynomial time. (Their answer is the "guess.")
comment in response to
post
Two other points of clarification. NP stands for "non-deterministic polynomial," not "non-polynomial" as a lot of people assume. A problem is in NP if or can be solved in polynomial time when you're allowed to make one polynomial-sized "guess" that's guaranteed to be right.
comment in response to
post
They all seem like pretty hard problems, and we've been trying for a long time. So most computer scientists assume that P≠NP.
comment in response to
post
So we have this web of interconnected problems which are all at least as hard as each other. None of them is known to be in P, but none of them are proven *not* to be in P. If any one of them were in P, it would have to be that P=NP.
comment in response to
post
If the given proven were any "easier" than NP, that the already known problem would be too.
comment in response to
post
Usually the way we "prove a problem is not in P" is by proving that it's NP-hard—at least as hard as any NP problem. We do this by "reducing" a problem already known to be in NP to the given problem. (Or by showing the problem is undecidable, in which case it's not even in NP, let alone P.)
comment in response to
post
"Do you mean A or B?" That's true!
comment in response to
post
I've been tickled by this song since I first heard it. It's a perfect parody of folk tales about American mythology, where the narrator gets every historical fact wrong.
comment in response to
post
Qu'est-ce que c'est?
comment in response to
post
"He is the first American pope in the 2,000-year history of the Catholic Church." That's not 𝘲𝘶𝘪𝘵𝘦 as impressive as it sounds when the USA didn't exist as a country for 1,800 of those 2,000 years.
comment in response to
post
He's a great guy once you get to know him well enough that he stops othering you by default and sees that you're one of the good ones.
comment in response to
post
Thanks for fixing Shift+WASD!
comment in response to
post
‘It's called ✨solidarity✨, which means “agreement between and support for the members of a group, especially a political group”. (Cambridge Dictionary) But god I wish they'd stop asking me, their elected representative, to support them and say that I agree with them!’ — You
comment in response to
post
The celebration continues! #bg3 #photomode #tav #heroesofbaldursgate
comment in response to
post
Getting some comfort from Shadowheart. #bg3 #photomode #tav
comment in response to
post
Make sure you use their full first and middle names so they know they're in trouble.
comment in response to
post
youtu.be/MVbzyikWeBg #guitar #cover #fleetwoodmac
comment in response to
post
As a 37-year-old, I try to start each day with positive affirmations: "That is not dead which can eternal lie, and with strange aeons even death may die."
comment in response to
post
Oh yeah, I always forget about that guy.
comment in response to
post
I was not prepared for this.
comment in response to
post
Well for one, it looks like you forgot to pick your pencil up before taking the photo. 😉
comment in response to
post
(Move over, Susan. I can decipher hidden clues too!)
comment in response to
post
This is clearly a hint that the immortals have 𝘭𝘦𝘵 𝘪𝘵 𝘨𝘰—can't hold them back anymore! They've turned away and slammed the door.
comment in response to
post
FWIW, this is the calculator I used. Not necessarily an endorsement, but it seems to be in the right ballpark. www.minneapolisfed.org/about-us/mon...
comment in response to
post
But remember a dollar from even 1999 was worth almost double a dollar today, with inflation. A dollar from 1985 is worth about three times as much as one today.
So those prices would be more like $100 to $150 today.
comment in response to
post
I think you might be making a molehill out of a mountain.
comment in response to
post
Instantaneously collapsed to the opposite conclusion, regardless of how far they'd been separated.
comment in response to
post
Oh, right, the plays. The plays by Shakespeare. The plays attributed specially to Shakespeare. Shakespeare's plays.
Those plays?
comment in response to
post
The not-quite-letters remind me of kids trying to fool the teacher on true-false tests with a super clever hybrid T/F symbol. It's whatever letter you want to see!
comment in response to
post
The "label this diagram" question on the 10th grade biology test when you kinda sorta remember some of the words.
comment in response to
post
I'm reminded of this classic Weird All song: youtu.be/9gocPZA0HLA