Datman2020@lemmy.fmhy.ml to Asklemmy@lemmy.ml · 1 year agoWhat two things are thought to be completely unrelated but in reality are actually very similar?message-squaremessage-square31fedilinkarrow-up161arrow-down10
arrow-up161arrow-down1message-squareWhat two things are thought to be completely unrelated but in reality are actually very similar?Datman2020@lemmy.fmhy.ml to Asklemmy@lemmy.ml · 1 year agomessage-square31fedilink
minus-squareBarbacamanitu@lemmy.worldlinkfedilinkarrow-up1·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-squareRiven@sh.itjust.workslinkfedilinkarrow-up1·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.