Computational complexity of decisions: Quantifying computational hardness and its effects on human computation

© 2021 Juan Pablo Franco UlloaHumans are presented daily with decisions that require solving complex problems. In many cases, solving these problems is computationally hard. This raises a tension between the computational capacity of the agent and the computational requirements of a task. Whilst the underlying invariants of this mechanism remain unclear in cognition, they have been widely studied in computer science. I build on theoretical and empirical work in computational complexity, which characterizes the intrinsic computational hardness of problems. I first present an adaptation of this theoretical framework for the study of human cognition by introducing a set of metrics of hardness of instances of problems. I do this in a way that is independent of any algorithm or computational model and that can be generalized to other problems. Based on this, I explore empirically, in a set of lab experiments, how these task-independent metrics of hardness affect human problem-solving. I do this at two levels of analysis. Firstly, I study how these metrics affect human performance at the behavioral level in three canonical computational problems: the knapsack problem, the traveling salesperson problem and the Boolean satisfiability problem. Secondly, I examine the relation between computational hardness and the neural processes associated with problem-solving, employing ultra-high field functional MRI. I find that the metrics of intrinsic hardness put forward here predict human performance and time-on-task across the three computational problems in a similar way. Moreover, I identify the neural correlates of computational hardness in the knapsack task, a complex problem-solving task. I show that this framework can be used for the study of the neural underpinnings of problem-solving by providing a generic definition of cognitive demand. The results of these studies provide support for the conceptual premise that the quantification of intrinsic hardness is fundamental in the development of more refined theories of human decision-making and its neural underpinnings. Critically, they provide a framework to study how humans adapt to computational complexity and how intrinsic hardness of tasks affect the reliability of human decision-making. This could inform public policy by identifying which decisions over products involve solving problems that require computational resources beyond those available to an agent, and how this affects decisions