Phase transitions in the knapsack problem

OVERVIEW

Instances of NP-complete problems, such as the knapsack problem, differ significantly in their computational complexity. Computer scientists have been using random instances of NP-complete problems to study differences in computational complexity. It has been shown that some NP-complete problems exhibit so-called threshold phenomena and that computational complexity is related to those thresholds.

More specifically, it has been shown for some NP-complete problems that they have a solvability threshold: there exists an order parameter and a value of this parameter at which instances exhibit a sudden transition (phase transition) from solvable to unsolvable. It has also been shown that instances near this threshold are hard to solve.

In this project, we characterise upper and lower bounds for the solvability threshold in the 0-1 knapsack problem, another NP-complete problem. Using computational experiments, we show that compute time of instances peaks near this solvability threshold. We also show, using data from a laboratory experiment, that effort exerted by people peaks near this threshold.

This is work helps to identify the origins of computational complexity and, thus, 'hardness' of decisions.

KEY RESEARCH QUESTIONS

Does there exist an order parameter for the 0-1 knapsack problem for which instances exhibit a threshold (phase transition) in solvability?
Is compute time related to this order parameter/threshold?

Recent Publications

Research Program

Complexity