Human performance on random instances of NP-complete problems

How does instance complexity affect effort and decision quality?

OVERVIEW

Instances of NP-complete problems differ significantly in their computational complexity. An important approach to understanding the origins of computational complexity has been the study of random instances. It has been shown for some NP-complete problems that there exists an order parameter and a value of this parameter at which there occurs a sudden transition (phase transition) from solvable to unsolvable. This threshold is sometimes referred to as solvability threshold.

We have recently characterised such a solvability threshold for the 0-1 knapsack problem (see related project page for more information).

It has been shown that solving instances near this threshold is 'hard' for computers (technically, there is no known algorithm that can solve these instances in polynomial time).

In this project, we asked participants in a laboratory experiment to solve a set of random instances of different NP-complete problems. Instances differed in their distances to the solvability threshold.

This project provides important evidence linking computational complexity theory and decision-making and helps identifying the origins of computational complexity of decisions.

KEY RESEARCH QUESTIONS

How does distance of instances to the solvability threshold affect effort exerted and computational performance?

Recent Publications

Research Program

Complexity