60
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 10 Jul 2023
60 points (100.0% liked)
Asklemmy
43019 readers
1245 users here now
A loosely moderated place to ask open-ended questions
If your post meets the following criteria, it's welcome here!
- Open-ended question
- 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.
- Not regarding using or support for Lemmy: context, see the list of support communities and tools for finding communities below
- Not ad nauseam inducing: please make sure it is a question that would be new to most members
- An actual topic of discussion
Looking for support?
Looking for a community?
- Lemmyverse: community search
- sub.rehab: maps old subreddits to fediverse options, marks official as such
- !lemmy411@lemmy.ca: a community for finding communities
~Icon~ ~by~ ~@Double_A@discuss.tchncs.de~
founded 5 years ago
MODERATORS
Aren't Sudoku and protein folding essentially the same problem? Like, if you could write a computer program to solve sudoku in polynomial time, you could adapt that solution to solve protein folding problems in polynomial time? Or something like that.
Someone who is smarter than me, please chime in.
You're talking about the theory of p = np. The idea that any problem whose solution can be verified quickly can also be solved quickly. This has not been proven or disproven, it's a bit of an open mystery in computer science, but most are under the impression this is not the case and that p != np. Someone smarter than me please verify my explanation in linear time please.
Yes. Your explanation used proper English and punctuation. As for whether p == np or p != np I don't know.
Specifically I think they’re talking about the subclass of np problems called “np complete” that are functionally identical to each other in some mathy way such that solving one of them instantly gives you a method to solve all of them.
Is it only no complete? Or does this include np-hard? I just posted a comment about this and thought it applied to np-hard.
My understanding is that it’s layered. An np-complete solution solves all np and np-complete problems, and an np-hard solution solves all np, np-complete, and np-hard problems.
Of course by “np” here I mean non-complete non-hard np problems.
Similar with circle-packing algorithms and origami?
I heard on Stephen Wolfram's podcast the other day that all NP Hard problems are equivalent. For example, you can embed the halting problem within the traveling salesman problem and vice versa. I believe this means that solving one would automatically solve all the others.