Using some of my own work, I set out to clear up a few relevant concepts from theoretical computer science and computational cognitive science that can help to build conceptual hygiene and immunity against hyped claims about “AI” capabilities.

[A version of this blogpost also appeared as a thread on social media. I transformed it to a blogpost for easier reading.]

We start with a definition of the concept of `algorithm’: “An effective procedure—also called algorithm—for a function $ψ: I → O$, is a finite step-by-step procedure that when followed mindlessly will transform any input $i ∈ I$ into the required output $ψ(i)$” (van Rooij, 2008, p. 941). Note that this definition mentions “mindlessly”. This means that no gaps in the steps or humans-in-the-loop are allowed.

Functions that have no algorithms that compute them are called uncomputable. Some functions are computable, but not tractable (more on this in a moment). Assuming that cognition is (explainable as) a form of computation, it follows that cognitive functions ⊆ tractable functions ⊆ computable functions.

Tractability is a stronger constraint than computability. It requires that an algorithm runs in a reasonable amount of time, using reasonable amounts of resources. This informal idea can be formalized in different ways. The classical formalisation is polynomial-time computability (class $P$).

“To see that the definition has merit, consider Table 1 [which] shows that an exponential function, like $O(2^{|i|})$, grows much faster than a polynomial function, like $O(|i|^2)$. [A]s $|i|$ grows, the exponential running time gets unrealistic very fast (…)” (van Rooij, 2008, p. 948)

A more lenient formalisation of tractability is the concept of fixed-parameter tractability (class $FPT$). This formalisation of tractability allows for running times to grow, say, exponentially in a confined way$–$i.e., only in the parameter $k$, assumed to be much smaller than the input size $n$$–$provided that the remainder of the running time is polynomial in the input size $n$.

“More formally, a function $ψ_T$ is fixed-parameter tractable for a parameter $k$ if there exists at least one algorithm that computes $ψ_T$ in time $O(f(k)|i|^\alpha)$, where $f$ is a function depending only on the parameter $k$ and $\alpha$ is a constant” (van Rooij, 2008, p. 957) Table 3 above from van Rooij, 2008 illustrates fixed-parameter tractable running times.

Proving a function $ψ_T$ is tractable, be it $P$ or $FPT$, is conceptually straightforward: provide at least 1 algorithm for $ψ_T$ that runs in polynomial time or fpt-time, respectively. Proving intractability instead is harder. It is often done with a technique called reduction (See Fig. 6 from van Rooij, 2008 below for an illustration and explanation).

I give intuitive explanations of reduction$–$be it polynomial-time or parameterized$–$in several of my papers and also of course in our textbook, titled Intractability and Cognition: A guide to classical and parameterized complexity analysis.

But my favourite illustration is the one below in Fig. 3 from Rich, Blokpoel, de Haan & van Rooij (2020). In this video I also explain the basic idea of ‘reduction’, using the same illustration (at min 15:57).

Now we are ready to dive deeper into these concepts and distinctions: What is the difference between algorithm, heuristic, and approximation? Why do people feel compelled to blur the distinctions? As we’ll see, intractability plays a role.

In my work, as in theoretical computer science, we distinguish between (exact) algorithms, heuristics (no guarantees), and approximation algorithm (approx. guarantees). Clear distinctions are relevant in many contexts, for instance this one in cognitive science. (van Rooij, 2026)

We already started off, at the top of this post, with a definition of algorithm for a function (see here for a different notion). Important features of such algorithms include: 1) finite, 2) step-by-step procedure, 3) unambiguous, 4) guaranteed correct. Here ‘correct’ is not meant normatively, but merely means the output matches the to-be-computed function (whatever that function is).

As we saw above, some functions are uncomputable or intractable, and hence have no algorithm or no tractable agorithm. In such cases, often people (incl. scientists) propose to instead use or postulate ‘heuristics‘ (i.e., inexact algorithms) to compute these functions.

Stop and Think $–$ What slip may be occuring here? Do you notice? (see also van Rooij et al., 2012, p. 475).

Note that a tractable heuristic $H$ cannot compute an uncomputable or intractable $f$. Here is a proof sketch: Assume $H$ would compute $f$ tractably, then $H$ would be an algorithm (not a mere heuristic) and thus $f$ would be computable and tractable. QED

Furthermore note that, in fact, $H$ must fail on infinitely many inputs of $f$. Do you see why? Here a proof sketch: Let $H$ fail on only a finite subset of all possible inputs of intractable $f$. Then we could have a lookup table (= finite) for that subset if inputs. Let us call it $L$. Then $L + H$ combined make a tractable exact algorithm for $f$. But this contradicts that no such algorithm exists. QED

So heuristics make no promises. They may succeed on some inputs, they may fail on many inputs. There are no guarantees, they may fail massively, terribly, and often. Using heuristics is more like faith or hope than computer science or engineering.

So what about approximation algorithms? A lot depends on what we mean by ‘approximation’. Approximating what and how? Often this remains underspecified and claims of approximation are regularly made not with proofs but by handwaving.

Long ago, I noticed that in computer science ‘approximation’ is often defined w.r.t. some optimal value. In cognitive science this type of value-approximation has limited theoretical import. Instead, structure-approximation is often more relevant. Yet, AI approaches in/to cognitive science tend to ignore this.

The Tables 1 and 2 below from van Rooij and Wareham (2012) illustrate the difference between these two notions of approximation.

As it turns out, value- versus structure-approximability are fully dissociable. In other words, an output may be close to the optimal value, yet arbitrarily off in terms of structure, and vice versa, an output may be close to the required structure, yet arbitrarily off in terms of value. See illustrations in the figures below from van Rooij and Wareham (2012).

One upshot is that it really matters what kind of approximation $–$ with what kinds of guarantees (e.g., value, structure, how close) $–$ one is making claims about. One cannot just claim “this intractable function $f$ is approximable with this $A_{approx}$“, without precise definitions and formal proof.

What are your intuitions about how often an intractable function may be tractably approximable? Pick one of the below options:

a) always
b) often
c) sometimes
d) seldom
e) never

The answer is definitely not ‘always’. It all depends on how approximation is defined. If the error margin can be large and/or grow with input size, then the answer is ‘sometimes’. However, if the error margin is small and/or a constant, then the answer is ‘seldom’ or ‘never’. Well-behaved approximations are constant-additive approximations. All other types of approximations become increasingly bad as input size scales up.

It has been proven that no neighborhood-searchable intractable problems have well-behaved, constant-additive approximations. See, for instance, the below Lemma proven in van Rooij et al. (2012).

In other words, any intractable (formally, $NP$-hard) problem that allows for local hill climbing cannot be globally well-approximated. Well, isn’t that the opposite of what many people think and claim 🙃

So how does all this help build immunity to hyped claims about “AI” capabilities?

It helps when we realize that …

“(…) no computationally tractable account exists to date for substantive and domain-general cognitive capacities, such as reasoning, communication, decision-making, planning, analogizing, categorization, and concept formation (van Rooij et al., 2019). Moreover, there is no good reason to believe that such tractable accounts will be forthcoming via machine learning (van Rooij, Guest, et al., 2024) or otherwise (Rich et al., 2021).

$–$quote from van Rooij & Guest (2026)

… and that no appeal to heuristics or approximation is going to change this.

References

• Kwisthout, J., Wareham, T., & van Rooij, I. (2011). Bayesian intractability is not an ailment that approximation can cure. Cognitive Science, 35(5), 779-784.
• Rich, P., Blokpoel, M., de Haan, R., & van Rooij, I. (2020). How intractability spans the cognitive and evolutionary levels of explanation. Topics in Cognitive Science, 12, 1382–1402.
• Rich, P., de Haan, R., Wareham, T., & van Rooij, I. (2021). How hard is cognitive science? Proceedings of the Annual Meeting of the Cognitive Science Society, 43.
• van Rooij, I. (2008). The Tractable Cognition thesis. Cognitive Science, 32, 939-984.
• van Rooij, I., Blokpoel, M., Kwisthout, J., Wareham, T. (2019). Intractability and Cognition: A guide to classical and parameterized complexity analysis. Cambridge: Cambridge University Press.
• van Rooij, I., Wright, C. & Wareham, H.T. (2012). Intractability and the use of heuristics in psychological explanations. Synthese. 187,471-487.
• van Rooij, I. & Wareham, T. (2012). Intractability and approximation of optimization theories of cognition. Journal of Mathematical Psychology, 56,232-247.
• van Rooij, I., Guest, O., Adolfi, F. G., de Haan, R., Kolokolova, A., & Rich, P. (2024). Reclaiming AI as a theoretical tool for cognitive science. Computational Brain & Behavior.
• van Rooij, I., & Guest, O. (2026). Combining Psychology With Artificial Intelligence: What Could Possibly Go Wrong? Current Directions in Psychological Science, 35(3), 193-200.

More resources

Interested to learn more? Maybe check out the Computational Complexity for Cognitive Scientists blogpost.

If you enjoy watching videos, you may also appreciate this talk about ‘Why cognitive scientists should care about computational complexity’ and/or this talk about ‘How hard is cognitive science?’ and/or this talk about ‘Reclaiming AI as a theoretical tool for cognitive science’.

Acknowledgements

Banner image by Gundula Vogel on Pexels.