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