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