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