We investigate the complexity cost of demonstrating the key types of nonclassical correlations—Bell inequality violation, Einstein, Podolsky, Rosen (EPR)-steering, and entanglement—with independent agents, theoretically and in a photonic experiment. We show that the complexity cost exhibits a hierarchy among these three tasks, mirroring the recently discovered hierarchy for how robust they are to noise. For Bell inequality violations, the simplest test is the well-known Clauser–Horne–Shimony–Holt test, but for EPR-steering and entanglement the tests that involve the fewest number of detection patterns require nonprojective measurements. The simplest EPR-steering test requires a choice of projective measurement for one agent and a single nonprojective measurement for the other, while the simplest entanglement test uses just a single nonprojective measurement for each agent. In both of these cases, we derive our inequalities using the concept of circular two-designs. This leads to the interesting feature that in our photonic demonstrations, the correlation of interest is independent of the angle between the linear polarizers used by the two parties, which thus require no alignment.