Physical Complexity of a Cognitive Artifact

There are currently two well established domains for studying general problem solving. The first describes strategies used by humans on both experimental and real-world tasks. Human problem solving is captured through a number of frameworks including skill acquisition [1] and automaticity [2], the application of expert knowledge [3, 4], the use of heuristics [5, 6], reinforcement learning and conditioning [7, 8], Bayesian inference [9, 10], analogy making [11, 12], collective intelligence and cognition [13, 14], simulation intelligence [15], the use of external representations [16, 17] and the synergy of mind and matter through exbodiment [18]. The second domain, computational problem solving, investigates algorithms that enable computers to tackle problems effectively . Within this domain, two branches especially pertinent to the present question are: (i) computational complexity theory, which analyzes the resources (time, memory, etc.) required to solve problems as functions of input size, typically in the asymptotic limit; and (ii) the study of search algorithms, which seeks efficient solutions to specific tasks (e.g., games and puzzles) by exploiting the combinatorial structure of state spaces, often via heuristics [19-22].