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