CNS*2020 Online has ended
Welcome to the Sched instance for CNS*2020 Online! Please read the instruction document on detailed information on CNS*2020.
Back To Schedule
Sunday, July 19 • 9:00pm - 10:00pm
P140: How hard are NP-complete problems for humans?

Log in to save this to your schedule, view media, leave feedback and see who's attending!

Feedback form is now closed.

Zoom Link: https://unimelb.zoom.us/j/99879943198?pwd=K1FSK1d4V1dYYXYyT1c1ZUIwWlBVUT09
Password: 105270

Poster link: https://prezi.com/view/TcBGr7hdgut8rgw7blAQ

Pablo Franco, Karlo Doroc, Nitin Yadav, Peter Bossaerts, Carsten Murawski

It is widely accepted that humans have limited cognitive resources and that these finite resources impose restrictions on what the brain can compute. Although endowed with limited computational power, humans are still presented daily with decisions that require solving complex problems. This raises a tension between computational capacity and the computational requirements of solving a problem. In order to understand how hardness of problems affect problem-solving ability we propose a measure to quantify the difficulty of problems for humans. For this we make use of computational complexity theory, a widely studied theory used to quantify the hardness of problems for electronic computers. It has been proposed that computational complexity theory can be applied to humans, but it remains an open empirical question whether this is the case.

We study how difficulty of problems affects decision quality in complex problems by studying a measure of expected difficulty over random instances (i.e. random cases) of a problem. This measure, which we refer to as instance complexity (IC), quantifies the expected hardness of a decision problems; that is, problems that have a yes/no answer. More specifically, this measure captures how constrained the problem is, based on a small number of features of the instance. Overall, IC has three main advantages. Firstly, it is a well- studied measure that has been proven to be applicable to a large range of problems for electronic computers. Secondly, it allows calculation of expected hardness of a problem ex-ante, that is, before solving the problem. And lastly, it captures complexity that is independent of a particular algorithm or model of computation. Thus, it is considered to characterize the inherent computational complexity of random instances, which is independent of the system solving it.

In this study we test whether IC is a generalizable measure, for humans, of the expected hardness of solving a problem. For this purpose, we ran a set of experiments in which human participants solved a set of instances of one of three widely studied NP-Complete problems, namely the Traveling Salesperson, the Knapsack Problem or Boolean Satisfiability. Instances varied in their IC. We show that participants expended more effort on instances with higher IC, but that decision quality was lower in those instances. Together, our results suggest that IC can be used to measure the expected computational requirements of solving random instances of a problem, based on an instance’s features.

The findings of this study speak to the broader question of whether there is a link between the computation model in humans and electronic computers. Specifically, this study gives evidence that the average hardness of random instances can be characterized via the same set of parameters for both computing systems. This provides support that computational complexity theory applies to humans. Moreover, we argue that decision-makers could use IC to estimate the expected costs of performing a task. One reason is that the estimation of IC can be done without having to solve the problem. Furthermore, the results of this study suggest that IC captures the hardness of a random instance. Most importantly, our findings suggest that people modulate their effort according to IC. Altogether, this generates future avenues for research, based on IC, that could shed light into the cognitive resource allocation process in the brain.

avatar for Pablo Franco

Pablo Franco

PhD candidate, University of Melbourne
Human Decision-Making, Computational Complexity, Neuroimaging (fMRI), Open Science, R....

Sunday July 19, 2020 9:00pm - 10:00pm CEST
Slot 17