• Barbacamanitu@lemmy.world
    link
    fedilink
    arrow-up
    1
    ·
    1 year ago

    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.

    • Riven
      link
      fedilink
      arrow-up
      1
      ·
      1 year ago

      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.