Reference. Isomorphismes de graphes en temps quasi-polynomial (d'après Babai et Luks, Weisfeiler-Leman...) [helfgott2017]

12 October 2017
Harald Andrés Helfgott
10.48550/arXiv.1701.04372
http://arxiv.org/abs/1701.04372

Backlinks

Note. Computation, cognition and language [001E]

27 April 2026

Our earlier conclusions (A model of computation) might be summarised as making the following conjecture: physically plausible models of computation do not differ in the problems they can solve in polynomial time.

What has this to do with language? To a certain extent, the argument must be reconstructed, but its rough outlines are clear.

A first premiss is the so-called Cobham–Edmonds thesis.

Claim. Cobham–Edmonds thesis

27 April 2026
J.P. Loo

A function is feasibly computable if and only if some machine with polynomial runtime computes it (Cobham, Difficulty, Edmonds, Paths).

The Cobham–Edmonds thesis is only meaningful relative to a model of computation. But, if the van Emde Boas invariance thesis is correct, any reasonable model of computation will yield the same class of feasibly computable functions.

I shall, at this point, make a

Distinction. Conjectures and heuristics

27 April 2026
J.P. Loo

By conjecture, I mean a claim that is thought to straightforwardly be true, but for which we have no proof. For instance, Fermat’s last theorem was long a conjecture. By heuristic, I mean a claim counterexamples to which are accepted but which is thought generally to be at least approximately true. For instance, a useful heuristic in most engineering problems is to assume that relativistic effects are negligible; this is not true e.g. for GPS but is (at least approximately) true e.g. for most architectural purposes.

The Cobham–Edmonds thesis might seem to admit obvious counterexamples. For instance, an algorithm that takes $Θ (n^{2^{100}})$ time seems obviously infeasible. (For that runtime to be meaningful, it would have to be associated with some privileged subset of the ‘reasonable’ machine-class above; a good example is e.g. physically instantiated computers.) Less obviously, there is some reason to suspect that some problems that likely have no polynomial-time algorithm are feasible. In this case, we might nevertheless hold that, most of the time, the Cobham–Edmonds thesis is correct. For instance, there are surprisingly few ‘galactic’ algorithms, i.e. algorithms with polynomial asymptotic runtime that in practice are unusable; see e.g. Helfgott (Isomorphismes de graphes en temps quasi-polynomial (d'après Babai et Luks, Weisfeiler-Leman...)), Helfgott (Isomorphismes de graphes en temps quasi-polynomial (d’après Babai et Luks, Weisfeiler-Leman, ...)), and Lipton and Regan (David Johnson). We can therefore provisionally take the Cobham–Edmonds thesis to be a (defeasible) heuristic in the sense above.

What has this to do with language or cognition? There are, broadly, I think, two sorts of argument that relate asymptotic analysis to language.

Argument. The conceptual argument for asymptotic analysis of language

27 April 2026
J.P. Loo

Certain processes are constitutive of human language: production, comprehension and acquisition. These are cognitive processes that map from inputs to outputs—e.g. from acoustic or visual signals to representation of linguistic information; they are ipso facto comptuations.

Ristad (Game: 1) seems to offer something like this argument.

So do Clark and Lappin (Nativism: § 4.1) in the context of language acquisition.

[T]he child is, among other things, an information processing system, and is subject to the laws that govern computational systems. By studying the theoretical bounds on learning systems, we can make important inferences about the limiting conditions of the empirical question. To take a simple analogy, the problem of determining how birds fly is an empirical matter, but it is also clear that the principles of aerodynamics are highly relevant to this study. The bird is subject to the laws of physics, and no plausible account will violate those laws. We can reject out of hand any explanation that does not conform to the principles of aerodynamics.

The invitation, then, is to reject out of hand any account of language or linguistic phenomena that does not conform, putatively, to the laws of computation, whence asymptotic analysis.

Argument. The physicalist argument for asymptotic analysis of language

27 April 2026
J.P. Loo

The physicalist argument proceeds in four steps, the latter three from Rooij et al. (Cognition: 14). First, we should study in terms of cognitive processes (e.g. acquisition and production). Second, postulation of some cognitive capacity entails commitment to some explanation as to how that capacity is realised. Third, physically feasible explanations of cognition must be ‘computable and tractable’. Fourth, by the invariance and Cobham–Edmonds thesis, such explanations must (to a first approximation) be in polynomial time.

For the sake of argument, I will assume that these arguments are right, and that, therefore, ‘language computations’ are amenable to asymptotic analysis.

Is the application of asymptotic analysis to cognition and language an idealisation? First, I shall give an example of computational analysis that plausibly is not an idealisation.

Let us suppose, with Searle (Rediscovery: 200), that

[T]here [is] some description of the brain such that under that description you could do a computational simulation of the operations of the brain…given Church's thesis that anything that can be given a precise enough characterization as a set of steps can be simulated on a digital computer…in the same sense in which weather systems, the behavior of the New York stock market, or the pattern of airline flights over Latin American can.

Turing (Computability: § 11) showed that no Turing machine decides the Entscheidungsproblem. If we follow Searle’s rendering of Church’s thesis, it follows that the brain does not solve the Entscheidungsproblem either. I suggest there is no obvious idealisation here. (Of course, the argument might be false; but on its intended reading, it should be read as approximately false in the way idealisations usually are.) In other words, a fairly natural computationalist view is that these results from computability theory apply straightforwardly to computation generally, and, therefore, to cognition—and so to language computations.

However, in a considerable number of the arguments to follow, some antecedent assumptions seem to be false, and, therefore, the arguments will have to be parsed as idealisations. To say that the antecedent assumptions are false is not to deny computationalism. Suppose we are given a learning task over some stream of data $x_{1}, x_{2}, x_{3}, . . .$ (e.g. linguistic input). It may turn out that the probability distributions from which $x_{1}$ and $x_{2}$ , for instance, are drawn are not independent. For simplicity, however we may assume that $x_{1}, . . .$ are i.i.d. variables; making this assumption, we may find some asymptotic bound on the learning task. There is nothing inherently objectionabfle about the i.i.d. assumption, but it must be assessed as an idealised antecedent assumption, in addition to the computational model of language computations supposed.