Datman2020 to [email protected] • 1 year agoWhat two things are thought to be completely unrelated but in reality are actually very similar?message-square30fedilinkarrow-up161arrow-down10
arrow-up161arrow-down1message-squareWhat two things are thought to be completely unrelated but in reality are actually very similar?Datman2020 to [email protected] • 1 year agomessage-square30fedilink
minus-square@Barbacamanitulink1•1 year agoIs it only no complete? Or does this include np-hard? I just posted a comment about this and thought it applied to np-hard.
minus-squareRivenlinkfedilink1•1 year agoMy 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.
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.