The neural dynamics associated with computational complexity.

Publisher: Public Library of Science Country of Publication: United States NLM ID: 101238922 Publication Model: eCollection Cited Medium: Internet ISSN: 1553-7358 (Electronic) Linking ISSN: 1553734X NLM ISO Abbreviation: PLoS Comput Biol Subsets: MEDLINE

Original Publication: San Francisco, CA : Public Library of Science, [2005]-

Magnetic Resonance Imaging* ; Brain*/physiology ; Brain*/diagnostic imaging ; Computational Biology*; Humans ; Male ; Female ; Adult ; Brain Mapping/methods ; Young Adult ; Problem Solving/physiology ; Models, Neurological ; Cognition/physiology ; Nerve Net/physiology ; Nerve Net/diagnostic imaging

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, including the anterior insula, dorsal anterior cingulate cortex and the intra-parietal sulcus/angular gyrus. Activation and connectivity changed dynamically as a function of complexity, in line with theoretical computational requirements. Overall, our results suggest that computational complexity theory provides a suitable framework to study the effects of computational hardness on the neural processes associated with solving complex cognitive tasks.
Competing Interests: The authors have declared that no competing interests exist.
(Copyright: © 2024 Franco et al. This is an open access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.)

Neuropsychologia. 2009 Jan;47(2):604-8. (PMID: 19007800)
Neuron. 2013 Jul 24;79(2):217-40. (PMID: 23889930)
PLoS Comput Biol. 2018 Aug 24;14(8):e1006370. (PMID: 30142152)
Neuroimage. 2011 Feb 1;54(3):2382-93. (PMID: 20946958)
Neuroimage. 2012 Mar;60(1):747-65. (PMID: 22245637)
Science. 2014 Jun 27;344(6191):1481-6. (PMID: 24876345)
Nature. 2005 Jun 9;435(7043):759-64. (PMID: 15944693)
Psychophysiology. 2018 Mar;55(3):. (PMID: 29044552)
J Exp Psychol Gen. 2014 Dec;143(6):2380-400. (PMID: 25347536)
Hum Brain Mapp. 2018 Jul;39(7):2887-2906. (PMID: 29575249)
Cereb Cortex. 2020 Jun 30;30(8):4361-4380. (PMID: 32244253)
Neuroimage. 2011 Jul 15;57(2):303-11. (PMID: 21168515)
Proc Natl Acad Sci U S A. 2007 Jun 26;104(26):11073-8. (PMID: 17576922)
Neuron. 2006 Jun 1;50(5):799-812. (PMID: 16731517)
Cereb Cortex. 2016 Jan;26(1):192-201. (PMID: 25150283)
Philos Trans R Soc Lond B Biol Sci. 2021 Mar;376(1819):20190664. (PMID: 33423634)
Neuroimage. 2014 Oct 1;99:59-68. (PMID: 24887509)
Front Integr Neurosci. 2018 Dec 04;12:61. (PMID: 30568581)
Proc Natl Acad Sci U S A. 2007 Jun 19;104(25):10318-23. (PMID: 17567754)
Sci Rep. 2022 Jul 28;12(1):12914. (PMID: 35902593)
Front Neurosci. 2017 Jun 06;11:316. (PMID: 28634438)
Sci Rep. 2016 Oct 07;6:34851. (PMID: 27713516)
Nat Commun. 2021 Feb 15;12(1):1030. (PMID: 33589626)
Proc Natl Acad Sci U S A. 2013 Oct 8;110(41):16616-21. (PMID: 24062451)
Cereb Cortex. 2011 Nov;21(11):2650-62. (PMID: 21498405)
Nat Neurosci. 2011 Sep 18;14(10):1338-44. (PMID: 21926982)
Trends Cogn Sci. 2012 Feb;16(2):122-8. (PMID: 22226543)
J Neurosci. 2020 May 6;40(19):3838-3848. (PMID: 32273486)
Cereb Cortex. 2017 Oct 1;27(10):5024-5039. (PMID: 28922835)
Neuron. 2017 Jan 4;93(1):15-31. (PMID: 28056343)
Curr Opin Neurobiol. 2016 Apr;37:1-6. (PMID: 26687618)
Comput Biomed Res. 1996 Jun;29(3):162-73. (PMID: 8812068)
Trends Neurosci. 2000 Oct;23(10):475-83. (PMID: 11006464)
J Neurosci. 2011 Jul 27;31(30):11077-87. (PMID: 21795556)
J Neurosci. 2016 Jun 8;36(23):6147-55. (PMID: 27277793)
Cereb Cortex. 2017 Mar 1;27(3):2154-2165. (PMID: 26972752)
Cogn Affect Behav Neurosci. 2008 Dec;8(4):363-74. (PMID: 19033235)
Curr Opin Neurobiol. 2006 Apr;16(2):222-9. (PMID: 16546373)
Trends Cogn Sci. 2010 Apr;14(4):172-9. (PMID: 20171926)
Trends Cogn Sci. 2017 Dec;21(12):917-929. (PMID: 29149998)
Cereb Cortex. 2017 Mar 1;27(3):2403-2417. (PMID: 27095824)

Date Created: 20240923 Date Completed: 20241003 Latest Revision: 20241005

20250114

PMC11449275

10.1371/journal.pcbi.1012447

39312586