Many decisions economic agents face are intractable. It is often suggested that people use heuristics to overcome intractability and that the resulting decisions closely approximate optimality. We scrutinize the latter claim using computational complexity theory, which predicts that solutions to certain problems cannot be approximated well. In a laboratory experiment, participants were asked to make decisions in three different settings that varied in the degree to which optimal decisions could be approximated. We find that the quality of decisions of human participants is consistent with the predictions of the theory. Our findings imply that intrinsic properties of decisions can explain decision quality without requiring knowledge of the heuristics decision-makers use, or which cognitive resource constraints they face. Since computational complexity theory is derived for abstract computers (“Turing machines”), we conclude that humans choose as if they were abstract computers.