How Would You Solve A Knapsack Problem? Computers Want To Know

Learning how people solve problems over a range of difficulties may be crucial to making computers think more like humans.

AsianScientist (Oct. 25, 2016) – Researchers in Australia now have a better understanding of human problem-solving, which could help make computer ‘thinking’ more human-like. Their study was published in Scientific Reports.

Computer science can help us understand why humans struggle with the complex dilemmas life throws at us. 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 at the University of Melbourne said mainstream economic models assume that people ‘optimize’ when faced with these kinds of problems. Yet, we know remarkably little about how humans actually approach problems that, in their most difficult form, choke the most powerful computers, he noted.

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.

However, people did show one advantage over computers: Murawski said that the participants worked harder on more difficult problems, suggesting that they could somehow sense its difficulty. 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 Bossaerts.

The article can be found at: Murawski and Bossaerts (2016) How Humans Solve Complex Problems: The Case of the Knapsack Problem.


Source: University of Melbourne; Photo: Pixabay.
Disclaimer: This article does not necessarily reflect the views of AsianScientist or its staff.

Asian Scientist Magazine is an award-winning science and technology magazine that highlights R&D news stories from Asia to a global audience. The magazine is published by Singapore-headquartered Wildtype Media Group.

Related Stories from Asian Scientist