I have mentioned P vs NP in the past—describing human tasks in terms of their computational complexity.

This kind of talk tends to remind my academic community—HCI, design research—of the machine learning community, whom they stereotypically view as believing the the brain is the center of all cognition; that cognition is the result of individual calculations in the brain [1]. In this worldview, a classical computer can model the brain, and with it, all cognition.

In reality, cognition extends beyond the brain: to the body (Noë and Thompson 2004), and across bodies (Clark and Chalmers 1998; Hutchins 2005). And we don't know for sure whether or not cognition is modelable as a Turing machine (Clark 2013).

Regardless, all modern accounts of cognition are deeply physical. They rely solely on material explanations. And, like all physical processes, cognition is subject to the computational constraints of space and time. Phrased differently, a hard problem takes longer than easy problems; it may also require more material “stuff.” In cognition, computational slowdowns come from communication overhead between people or things (think: the time it takes for one person to explain something to another, or to write something down); or, even in the most individualistic models of cognition simply “thinking time,” awaiting the results of private calculations.

So, when I talk about human tasks (like writing a symphony) being "in NP," it’s by no means a commitment to an old-fashioned cognitive science account of human activity. Insofar as cognition—embodied and distributed though it may be—is describable in the time and space it takes to perform, descriptions of complexity can apply.

Bibliography

Clark, Andy. 2013. “Whatever Next? Predictive Brains, Situated Agents, and the Future of Cognitive Science.” The Behavioral and Brain Sciences 36 (3):181–204. http://www.ncbi.nlm.nih.gov/pubmed/23663408.

Clark, Andy, and David Chalmers. 1998. “The Extended Mind.” Analysis 58 (1):7–19.

Hutchins, Edwin. 2005. “Distributed Cognition.” Cognition, Technology & Work 7 (1):5.

Noë, Alva, and Evan Thompson. 2004. “Are There Neural Correlates of Consciousness?” Journal of Consciousness Studies 11 (1):3–28.

Footnotes:

[1] This conception is perhaps overly simplistic, in reality.