Not being awkward is NP-hard
This meme got me thinking:
That feeling when you’re smart enough to know how awkward you are, but not smart enough to know how not to be awkward
The reason it works that way is because not being awkward is NP-hard, and I can prove it.
It is known that the SAT problem is NP-hard. SAT, or the satisfiability problem, is the problem of taking a logical statement involving a series of boolean values, and determining whether there is some combination of true/false assignments to those values such that the overall logical statement is true.
I will show that the problem of not being awkward is solvable in polynomial time only if SAT is solvable in polynomial time.
Let A be a statement that is known to be awkward. (For example, calling your interlocutor stinky could be regarded as awkward; the exact statement doesn’t matter.)
Now consider some arbitrarily complicated combination of a series of logical statements including statement A. Call that combination statement S. For example:
[you are stinky AND you have blue eyes] OR [you have red hair AND (you are stinky OR I am hungry)] OR […]
If I express S verbally, then I am asserting that S is true. The question then becomes, is there some truth assignment to each of these sub-statements such that the whole statement is true, BUT “you are stinky” is false? Answering that question is equivalent to solving SAT.
S is awkward if and only if “you are stinky” is forced to be true to make S true.
To knowing whether “you are stinky” is forced to be true (in full generality for any statement S), you have to solve SAT.
Therefore, if you can solve for the awkwardness of a statement, then you can solve SAT.
One conceivable objection to this proof: if it is ambiguous whether statement S requires “you are stinky” to be true, then perhaps S is unconditionally awkward. While this may be true in many social situations, it’s not universally true.
For not-being-awkward to be shown to be NP-hard, we don’t need to show that it always solves SAT, only that there is a class of statements that, if solved, would solve SAT. So consider the following social context:
You are talking to a literal-minded mathematician. You say to this person, “If [complicated logical statement] then you’re stinky.” Calling them stinky would be awkward. But, as a literal-minded mathematician, they only take you to be calling them stinky if the antecedent is true. This person would not consider it awkward if you said, “If the moon is made of cheese then you’re stinky.”
There only needs to be one such literal-minded mathematician in the world for my proof to hold, because if there is, that means you can’t always identify a non-awkward statement in polynomial time. There are some situations where identifying non-awkwardness solves SAT, and therefore the problem in full generality is NP-hard.
(It is not yet known whether the awkwardness problem is NP-complete.)
Thanks to Scott Aaronson for suggesting a way to simplify my proof.