• towerful@programming.dev
    link
    fedilink
    English
    arrow-up
    4
    ·
    10 days ago

    I had a huge reply, but after some googling to try and understand, I’m gonna go with this wiki image:

    https://upload.wikimedia.org/wikipedia/commons/thumb/a/a0/P_np_np-complete_np-hard.svg/1024px-P_np_np-complete_np-hard.svg.png

    (Black graph on transparent background, this might be better: https://en.m.wikipedia.org/wiki/NP_(complexity)#/media/File:P_np_np-complete_np-hard.svg )

    I see it as:
    P: is a problem that gets solved and proved easily.
    Np: is is a problem that is difficult to solve but easy to prove.
    P=np ie np-complete: as difficult to solve as it is to prove.
    Np-hard: no single solution, might require multiple “np” solutions (eg a different algorithm for each input element)

    • dfyx@lemmy.helios42.de
      link
      fedilink
      English
      arrow-up
      4
      ·
      edit-2
      10 days ago

      The diagram is pretty good but your interpretation is not quite right, especially for NP-complete and NP-hard.

      NP-hard means “at least as hard as all problems in NP”, proven by the fact that any single NP-hard problem can be used to solve the entire class of all NP problems.

      NP-complete means “at least as hard as all problems in NP and itself also in NP”, so the intersection between NP and NP-hard.

      The thing about P = NP or P != NP is something different. We don’t know if P and NP are the same thing or not, we don’t have a proof in either direction. We only know that P is at least a subset of NP. If we could find a P solution for any NP-hard problem, we would know that P = NP. That would have massive consequences for cryptography and cyber-security because modern encryption relies on the assumption that encrypting something with a key (P) is easier than guessing the key (NP).

      On the other hand, at some point we might find a mathematical proof that we can never find a P solution to an NP-hard problem which would make P != NP. Proving that something doesn’t exist is usually extremely hard and there is the option that even though P != NP we will never be able to prove it and are left to wonder for all eternity.