• 8 Posts
  • 352 Comments
Joined 2 years ago
cake
Cake day: June 5th, 2023

help-circle
















  • I have a wishlist that I share with my family and close friends. People follow that list unless they have an idea that they’re 100% sure about. I think the only times I got an unwanted gift was things I already had. Either because something went wrong coordinating between people (rare, everyone knows they can contact my partner to ask what’s still available) or because they accidentally bought the wrong thing (like the first book of a series instead the second one).

    The only exception ever was during a single https://givin.gifts/ secret santa exchange where someone at the same time a) completely ignored my profile, b) gifted something below the stated minimum value, c) didn’t wrap my gift, d) didn’t include a card and e) didn’t include any packing material. They just threw a random 5€ item from the supermarket into an unpadded box and called it a day.




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