Many results in combinatorics are governed by results from computational complexity. For example, we are unlikely to find a 'nice' mathematical characterization of Hamiltonian graphs because the corresponding decision problem is NP-complete. Unfortunately, many students pursuing graduate studies in combinatorics do not take courses in the theory of computation.

We discuss the complexity classes P, NP, PSPACE, and NSPACE as well as hardness and completeness with respect to these classes. We also put a modern twist on this standard material by framing the results in terms of Constraint Logic, which was popularized by Bob Hearn and Erik Demaine in their 2009 book Games, Puzzles, and Computation.

Then we have some fun by surveying recent hardness results. This survey includes the video games Buttons and Scissors (iOS / Android), Kwirk (Game Boy), Mazezam (GPL puzzle game), and even Super Mario Bros (Nintendo Entertainment System). We also consider the paper and pencil puzzle Moon-or-Sun (Nikoli) and the physical puzzle Turnstile (ThinkFun).

Throughout the survey our focus will be on the simple yet clever 'gadgets' that are used to bridge the complexity gap between seemingly unrelated problems. We also discuss computer searches that are designed to find gadgets.