• @[email protected]
    link
    fedilink
    81 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.

    • @GoofSchmoofer
      link
      81 year ago

      Yes. Your explanation used proper English and punctuation. As for whether p == np or p != np I don’t know.

    • Riven
      link
      fedilink
      31 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
        link
        11 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
          11 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.