In computational complexity theory, decision problems are divided into complexity classes based on the amount of computational resources it takes for algorithms to solve them. In theoretical computer science, it is commonly accepted that only functions for solving problems in the complexity class P, solvable by a deterministic Turing machine in polynomial time, are considered to be tractable. In cognitive science and philosophy, this tractability result has been used to argue that only functions in P can feasibly work as computational (...) models of human cognitive capacities. One interesting area of computational complexity theory is descriptive complexity, which connects the expressive strength of systems of logic with the computational complexity classes. In descriptive complexity theory, it is established that only first-order systems are connected to P, or one of its subclasses. Consequently, second-order systems of logic are considered to be computationally intractable, and may therefore seem to be unfit to model human cognitive capacities. This would be problematic when we think of the role of logic as the foundations of mathematics. In order to express many important mathematical concepts and systematically prove theorems involving them, we need to have a system of logic stronger than classical first-order logic. But if such a system is considered to be intractable, it means that the logical foundation of mathematics can be prohibitively complex for human cognition. In this paper I will argue, however, that this problem is the result of an unjustified direct use of computational complexity classes in cognitive modelling. Placing my account in the recent literature on the topic, I argue that the problem can be solved by considering computational complexity for humanly relevant problem solving algorithms and input sizes. (shrink)

Following Marr’s famous three-level distinction between explanations in cognitive science, it is often accepted that focus on modeling cognitive tasks should be on the computational level rather than the algorithmic level. When it comes to mathematical problem solving, this approach suggests that the complexity of the task of solving a problem can be characterized by the computational complexity of that problem. In this paper, I argue that human cognizers use heuristic and didactic tools and thus engage in cognitive processes that (...) make their problem solving algorithms computationally suboptimal, in contrast with the optimal algorithms studied in the computational approach. Therefore, in order to accurately model the human cognitive tasks involved in mathematical problem solving, we need to expand our methodology to also include aspects relevant to the algorithmic level. This allows us to study algorithms that are cognitively optimal for human problem solvers. Since problem solving methods are not universal, I propose that they should be studied in the framework of enculturation, which can explain the expected cultural variance in the humanly optimal algorithms. While mathematical problem solving is used as the case study, the considerations in this paper concern modeling of cognitive tasks in general. (shrink)

We overview logical and computational explanations of the notion of tractability as applied in cognitive science. We start by introducing the basics of mathematical theories of complexity: computability theory, computational complexity theory, and descriptive complexity theory. Computational philosophy of mind often identifies mental algorithms with computable functions. However, with the development of programming practice it has become apparent that for some computable problems finding effective algorithms is hardly possible. Some problems need too much computational resource, e.g., time or memory, to (...) be practically computable. Computational complexity theory is concerned with the amount of resources required for the execution of algorithms and, hence, the inherent difficulty of computational problems. An important goal of computational complexity theory is to categorize computational problems via complexity classes, and in particular, to identify efficiently solvable problems and draw a line between tractability and intractability. -/- We survey how complexity can be used to study computational plausibility of cognitive theories. We especially emphasize methodological and mathematical assumptions behind applying complexity theory in cognitive science. We pay special attention to the examples of applying logical and computational complexity toolbox in different domains of cognitive science. We focus mostly on theoretical and experimental research in psycholinguistics and social cognition. (shrink)

Experiments are presented showing that visual search for Mueller-Lyer (ML) stimuli is based on complete configurations, rather than component segments. Segments easily detected in isolation were difficult to detect when embedded in a configuration, indicating preemption by low-level groups. This preemption—which caused stimulus components to become inaccessible to rapid search—was an all-or-nothing effect, and so could serve as a powerful test of grouping. It is shown that these effects are unlikely to be due to blurring by simple spatial filters at (...) early visual levels. It is proposed instead that they are due to more sophisticated processes that rapidly bind contour fragments into spatially-extended assemblies. These results support the view that rapid visual search cannot access the primitives formed at the earliest stages of visual processing; rather, it can access only higher-level, more ecologically-relevant structures. (shrink)

Despite their success in describing and predicting cognitive behavior, the plausibility of so-called ‘rational explanations’ is often contested on the grounds of computational intractability. Several cognitive scientists have argued that such intractability is an orthogonal pseudoproblem, however, since rational explanations account for the ‘why’ of cognition but are agnostic about the ‘how’. Their central premise is that humans do not actually perform the rational calculations posited by their models, but only act as if they do. Whether or not the problem (...) of intractability is solved by recourse to ‘as if’ explanations critically depends, inter alia, on the semantics of the ‘as if’ connective. We examine the five most sensible explications in the literature, and conclude that none of them circumvents the problem. As a result, rational ‘as if’ explanations must obey the minimal computational constraint of tractability. (shrink)

Consciousness is known to be limited in processing capacity and often described in terms of a unique processing stream across a single dimension: time. In this paper, we discuss a purely temporal pattern code, functionally decoupled from spatial signals, for conscious state generation in the brain. Arguments in favour of such a code include Dehaene et al.’s long-distance reverberation postulate, Ramachandran’s remapping hypothesis, evidence for a temporal coherence index and coincidence detectors, and Grossberg’s Adaptive Resonance Theory. A time-bin resonance model (...) is developed, where temporal signatures of conscious states are generated on the basis of signal reverberation across large distances in highly plastic neural circuits. The temporal signatures are delivered by neural activity patterns which, beyond a certain statistical threshold, activate, maintain, and terminate a conscious brain state like a bar code would activate, maintain, or inactivate the electronic locks of a safe. Such temporal resonance would reflect a higher level of neural processing, one that is independent from sensorial or perceptual brain mechanisms. (shrink)

Can the output of human cognition be predicted from the assumption that it is an optimal response to the information-processing demands of the environment? A methodology called rational analysis is described for deriving predictions about cognitive phenomena using optimization assumptions. The predictions flow from the statistical structure of the environment and not the assumed structure of the mind. Bayesian inference is used, assuming that people start with a weak prior model of the world which they integrate with experience to develop (...) stronger models of specific aspects of the world. Cognitive performance maximizes the difference between the expected gain and cost of mental effort. Memory performance can be predicted on the assumption that retrieval seeks a maximal trade-off between the probability of finding the relevant memories and the effort required to do so; in categorization performance there is a similar trade-off between accuracy in predicting object features and the cost of hypothesis formation; in casual inference the trade-off is between accuracy in predicting future events and the cost of hypothesis formation; and in problem solving it is between the probability of achieving goals and the cost of both external and mental problem-solving search. The implemention of these rational prescriptions in neurally plausible architecture is also discussed. (shrink)

This book delivers much more than its title appears to promise; it is not merely a description of current methods for remotely monitoring brain activity. It primarily concentrates on just one such method: positron emission tomography, but it demonstrates beautifully how far that technique can now take us in the quest to discover the mechanisms underlying thought.

Many cognitive scientists, having discovered that some computational-level characterization f of a cognitive capacity φ is intractable, invoke heuristics as algorithmic-level explanations of how cognizers compute f. We argue that such explanations are actually dysfunctional, and rebut five possible objections. We then propose computational-level theory revision as a principled and workable alternative.

The purpose of this paper is to present two kinds of analogical representational change, both occurring early in the analogy-making process, and then, using these two kinds of change, to present a model unifying one sort of analogy-making and categorization. The proposed unification rests on three key claims: (1) a certain type of rapid representational abstraction is crucial to making the relevant analogies (this is the first kind of representational change; a computer model is presented that demonstrates this kind of (...) abstraction), (2) rapid abstractions are induced by retrieval across large psychological distances, and (3) both categorizations and analogies supply understandings of perceptual input via construing, which is a proposed type of categorization (this is the second kind of representational change). It is construing that finalizes the unification. (shrink)

The purpose of this paper is to present two kinds of analogical representational change, both occurring early in the analogy-making process, and then, using these two kinds of change, to present a model unifying one sort of analogy-making and categorization. The proposed unification rests on three key claims: (1) a certain type of rapid representational abstraction is crucial to making the relevant analogies (this is the first kind of representational change; a computer model is presented that demonstrates this kind of (...) abstraction), (2) rapid abstractions are induced by retrieval across large psychological distances, and (3) both categorizations and analogies supply understandings of perceptual input via construing, which is a proposed type of categorization (this is the second kind of representational change). It is construing that finalizes the unification. (shrink)

Working memory limits are best defined in terms of the complexity of the relations that can be processed in parallel. Complexity is defined as the number of related dimensions or sources of variation. A unary relation has one argument and one source of variation; its argument can be instantiated in only one way at a time. A binary relation has two arguments, two sources of variation, and two instantiations, and so on. Dimensionality is related to the number of chunks, because (...) both attributes on dimensions and chunks are independent units of information of arbitrary size. Studies of working memory limits suggest that there is a soft limit corresponding to the parallel processing of one quaternary relation. More complex concepts are processed by or In segmentation, tasks are broken into components that do not exceed processing capacity and can be processed serially. In conceptual chunking, representations are to reduce their dimensionality and hence their processing load, but at the cost of making some relational information inaccessible. Neural net models of relational representations show that relations with more arguments have a higher computational cost that coincides with experimental findings on higher processing loads in humans. Relational complexity is related to processing load in reasoning and sentence comprehension and can distinguish between the capacities of higher species. The complexity of relations processed by children increases with age. Implications for neural net models and theories of cognition and cognitive development are discussed. (shrink)

According to the target article authors, initial experience with a circumstance primes a relation that can subsequently be applied to a different circumstance to draw an analogy. While I broadly agree with their claim about the role of relational priming in early analogical reasoning, I put forward a few concerns that may be worthy of further reflection.

This paper explores the ways in which resource limitations influence the nature of perceptual and cognitive processes. A framework is developed that allows early visual processing to be analyzed in terms of these limitations. In this approach, there is no one ``best'' system for any visual process. Rather, a spectrum of systems exists, differing in the particular trade-offs made between performance and resource requirements.

Recent developments in vision science have resulted in several major changes in our understanding of human visual perception. For example, attention no longer appears necessary for "visual intelligence"--a large amount of sophisticated processing can be done without it. Scene perception no longer appears to involve static, general-purpose descriptions, but instead may involve dynamic representations whose content depends on the individual and the task. And vision itself no longer appears to be limited to the production of a conscious "picture"--it may also (...) guide processes outside the conscious awareness of the observer. (shrink)

One of the more powerful impressions created by vision is that of a coherent, richly-detailed world where everything is present simultaneously. Indeed, this impression is so compelling that we tend to ascribe these properties not only to the external world, but to our internal representations as well. But results from several recent experiments argue against this latter ascription. For example, changes in images of real-world scenes often go unnoticed when made during a saccade, flicker, blink, or movie cut. This "change (...) blindness" provides strong evidence against the idea that our brains contain a picture-like representation of the scene that is everywhere detailed and coherent. (shrink)

Why should moral philosophers, moral psychologists, and machine ethicists care about computational complexity? Debates on whether artificial intelligence (AI) can or should be used to solve problems in ethical domains have mainly been driven by what AI can or cannot do in terms of human capacities. In this paper, we tackle the problem from the other end by exploring what kind of moral machines are possible based on what computational systems can or cannot do. To do so, we analyze normative (...) ethics through the lens of computational complexity. First, we introduce computational complexity for the uninitiated reader and discuss how the complexity of ethical problems can be framed within Marr’s three levels of analysis. We then study a range of ethical problems based on consequentialism, deontology, and virtue ethics, with the aim of elucidating the complexity associated with the problems themselves (e.g., due to combinatorics, uncertainty, strategic dynamics), the computational methods employed (e.g., probability, logic, learning), and the available resources (e.g., time, knowledge, learning). The results indicate that most problems the normative frameworks pose lead to tractability issues in every category analyzed. Our investigation also provides several insights about the computational nature of normative ethics, including the differences between rule- and outcome-based moral strategies, and the implementation-variance with regard to moral resources. We then discuss the consequences complexity results have for the prospect of moral machines in virtue of the trade-off between optimality and efficiency. Finally, we elucidate how computational complexity can be used to inform both philosophical and cognitive-psychological research on human morality by advancing the moral tractability thesis. (shrink)

The rise of Artificial Intelligence (AI) has produced prophets and prophecies announcing that the age of artificial consciousness is near. Not only does the mere idea that any machine could ever possess the full potential of human consciousness suggest that AI could replace the role of God in the future, it also puts into question the fundamental human right to freedom and dignity. This position paper takes the stand that, in the light of all we currently know about brain evolution (...) and the never-stopping formation of adaptive neural circuitry for learning, memory, decision making and, ultimately, fully conscious reasoning and creativity in the human species, the idea of an artificial consciousness appears misconceived. The paper highlights some of the major reasons why. While awareness to external stimuli for processes such as perception, recognition, and operational problem solving is under the direct control of functionally specific brain networks associated with sensory and cognitive functions across animal species, consciousness is a unique property of the human mind. (shrink)

Consciousness is known to be limited in processing capacity and often described in terms of a unique processing stream across a single dimension: time. In this paper, we discuss a purely temporal pattern code, functionally decoupled from spatial signals, for conscious state generation in the brain. Arguments in favour of such a code include Dehaene et al.'s long-distance reverberation postulate, Ramachandran's remapping hypothesis, evidence for a temporal coherence index and coincidence detectors, and Grossberg's Adaptive Resonance Theory. A time-bin resonance model (...) is developed, where temporal signatures of conscious states are generated on the basis of signal reverberation across large distances in highly plastic neural circuits. The temporal signatures are delivered by neural activity patterns which, beyond a certain statistical threshold, activate, maintain, and terminate a conscious brain state like a bar code would activate, maintain, or inactivate the electronic locks of a safe. Such temporal resonance would reflect a higher level of neural processing, independent from sensorial or perceptual brain mechanisms. (shrink)

The recognition that human minds/brains are finite systems with limited resources for computation has led some researchers to advance theTractable Cognition thesis: Human cognitive capacities are constrained by computational tractability. This thesis, if true, serves cognitive psychology by constraining the space of computational‐level theories of cognition. To utilize this constraint, a precise and workable definition of “computational tractability” is needed. Following computer science tradition, many cognitive scientists and psychologists define computational tractability as polynomial‐time computability, leading to theP‐Cognition thesis. This article (...) explains how and why the P‐Cognition thesis may be overly restrictive, risking the exclusion of veridical computational‐level theories from scientific investigation. An argument is made to replace the P‐Cognition thesis by theFPT‐Cognition thesisas an alternative formalization of the Tractable Cognition thesis (here, FPT stands for fixed‐parameter tractable). Possible objections to the Tractable Cognition thesis, and its proposed formalization, are discussed, and existing misconceptions are clarified. (shrink)

Pictures of normal brain activity during human thought can be worth a great deal. Electrophysiology and functional neuroimaging together allow both temporal and spatial dimensions of neurocognitive functions to be explored. Although these techniqueshave their limitations, the Cognitive Neuroscience approach is well-suited to pursuing questions about how words are perceived, understood, and remembered.

The emperor's new mind (hereafter Emperor) is an attempt to put forward a scientific alternative to the viewpoint of according to which mental activity is merely the acting out of some algorithmic procedure. John Searle and other thinkers have likewise argued that mere calculation does not, of itself, evoke conscious mental attributes, such as understanding or intentionality, but they are still prepared to accept the action the brain, like that of any other physical object, could in principle be simulated by (...) a computer. In Emperor I go further than this and suggest that the outward manifestations ofconscious mental activity cannot even be properly simulated by calculation. To support this view, I use various arguments to show that the results of mathematical insight, in particular, do not seem to be obtained algorithmically. The main thrust ofthis work, however, is to present an overview ofthe present state of physical understanding and to show that an important gap exists at the point where, quantum and classical physics meet, as well as to speculate on how the conscious brain might be taking advantage ofwhatever new physics is needed to fill this gap to achieve its nonalgorithmic effects. (shrink)

Theory of mind refers to the human capacity for reasoning about others’ mental states based on observations of their actions and unfolding events. This type of reasoning is notorious in the cognitive science literature for its presumed computational intractability. A possible reason could be that it may involve higher-order thinking. To investigate this we formalize theory of mind reasoning as updating of beliefs about beliefs using dynamic epistemic logic, as this formalism allows to parameterize ‘order of thinking.’ We prove that (...) theory of mind reasoning, so formalized, indeed is intractable. Using parameterized complexity we prove, however, that the ‘order parameter’ is not a source of intractability. We furthermore consider a set of alternative parameters and investigate which of them are sources of intractability. We discuss the implications of these results for the understanding of theory of mind. (shrink)

Posner & Raichle's (1994) exciting, wonderfully illustrated book describes the past successes and future potential of the relatively noninvasive imaging of the nervous systems of living people. The focus has been on cognitive processes but there is no reason why emotional and motivational systems cannot also be tapped. Although the authors do not formally address such contentious issues as consciousness and the private experience of other species, imaging methods may hold promise for helping us to understand these phenomena, as well (...) as to integrate psychological processes into ethological and phylogenetic research in general. (shrink)

In Posner & Raichle's (1994) book, two essential and strictly related limitations of cognitive neurophysiology are not sufficiently enhanced: (1) The problem of “coding,” namely the capability of a natural brain to redefine its own “basic symbols” as a function of a changing environment; (2) the inadequacy of a Hebbian rule to reckon with complex computational problems such as those solved by real brains.

Posner & Raichle's (1994) book is a fascinating and readable account of the studies the authors have conducted on the localization of cognitive functions in the brain mainly using PET and EEC evoked potential methods. Our criticism concerns the underrepresentation of some imaging techniques (magnetoencephalography) and some forms of brain activity (spontaneous activity). Furthermore, the book leaves the reader with the impression that the brain only responds to external events.

By reviewing most of the neurobiology of consciousness, this article highlights some major reasons why a successful emulation of the dynamics of human consciousness by artificial intelligence is unlikely. The analysis provided leads to conclude that human consciousness is epigenetically determined and experience and context-dependent at the individual level. It is subject to changes in time that are essentially unpredictable. If cracking the code to human consciousness were possible, the result would most likely have to consist of a temporal pattern (...) code simulating long-distance signal reverberation and de-correlation of all spatial signal contents from temporal signals. In the light of the massive evidence for complex interactions between implicit (non-conscious) and explicit (conscious) contents of representation, the code would have to be capable of making implicit (non-conscious) processes explicit. It would have to be capable of a progressively less and less arbitrary selection of temporal activity patterns in a continuously developing neural network structure identical to that of the human brain, from the synaptic level to that of higher cognitive functions. The code’s activation thresholds would depend on specific temporal signal coincidence probabilities, vary considerably with time and across individual experience data, and would therefore require dynamically adaptive computations capable of emulating the properties of individual human experience. No known machine or neural network learning approach has such potential. (shrink)