Through the work of pioneering computer scientist Alan Turing, we know that some problems, even though theoretically solvable, would take even the most advanced computer longer than the rest of time to solve.
So how is it that we humans nonetheless tackle and resolve these kinds of difficult problems daily: from which investments to buy for retirement, to which Facebook friends to pay attention to?
These are known as ‘knapsack problems’: they are like deciding how best to fill a knapsack, given an array of items of varying size and value to choose from.
Co-lead author Dr Carsten Murawski, from the Faculty of Business and Economics, said mainstream economic models assume that people ‘optimise’ when faced with these kinds of problems.
“But we know remarkably little about how humans actually approach problems that, in their most difficult form, choke the most powerful computers,” he said.
Murawski and his co-lead, Professor Peter Bossaerts, gave twenty participants eight knapsack problems of varying difficulty (for a computer), not knowing whether complexity for computers would track what their participants found difficult, or whether human qualities of intuition or clever problem-solving would make computer complexity a poor model for humans.
Although people did much better than chance, they found that what is tricky for a computer is likewise harder for humans.
“This implies that many everyday problems that involve allocating resources are simply too complex for us to solve,” said Dr Murawski, although the diversity of approaches participants took to trying to solve the knapsack problems supports a ‘wisdom of crowds’ view, and the importance of information sharing in intellectual discovery and innovation.
However, people did show one advantage over computers.
“Our participants worked harder on more difficult problems, suggesting that they could somehow sense its difficulty,” Dr Murawski observed.
In contrast, computers can only tell whether a particular knapsack problem is hard once they know the solution.
“Discovering how people detect whether something is difficult may turn out to be crucial to making computers more human-like,” said Prof Bossaerts.
The study has been published in the latest edition of Nature Group’s Scientific Reports.