Finding a suitable NP-complete problem for reduction
This is SAT in disguise. Every name corresponds to a clause. Every paper corresponds to a variable. Each side of the paper corresponds to a possible truth assignment to the variable.

If this is unclear, I suggest working out an example.