The English mathematician Alan Mathison Turing (1912-1954) is well-known for his key role in the development of computer science, but he also made important contributions to the foundations of mathematics, numerical analysis, cryptography, quantum computing and biology. In the present paper we focus exclusively on the influence of Turing on computability and complexity theory, leaving aside other aspects of his work even within computer science, most notably his contribution to the birth of the digital computer and artificial intelligence.


Turing was an important player in the settlement of the decidability issue, which led naturally to the study of the complexity of decidable problems, i.e., once it was proved that there are problems unsolvable by a computer, research turned to the question of “how long would it take to solve a decidable problem?” This is an exciting research field with lots of open questions. In this paper, we try to give a gentle introduction to the historical perspective of the search for efficient computing and its limitations.


Gottfried W. Leibniz (1646-1716) was an important mathematician, philosopher, jurist and inventor, whose dream was to devise an automatic reasoning machine, based on an alphabet of unambiguous symbols manipulated by mechanical rules, which could formalize any consistent linguistic or mathematical system. He produced a calculus ratiocinator, an algebra to specify the rules for manipulating logical concepts. More than a century later, George Boole (1815-1864) and Augustus De Morgan (1806-1871) converted the loose ideas of Leibniz into a formal system, Boolean algebra, from which Gottlob Frege (1848-1925) finally produced the fully developed system of axiomatic predicate logic.


Frege went on to prove that all the laws of arithmetic could be logically deduced from a set of axioms. He wrote a two-volume book with the formal development of the foundations of arithmetic, and when the second volume was already in print, Frege received the celebrated letter from Bertrand Russell (1872-1970) showing his theory was inconsistent. The counterexample was the paradox of extraordinary sets. A set is defined to be extraordinary if it is a member of itself, otherwise it is called ordinary. Is the set of all ordinary sets also ordinary? (see Doxiadis, Papadimitriou, Papadatos and di Donna, 2009, pp. 169 to 171 for a particular charming account of the effect of Russell's letter to Frege).


Frege's work was the spark for 30 years of research on the foundations of mathematics, and the end of the 19th c. and beginning of the 20th c. witnessed strong mathematical, philosophical and personal battles between members of the intuitionist and formalist European schools (Davis, 2000; Doxiadis, Papadimitriou, Papadatos and di Donna, 2009).


To better frame further developments, let us recall some notions. A formal system is a language, a finite set of axioms, and a set of inference rules used to derive expressions (or statements) from the set of axioms; an example is mathematics with the first-order logic developed by Frege. A system is said to be complete if every statement can be proved or disproved; otherwise the system is said to be incomplete. A system is said to be consistent if there is not a step-by-step proof within the system that yields a false statement.


A system is said to be decidable if, for every statement, there exists an algorithm to determine whether the statement is true.


In 1928, at the International Congress of Mathematicians in Bologna, David Hilbert (1862-1943), a leading figure in the formalist school, presented to his fellow mathematicians three problems, the second of which would have a big impact on the development of computer science: the Entscheidungsproblem. In English, it is named the decision problem, and it can be formulated as follows: “provide a method that, given a first-order logic statement, would determine in a finite number of steps whether the statement is true". In other words, the Entscheidungsproblem asks for the existence of a finite procedure that could determine whether a statement in mathematics is true of false. Hilbert was convinced that the answer would be yes, as mathematics should be complete, consistent and decidable.


In 1936 Turing completed the draft of his paper "On Computable Numbers, with an Application to the Entscheidungsproblem", where he proposed a formal model of computation, the a-machine, today known as the Turing machine (TM), and he proved that any function that can be effectively computed (in Hilbert’s sense) by a human being could also be mechanically calculated in a finite number of steps by a mechanical procedure, namely the TM. Turing used his formalism to define the set of computable numbers, those reals for which their ith decimal can be computed in a finite number of steps. The number of computable numbers is countable but the number of reals is uncountable, so most of the reals are not computable. Some well-known computable numbers are 1/7, π and e.


In his model, Turing introduced two essential assumptions, the discretization of time and the discretization of the state of mind of a human calculator. A TM consisted of an infinite tape divided into squares, a finite input on a finite alphabet, and a write-read head that could be in a finite number of states representing those of the human calculator's brain (Davis, 2000; Moore and Mertens, 2011). The TM was a theoretical model of a stored-in program machine. An outstanding achievement of Turing was the concept of Universal Turing Machine (UTM). Given the codified description of a TM as input, the UTM is able to simulate the computation of that machine and write the result. Hence, the UTM can simulate any other Turing machine, thus opening the way to digital computers.


Relying on his UTM, Turing made a decisive contribution to computability, namely he produced a problem that was undecidable: the halting problem. It can be stated as follows: “Given a codified description of a TM and an input to it, decide if the UTM will halt”. The proof was a mimic of Geodel's incompleteness one, where a diagonalization argument produces a paradox (see Davis, 2000, chapter 7 for a nice informal explanation). Note that the halting problem is a counterexample, a negative solution to the Entscheidungsproblem1.


Turing’s PhD. thesis extended Gödel's incompleteness theorem by proving that when new axioms are added to an incomplete formal system the system remains incomplete (Turing, 1939). A very important contribution of that work was the Oracle Turing-machine model. In the words of Turing: “Let us suppose we are supplied with some unspecified means of solving number-theoretical problems, a kind of oracle as it were. We shall not go any further into the nature of this oracle apart from saying that it can't be a machine”.


Emil Post (1897-1954) realized that Turing's oracle machine had important implications for computability, as it could be used to compare the relative difficulty of problems; thus he defined the concept of Turing-reducibility (T-reducibility). Given problems P1 and P2, P1 is said to be Turing-reducible to P2 (P1 ≤T P2) if P2 can be used to construct in a finite number of steps, a program to solve P1. Note that if P1 ≤T P2 and P2 is decidable then P1 is also decidable, and if P1 ≤T P2 and P1 is undecidable, then P2 is also undecidable. Therefore, T-reducibility can be used to enlarge the class of know undecidable problems.


We have seen that the work of Turing and others let us determine, for any given problem, whether there is an algorithm to solve it (i.e., the problem is decidable) or not. Let us turn into the realm of solvable problems, and ask the question of how long it takes to solve a given decidable problem. It may seem that this is a pure technological issue, however we will see that there are problems for which today's computers would take more that the age of universe to find a solution, when the input to the problem is a bit large.


The time complexity of a problem with input x is a measure of the number of steps that an algorithm will take to solve it, as a function of the size of the input |x| = n. Let us consider the worst-case complexity, where among all the possible inputs of size n, we take the one that behaves worst in terms of the number of steps performed by the algorithm. As an example, consider the school algorithms for multiplying two integers a and b of sizes na and nb, respectively, size measured as the number of digits in the binary expression (i.e., na = log2a), and let n = max{na, nb}, then the worst-case complexity of the algorithm is T(n) = O(n2).2

For decidable problems, the time complexity expression has a tremendous impact on the running time of an algorithm. Figure 1 (taken from Moore and Mertens, 2011) is an indication of the running time of different worst-case complexity figures, assuming a processor can solve an instance of size n = 1 in 10−3 seconds, which is consistent with today’s technology. Note that an algorithm that solves a problem with complexity O(2n), if given an input of size n = 90, may yield the output after the universe would be finished (again, assuming today's technological level).


Let us try to get a feeling for the time-complexity of some problems. Given an n x n matrix M = (mij), its determinant is defined by the Leibniz formula


where σ is one permutation from the symmetric group of permutations Sn, and sgn (σ) is the sign of the permutation. A similar associate value of a square matrix is the permanent, which is defined


For example if


then det(M) = m11 . m22– m12 . m21 , while perm(M) = m11.m22 + m12.m21.


A direct implementation of the definition yields an O(n!) algorithm for both problems. However, by using the LU decomposition by Gauss and Turing, the determinant of an n x n matrix can be computed in O(n3) steps, see for example in Cormen, Leiserson, Rivest and Stein (2001), while the complexity of computing the permanent seems to be much more difficult (Valiant, 1979). Recently D. Glynn has obtained a deterministic bound of O(n2n) to the complexity of the permanent (Glynn, 2010). Notice that if M1 and M2 are square matrices then det(M1M2) = det(M1) x det(M2), while perm(M1M2) ≠ perm(M1) x perm(M2).


A problem is said to be feasible if there exists an algorithm that solves it with polynomial time-complexity. All other decidable problems are said to be unfeasible, which does not imply that in the near or distant future some problems may turn into feasible.


A particularly interesting kind of problems are the combinatorial optimization problems, where for any instance x and a solution sx for that instance, there is a cost function k(x, sx) ∈ ℝ+ and the objective is to find the sx* that optimizes (maximizes or minimizes) k(x, sx) over all possible solutions sx3. Let Opt(x) denote the cost of an optimal solution.


For example, consider the chromatic number problem of a graph: “Given as input a graph G = (V, E), find the minimum number of different colors needed to have a valid coloring of the vertices in V”, where a valid coloring of G is an assignment of labels χ : V → {1, 2, …, k}, each integer representing a color, such that for any (u, v) Є E, χ(u) ≠ χ(v). Notice that, for any input G and solution χ, Opt(G) is a valid coloring with minimum number of colors.


A fascinating line of research in theoretical computer science started in the mid 1980’s, which led to fruitful results, namely Interactive Proofs. In this section, we aim to give a brief intuitive introduction to the topic, in particular to Zero-Knowledge Proofs (ZKP) and Probabilistically Checkable Proofs (PCP). For the interested reader, we recommend Chapter 11 in Moore and Mertens (2011) and Chapters 8, 9 and 11 in Arora and Barak (2009). The topic has spanned 26 years, with numerous papers and fruitful applications in various fields, such as cryptography and approximation algorithms, among others.


The basic idea is how one researcher (the prover P) can convince another researcher (the verifier V )6 that he has a correct proof to a difficult theorem by only showing to V a few random bits of the proof, in such a way that at the end V is convinced that the proof is correct without having any insight into how it works.


To grasp the concept of zero-knowledge proof, let us start with the very simple illustrative example from Quisquater, Quisquater, Quisquater, Quisquater, Guillou, Guillou, Guillou, Guillou, Guillou, Guillou, and Berson (1989)7. There is a cave with two paths A and B, which are connected at their ends by a secret passage (see Figure 5). To cross that passage one must know the magic words. In our case, P wants to convince V that he knows the magic words without telling them to V. They agree on the following protocol: V will remain outside of the cave, so he cannot see which path P takes. When P arrives at the end of the cave, V tells P which path to return along, and V enters the cave to make sure P is returning for the path he indicated. The probability that P took the path V asks him to return is 1/2, therefore if the experiment is repeated a sufficiently large number of times, and each time P returns by the correct path, with probability 1 P must know the magic words to cross the cave, and V is convinced that P knows them.


ZKP are a particular case of the most general Interactive Proofs Systems, introduced concurrently in Babai (1985) and Goldwasser, Micali and Rackoff (1989)8. Technically the word proof refers to a randomized interactive protocol between P and V, where P has unlimited computational capabilities and tries to convince V of the truth of a certain statement. Loosely speaking, the two characteristics that an interactive protocol must have to be an interactive proof is that an honest V should always be convinced by an honest P , but a cheater P should have a very small probability of convincing an honest V that a false statement is true. The interactive proof system is zero-knowledge if V is not going to learn anything from the interaction with P. In the previous example, V becomes convinced that P knows the magic words to cross between the two paths.

Let us describe a more interesting example. Consider a given graph G = (V, E), where V = n and E = m. As we saw before, to decide whether G has chromatic number 3 is an NP-complete problem, therefore in general it is not a feasible problem to solve for large values of n. In this setting, P wants to convince V that he has a valid 3-coloring of G, without revealing the coloring. This example is from Goldreich, Micali and Wigderson (1991). At each iteration of the protocol, V only has access to the colorings at the ends of a single edge he chooses at the iteration. The protocol is the following: First P selects a valid 3-coloring (for every (, ) ⋲ E, u and v must have different colors) and generates all 3! = 6 permutations of valid 3-colorings for G; let C be the set of all 6 valid colorings. For n3 iterations, at each iteration i, P chooses with probability 1/6 a new coloring ci ⋲ C , V selects an edge and verifies that the edge is correctly colored. Assume that G has a valid 3-coloring (see for example Figure 3). Notice that if V chooses the same edge (u, v) at two different iterations, the colors assigned to each vertex may be different, as at each iteration P chooses a new random coloring, therefore V will not be able to learn a valid coloring for the whole G. On the other hand, if G is not 3-colorable, at each round, at least one edge will have the same color for both vertices, therefore the probability that V will discover a wrong edge is at least 1/m per round. As m ≤ n2, after n3 iterations with probability tending to 1, V will discover that G is not 3-colorable.


Technically the way P shows the colors to V is a bit more complicated, using a one-way-function. One-way-functions are functions that can be easily computed but are hard (exponential time) to invert. A trivial ex­ample of one-way-function is integer multiplication: it is easy to multiply m = al x a2 x ... x an, however as we already mentioned, there is no known polynomial-time algorithm for factorizing m. Another more interesting ex­ample of a one-way-function is the discrete logarithm: “Given n-bit integers x, y, z, find whether there exists an integer w such that y = xw mod z”. Given x, w and z, it is easy to compute y = f (x, w, z) = xw mod z, but it is conjectured that finding f −1(y) takes exponential time. One-way-functions are in standard use in cryptography.


By applying reductions to the 3-colorability problem, it was shown in Goldreich, Micali and Wigderson (1991) that under the assumption of the existence of one-way-functions, every problem in class NP has a zero-knowledge proof. In fact, if we denote IP the class of problems having an interactive protocol, it is known that IP, as a complexity class, contains far more difficult problems than NP (under the hypothesis P≠NP) (Shamir, 1992). Computing the permanent of a matrix is a prob­lem in the class IP, which means that even under the hypothesis P=NP, it would remain a hard problem.


The culmination of interactive proof systems research was one of the most beautiful and deep theorems in computer science, the PCP-theorem. Although the Gödel prize 2001 was shared by Arora and Safra (1998), Arora, Lund, Motwani, Sudan and Szegedy (1998) and Feigue, Goldwasser, Lovasz, Safra, and Szegedy (1996) for their contribution to Probabilistically Checkable Proofs and the PCP-theorem, many of the techniques and ideas are due to a much larger number of researchers (see for example Johnson (1992) for an extensive historical account, and Chapter 16 in Williamson and Smoys (2010) for further recent work using the PCP-theorem to obtain inapproximability results).


The rough idea of probabilistically checkable proof systems is: “Given a conventional mathematical proof in which a mistake could be hidden in any equation, transform the proof in such a way that the mistake is spread almost everywhere”. This kind of proof is denoted a holographic proof. A PCP system for an NP problem encodes the witness to the problem in a way such that V can verify probabilistically the witness by looking only to a few of its bits, so that if it is true V accepts with probability 1, and if it is false V accepts with probability < 1/2.


The PCP-theorem states that holographic proofs exist for problems in NP, i.e., that any problem in NP has a polynomial length probabilistically checkable proof, where V flips O(log n) random coins and need to look only at O(1) bits of the proof.


Contrary to Hilbert’s Entscheidungsproblem, it remains an open problem to decide whether the truncated Entscheidungsproblem is feasible, i.e., it remains open to decide whether P=NP. It follows from the arguments in the present paper that a positive answer to that question may answer all seven remaining open millennium problems.


At least there are 54 existing bogus proofs of the P=NP question. Of them, 26 “proving” the equality, 24 “proving” the strict inclusion, and 3 “proving” that the P=NP question is itself undecidable. For further details see Woeginger. Most scientists working in complexity theory believe that P ≠ NP, but there are some top scientists in the field that disagree with the majority, see for instance Lipton’s blog.


The aim of this manuscript was not to review the complexity field or the status and future of the P=NP question. As we pointed out, there are some outstanding textbooks dealing with all the past, present and future attempts and results in complexity. Our only incursion into the areas of modern com­plexity has been the topic of interactive proofs, and this is because we think that it is a natural continuation to the truncated Entscheidungsproblem, in the sense that PCP basically tells us how to convince our colleagues that we have a correct proof without giving away any real details. Moreover, it turns out that PCP is a strong characterization of NP problems. Could we one day even have a practical holographic way to check proofs?


Complexity theory has studied different models of computation (Turing machine with bounded number of steps, Boolean circuits, quantum algorithms, randomized algorithms), the complexity of measuring different parameters (space, number of iterations, depth of circuits), and several measures of complexity (worst case, average, smoothed). All this work has created a whole cosmos of about 500 complexity classes (Aaronson, Kuperberg and Granade). For most of them, strict relations are not known and, at the end, the main issue boils down to the basic intuition by Kurt Gödel in 1954.


We tried to convey the idea that this is one of the deepest questions of today’s science, affecting not only computer science, mathematics and physics, but also biology, sociology, economics and most human activities. We see this broad coverage of this question as a direct consequence of Turing’s way of looking through the algorithmic lens to problems in different disciplines, from cryptography and physics to biology. The spread of modern technologies is accelerating the need for an algorithmic view of today’s social, economical, cultural, and political interactions, leading directly to the question P=NP? For an excellent survey of the role of the algorithmic view into the activities within the modern world, we recommend the book by Easley and Kleinberg (Easley and Kleinberg, 2010).