Computational complexity improves recognition memory for reward-relevant attributes

Computational complexity in optimisation tasks is often seen as impairing optimal choice. We test whether it could have beneficial effects on memory. In a preregistered lab experiment (N = 131) using the NP-hard 0-1 knapsack problem, we manipulated knapsack capacity to create instances differing in two objective complexity metrics: phase transition proximity and Sahni-k. As predicted, solving a more complex instance resulted in a 44% (d = 0.45) increase in above-chance recognition memory relative to a lower-complexity instance. Participants spent longer on the complex instance and clicked on items more often. A plausible interpretation of these findings is that the increased processing requirements of search algorithms under complexity may have resulted in enhanced encoding through frequent revisiting of reward-relevant information. These findings provide a formal framework to generate hypotheses about the memory consequences of complexity and the effects of cognitive offloading in real-world decisions.