The neural dynamics associated with computational complexity

Many everyday tasks require people to solve computationally complex problems. However, little is known about the effects of computational hardness on the neural processes associated with solving such problems. Here, we draw on computational complexity theory to address this issue. We performed an experiment in which participants solved several instances of the 0-1 knapsack problem, a combinatorial optimization problem, while undergoing ultra-high field (7T) functional magnetic resonance imaging (fMRI). Instances varied in computational hardness. We characterize a network of brain regions whose activation was correlated with computational complexity.

众多日常任务要求人们解决计算复杂的难题。然而，关于计算难度对解决此类问题相关的神经过程的影响，我们所知甚少。本研究借鉴计算复杂性理论，旨在解决此问题。我们进行了一项实验，参与者需要在经历超高压场（7T）功能性磁共振成像（fMRI）的过程中解决0-1背包问题的多个实例，该问题属于组合优化问题。这些实例的计算难度各不相同。我们描绘了与计算复杂性相关的脑区网络，其激活与计算复杂度呈相关性。