• phorq@lemmy.ml
    link
    fedilink
    arrow-up
    8
    ·
    1 year ago

    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.

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

      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.

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