How effective do observers expect other problem solvers to be? What makes a decision seem "human"?" We addressed this question in the context of the Traveling Salesman Problem (TSP), a decision problem in which a perfectly optimal solution is intractable, but for which various kinds of approximate solutions are available. We conducted a series of experiments involving both "production tasks" in which we asked subjects to solve the TSP, and "perception tasks", in which we asked subjects to judge others' solutions to the TSP, rating them for intelligence or humanness. Results suggest that observers expect human solutions to be less optimal than algorithmic solutions: observers expect human problem solvers to exhibit a combination of local and global solution criteria, and to use a short look-ahead window when choosing a solution. These results shed light on human models of other humans' minds, a fundamental problem in social interaction and robotics.

Although the Traveling Salesman Problem (TSP) is an NP-hard problem, human schedulers can find strategies that are comparable if not better than existing algorithms. However, it is still unclear what heuristics they adopt in order to select an approximate solution (Schaefer, 2018). In solving a navigational problem in 3D, the directional heading is an essential factor because changes of direction require additional energy expenditure. In our study, we focus on the connection between local choices minimizing distance and local choices minimizing the turning angle. We then examine human solutions to the TSP in light of the tradeoff between local and global optimization of distance and turning angle. We conducted two experiments showing that while subjects were more likely to move to the nearest node when they plan the next step ahead, they also take the turning angle into consideration and overall adopt a strategy that combines local and global heuristics.