A mathematical problem iscomputable if it can be solved inprinciple by a computing device. Some common synonyms for“computable” are “solvable”,“decidable”, and “recursive”. Hilbert believedthat all mathematical problems were solvable, but in the 1930’sGödel, Turing, and Church showed that this is not the case. Thereis an extensive study and classification of which mathematicalproblems are computable and which are not. In addition, there is anextensive classification of computable problems into computationalcomplexity classes according to how much computation—as afunction of the size of the problem instance—is needed toanswer that instance. It is striking how clearly, elegantly, andprecisely these classifications have been drawn.

• 1. What can be computed in principle? Introduction and History
• 2. Turing Machines
  • 2.1 Universal Machines
  • 2.2 The Halting Problem
  • 2.3 Computable Functions and Enumerability
  • 2.4 The Unsolvability of the Halting Problem
• 3. Primitive Recursive Functions
  • 3.1 Recursive Functions
• 4. Computational Complexity: Functions Computable in Practice
  • 4.1 Reductions and Completeness
  • 4.2 Significance of Complexity
• Bibliography
• Academic Tools
• Other Internet Resources
• Related Entries

1. What can be computed in principle? Introduction and History

In the 1930’s, well before there were computers, variousmathematicians from around the world invented precise, independentdefinitions of what it means to be computable. Alonzo Church definedthe Lambda calculus, Kurt Gödel defined Recursive functions,Stephen Kleene defined Formal systems, Markov defined what became knownas Markov algorithms, Emil Post and Alan Turing defined abstractmachines now known as Post machines and Turing machines.

Surprisingly, all of these models are exactly equivalent: anythingcomputable in the lambda calculus is computable by a Turing machine andsimilarly for any other pairs of the above computational systems. Afterthis was proved, Church expressed the belief that the intuitive notionof “computable in principle” is identical to the above precise notions.This belief, now called the “Church-Turing Thesis”, is uniformlyaccepted by mathematicians.

Part of the impetus for the drive to codify what is computable camefrom the mathematician David Hilbert. Hilbert believed that all ofmathematics could be precisely axiomatized. Once this wasdone, there would be an “effective procedure”, i.e., an algorithm thatwould take as input any precise mathematical statement, and, after afinite number of steps, decide whether the statement was true or false.Hilbert was asking for what would now be called adecisionprocedure for all of mathematics.

As a special case of this decision problem, Hilbert considered thevalidity problem for first-order logic. First-order logic is amathematical language in which most mathematical statements can beformulated. Every statement in first-order logic has a precise meaningin every appropriate logical structure, i.e., it is true or false ineach such structure. Those statements that are true in everyappropriate structure are calledvalid. Those statements thatare true in some structure are calledsatisfiable. Notice thata formula, \(\varphi\), is valid iff its negation, \(\neg \varphi\), is notsatisfiable.

Hilbert called the validity problem for first-order logic, theentscheidungsproblem. In a textbook,Principles ofMathematical Logic by Hilbert and Ackermann, the authors wrote,“The Entscheidungsproblem is solved when we know a procedure thatallows for any given logical expression to decide by finitely manyoperations its validity or satisfiability.… Theentscheidungsproblem must be considered the main problem ofmathematical logic.” (Böerger, Grädel, & Gurevich1997).

In his 1930 Ph.D. thesis, Gödel presented a completeaxiomatization of first-order logic, based on thePrincipiaMathematica by Whitehead and Russell (Gödel 1930). Gödel proved hisCompleteness Theorem, namely that a formula is provable from the axiomsif and only if it is valid. Gödel’s Completeness theorem was astep towards the resolution of Hilbert’sentscheidungsproblem.

In particular, since the axioms are easily recognizable, and rulesof inference very simple, there is a mechanical procedure that can listout all proofs. Note that each line in a proof is either an axiom, orfollows from previous lines by one of the simple rules. For any givenstring of characters, we can tell if it is a proof. Thus we cansystematically list all strings of characters of length 1, 2, 3, and soon, and check whether each of these is a proof. If so, then we can addthe proof’s last line to our list of theorems. In this way, we can listout all theorems, i.e., exactly all the valid formulas of first-orderlogic, can be listed out by a simple mechanical procedure. Moreprecisely, the set of valid formulas is the range of a computablefunction. In modern terminology we say that the set of valid formulasof first-order logic isrecursively enumerable (r.e.).

Gödel’s Completeness theorem was not sufficient, however, togive a positive solution to theentscheidungsproblem. Given aformula, \(\varphi\), if \(\varphi\) is valid then the above procedure wouldeventually list it out and thus could answer, “Yes, \(\varphi\) is valid.”However, if \(\varphi\) were not valid then we might never find this factout. What was missing was a procedure to list out all the non-validformulas, or equivalently to list out all satisfiable formulas.

A year later, in 1931, Gödel shocked the mathematical world byproving his Incompleteness Theorem: there is no complete and computableaxiomatization of the first-order theory of the natural numbers. Thatis, there is no reasonable list of axioms from which we can proveexactly all true statements of number theory (Gödel 1931).

A few years later, Church and Turing independently proved that theentscheidungsproblem is unsolvable. Church did this by usingthe methods of Gödel’s Incompleteness Theorem to show that the setof satisfiable formulas of first-order logic is not r.e., i.e., theycannot be systematically listed out by a function computable by thelambda calculus. Turing introduced his machines and proved manyinteresting theorems some of which we will discuss in the next section.In particular, he proved the unsolvability of thehaltingproblem. He obtained the unsolvability of theentscheidungsproblem as a corollary.

Hilbert was very disappointed because his program towards a decisionprocedure for all of mathematics was proved impossible. However, as wewill see in more detail in the rest of this article, a vast amount waslearned about the fundamental nature of computation.

2. Turing Machines

In his 1936 paper, “On Computable Numbers, with an Application tothe Entscheidungsproblem”, Alan Turing introduced his machines andestablished their basic properties.

He thought clearly and abstractly about what it would mean for amachine to perform a computational task. Turing defined his machines toconsist of the following:

• a finite set, \(Q\), of possible states, because any devicemust be in one of finitely many possible states;
• a potentially infinite tape, consisting of consecutive cells,\(\sigma_{1}, \sigma_{2}, \sigma_{3}\), fromsome finite alphabet, \(\Sigma\);
  \((\Sigma\) may be any finite set containing at least two symbols. It isconvenient to fix \(\Sigma = \{0, 1, b\}\) consisting of the binaryalphabet plus the blank cell symbol. We usually assume that a finiteinitial segment of the tape contains binary symbols, and the rest isblank.)
• a read/write tape head, \(h \ge 1\), scanning tape cell\(\sigma_{h}\); and finally,
• a transition function, \(\delta : Q \times \Sigma \rightarrow Q\times \Sigma \times \{-1,0,1\}\).
  (The meaning of thetransition function is that from any given state, \(q\), looking atany given symbol, \(\sigma_{h}, \delta\) tells us the new state themachine should enter, the new symbol that should be written in thecurrent square, and the new head position, \(h' = h + d\), where \(d\in \{-1,0,1\}\) is the displacement given by \(\delta\).)

The linear nature of its memory tape, as opposed to random accessmemory, is a limitation on computation speed but not power: a Turingmachine can find any memory location, i.e., tape cell, but this may betime consuming because it has to move its head step by step along itstape.

The beauty of Turing machines is that the model is extremely simple,yet nonetheless, extremely powerful. A Turing machine has potentiallyinfinite work space so that it can process arbitrarily large inputs,e.g., multiply two huge numbers, but it can only read or write abounded amount of information, i.e., one symbol, per step. Even beforeTuring machines and all the other mathematical models of computationwere proved equivalent, and before any statement of the Church-Turingthesis, Turing argued convincingly that his machines were as powerfulas any possible computing device.

2.1 Universal Machines

Each Turing machine can be uniquely described by its transitiontable: for each state, \(q\), and each symbol, \(\sigma ,\delta(q,\sigma)\) is the new state, the new symbol, and thehead displacement. These transition tables, can be written as a finitestring of symbols, giving the complete set of instructions of eachTuring machine. Furthermore, these strings of symbols can be listed inlexicographic order as follows: \(M_{1},M_{2}, M_{3},\ldots\), where\(M_{i}\) is the transition table, i.e., the complete setof instructions, for Turing machine number \(i\). The transitiontable for \(M_{i}\) is the program for Turing machine\(i\), or more simply, the \(i\)^th program.

Turing showed that he could build a Turing machine, \(U\), thatwasuniversal, in the sense that it could run the program ofany other Turing machine. More explicitly, for any \(i\), and anyinput \(w, U\) on inputs \(i\) and \(w\) woulddo exactly what \(M_{i}\) would do on input \(w\), insymbols,

Turing’s construction of a universal machine gives the mostfundamental insight into computation: one machine can run any programwhatsoever. No matter what computational tasks we may need to performin the future, a single machine can perform them all. This is theinsight that makes it feasible to build and sell computers. Onecomputer can run any program. We don’t need to buy a new computer everytime we have a new problem to solve. Of course, in the age of personalcomputers, this fact is such a basic assumption that it may bedifficult to step back and appreciate it.

2.2 The Halting Problem

Because they were designed to embody all possible computations,Turing machines have an inescapable flaw: some Turing machines oncertain inputs never halt. Some Turing machines do not halt for sillyreasons, for example, we can mis-program a Turing machine so that itgets into a tight loop, for example, in state 17 looking at a 1 itmight go to state 17, write a 1 and displace its head by 0. Slightlyless silly, we can reach a blank symbol, having only blank symbols tothe right, and yet keep staying in the same state, moving one step tothe right, and looking for a “1”. Both of those cases of non-haltingcould be easily detected and repaired by a decent compiler. However,consider the Turing machine \(M_{F}\), which oninput “0”, systematically searches for the first counter-example toFermat’s last theorem, and upon finding it outputs the counter-exampleand halts. Until Andrew Wiles relatively recently proved Fermat’s LastTheorem, all the mathematicians in the world, working for over threecenturies, were unable to decide whether or not\(M_{F}\) on input “0” eventually halts. Now weknow that it never does.

2.3 Computable Functions and Enumerability

Since a Turing machine might not halt on certain inputs, we have tobe careful in how we define functions computable by Turing machines.Let the natural numbers, \(\mathbf{N}\), be the set\(\{0,1,2,\ldots \}\) and let us consider Turing machines as partialfunctions from \(\mathbf{N}\) to \(\mathbf{N}\).

Let \(M\) be a Turing machine and \(n\) a natural number.We say that \(M\)’s tapecontains the number\(n\), if \(M\)’s tape begins with a binaryrepresentation of the number \(n\) (with no unnecessary leading0’s) followed by just blank symbols from there on.

If we start the Turing machine \(M\) on a tape containing\(n\) and it eventually halts with its tape containing \(m\),then we say that \(M\) on input \(n\), computes \(m:M(n) = m\). If, when we start \(M\) oninput \(n\), it either never halts, or when it halts, its tapedoes not contain a natural number, e.g., because it has leading 0’s, ordigits interspersed with blank symbols, then we say that\(M(n)\) is undefined, in symbols: \(M(n)=\nearrow\). We can thusassociate with each Turing machine, \(M\), apartialfunction, \(M: \mathbf{N} \rightarrow \mathbf{N} \cup \{\nearrow\}\). We say thatthe function \(M\) istotal if for all\(n\in \mathbf{N}\), \(M(n) \in \mathbf{N}\), i.e., M\((n)\) is always defined.

Now we can formally define what it means for a set to berecursively enumerable (r.e.) which we earlier describedinformally. Let \(S \subseteq \mathbf{N}\). Then \(S\)is r.e. if and only if there is some Turing machine, \(M\), suchthat \(S\) is the image of the function computed by \(M\), insymbols,

Thus, \(S\) is r.e. just if it can be listed out by some Turingmachine. Suppose that \(S\) is r.e. and its elements areenumerated by Turing machine \(M\) as above. We can then describeanother Turing machine, \(P\), which, on input \(n\), runs\(M\) in a round-robin fashion on all its possible inputs untileventually \(M\) outputs \(n\). If this happens then\(P\) halts and outputs “1”, i.e., \(P(n)=1\). If\(n \not\in S\), then\(M\) will never output \(n\), so \(P(n)\) willnever halt, i.e., \(P(n)=\nearrow\).

Let the notation \(P(n)\downarrow\) mean that Turingmachine \(P\) on input \(n\) eventually halts. For a Turingmachine, \(P\), define \(L(P)\), thesetaccepted by \(P\), to be those numbers \(n\) such that\(P\) on input \(n\) eventually halts,

The above argument shows that if a set \(S\) is r.e. then it isaccepted by some Turing machine, \(P\), i.e., \(S = L(P)\). Theconverse of this statement holds as well. That is, \(S\) is r.e. ifand only if it is accepted by some Turing machine, \(P\).

We say that a set, \(S\), isdecidable if and only if thereis a total Turing machine, \(M\), that decides for all \(n \in\mathbf{N}\) whether or not \(n \in S\). Think of “1” as“yes” and “0” as “no”. For all\(n\in \mathbf{N}\), if \(n \in S\), then \(M(n) = 1\), i.e., \(M\) oninput \(n\) eventually halts and outputs “yes”, whereas if\(n \not\in S\), then \(M(n) = 0\), i.e., \(M\) on input \(n\)eventually halts and outputs “no”. Synonyms for decidableare:computable,solvable, andrecursive.

For \(S \subseteq \mathbf{N}\), thecomplement of\(S\) is \(\mathbf{N} - S\), i.e., the set of allnatural numbers not in \(S\). We say that the set \(S\) isco-r.e. if and only if its complement is r.e. If a set,\(S\), is r.e. and co-r.e. then we can list out all of itselements in one column and we can list out all of its non-elements in asecond column. In this way we can decide whether or not a givenelement, \(n\), is in \(S\): just scan the two columns andwait for \(n\) to show up. If it shows up in the first column then\(n \in S\). Otherwise it will show up in the secondcolumn and \(n \not\in S\).In fact, a set is recursive iff it is r.e. and co-r.e.

2.4 The Unsolvability of the Halting Problem

Turing asked whether every set of natural numbers is decidable. Itis easy to see that the answer is, “no”, by the following countingargument. There are uncountably many subsets of \(\mathbf{N}\), butsince there are only countably many Turing machines, there can be onlycountably many decidable sets. Thus almost all sets areundecidable.

Turing actually constructed a non-decidable set. As we will see, hedid this using a diagonal argument. The diagonal argument goes back toGeorg Cantor who used it to show that the real numbers are uncountable.Gödel used a similar diagonal argument in his proof of theIncompleteness Theorem in which he constructed a sentence, \(J\),in number theory whose meaning could be understood to be, “\(J\)is not a theorem.”

Turing constructed a diagonal halting set, \(K\), asfollows:

That is, \(K\) consists of those Turing machines thateventually halt when input their own programs.

It is not hard to see that \(K\) is r.e. Suppose for the sakeof a contradiction that \(K\) is also co-r.e., and let \(d\)be the number of a Turing machine that accepts the complement of\(K\). That is, for any \(n\),

But consider what happens when we substitute \(d\) for\(n\) in the above equation:

However, the definition of \(K\) tells us that:

Thus we have that

which is a contradiction. Thus our assumption that \(K\) isco-r.e. is false. Thus \(K\) is not recursive. It follows that itis not a computable problem to be given a Turing machine and its inputand to decide whether or not the Turing machine will eventually halt onthat input, i.e., the halting problem is unsolvable.

3. Primitive Recursive Functions

We next define the class ofPrimitive Recursive Functions.This is a very interesting class of functions described a in paper by Skolem (1923) and used byGödel inhis proof of the Incompleteness Theorem. We are interested infunctions \(f\) from \(\mathbf{N}^{r}\) to\(\mathbf{N}\), for \(r = 0, 1, 2,\ldots\) . Here\(r\) is called the arity of the function \(f\), i.e., thenumber of arguments that it takes. Gödel started with three verysimple functions, the initial functions, and two natural closureoperations, composition and primitive recursion, each of which takesome already defined functions and use them to define a new one. Wenext explain his definitions in detail. This section is technical andcan be safely skipped. The important idea is that the primitiverecursive functions comprise a very large and powerful class ofcomputable functions, all generated in an extremely simple way.

We begin with the threeinitial primitive recursivefunctions:

• \(\zeta\), the zero function of arity \(0, \zeta\)( ) \(= 0\);
• \(\eta\), the identity function of arity \(1, \eta(n) = n\); and,
• \(\sigma\), the successor function of arity \(1, \sigma(n) = n +1\).

Now consider the following two operations:

• Composition: if \(f\) is a primitive recursivefunction of arity \(a\), and \(g_{1}, \ldots ,g_{a}\) are primitiverecursive functions of arities \(r_{1}, \ldots ,r_{a}\), and \(k\in\mathbf{N}\), then the following is a primitive recursive function ofarity \(k\):\[h(x_{1}, \ldots ,x_{k}) = f(g_{1}(w_{1}), \ldots ,g_{a}(w_{a})),\]

  where each \(w_{i}\) is a list of \(r_{i}\) arguments, perhaps withrepetition, from \(x_{1}, \ldots ,x_{k}\); and,

• Primitive recursion: if \(f\) and \(g\)are primitive recursive functions of arity \(k\) and \(k+2\),respectively, then there is a primitive recursive function, \(h\),of arity \(k+1\) satisfying the following conditions: \[\begin{align} h(0,x_{1},\ldots ,x_{k}) &= f(x_{1},\ldots ,x_{k}); \text{ and,} \\ h(n+1,x_{1},\ldots ,x_{k}) &= g(h(n,x_{1},\ldots ,x_{k}), n,x_{1},\ldots ,x_{k}).\end{align}\]

Here composition is the natural way to combine functions, andprimitive recursion is a restricted kind of recursion in which\(h\) with first argument \(n+1\) is defined in terms of\(h\) with first argument \(n\), and all the other argumentsunchanged.

Define theprimitive recursive functions to be the smallestclass of functions that contains the Initial functions and is closedunder Composition and Primitive Recursion. The set of primitiverecursive functions is equal to the set of functions computed usingbounded iteration (Meyer & Ritchie 1967), i.e. the set offunctions definable in the language Bloop from (Hofstadter 1979).

The primitive recursive functions have a very simple definition andyet they are extremely powerful. Gödel proved inductively thatevery primitive recursive function can be simply represented infirst-order number theory. He then used the primitive recursivefunctions to encode formulas and even sequences of formulas by numbers.He finally used the primitive recursive functions to compute propertiesof the represented formulas including that a formula is well formed and that asequence of formulas is a proof.

It takes a long series of lemmas to show how powerful the primitiverecursive functions are. The following are a few examples showing thataddition, multiplication, and exponentiation are primitiverecursive.

Define the addition function, \(P(x,y)\), asfollows:

(Note that this fits into the definition of primitive recursionbecause the function \(g(x_{1},x_{2},x_{3}) = \eta(\sigma(x_{1}))\) isdefinable from the initial functions \(\eta\) and \(\sigma\) bycomposition.)

Next, define the multiplication function,\(T(x,y)\), as follows:

Next, we define the exponential function,\(E(x,y)\). (Usually \(0^{0}\) isconsidered undefined, but since primitive recursive functions must betotal, we define \(E\)(0,0) to be 1.) Sinceprimitive recursion only allows us to recurse on the first argument,we use two steps to define the exponential function:

Finally we can define \(E(x,y) = R(\eta(y),\eta(x))\) bycomposition. (Recall that \(\eta\) is the identity function so thiscould be more simply written as \(E(x,y) = R(y,x)\).)

The exponential function, \(E\), grows very rapidly, forexample, \(E\)(10,10) is ten billion, and \(E\)(50,50) isover \(10^{84}\) (and thus significantly more than the estimatednumber of atoms in the universe). However, there are much fastergrowing primitive recursive functions. As we saw, \(E\) wasdefined from the slowly growing function, \(\sigma\), using threeapplications of primitive recursion: one for addition, one formultiplication, and then one more for exponentiation. We can continueto apply primitive recursion to build a series of unimaginably fastgrowing functions. Let’s do just one more step in the series definingthe hyper-exponential function, \(H(n,m)\) as 2to the 2 to the 2 to the … to the \(m\), with a tower of\(n\) 2s. \(H\) is primitive recursive because it can bedefined from \(E\) using one more application of primitiverecursion:

Thus \(H(2,2) = 2^{4} = 16, H(3,3) = 2^{256}\) is more than\(10^{77}\) and comparable to the number of atoms in the universe. Ifthat’s not big enough for you then consider \(H(4,4)\). To writethis number in decimal notation we would need a one, followed by morezero’s than the number of particles in the universe.

3.1 Recursive Functions

The set of primitive recursive functions is a huge class ofcomputable functions. In fact, they can be characterized as the set offunctions computable in time that is some primitive recursive functionof \(n\), where \(n\) is the length of the input. Forexample, since \(H(n,n)\) is a primitiverecursive function, the primitive recursive functions include all ofTIME[\(H(n,n)\)]. (See the next section for adiscussion of computational complexity, including TIME.) Thus, theprimitive recursive functions include all functions that are feasiblycomputable by any conceivable measure of feasible, and much beyondthat.

However, the primitive recursive functions do not include allfunctions computable in principle. To see this, we can again usediagonalization. We can systematically encode all definitions ofprimitive recursive functions of arity 1, calling them\(p_{1}, p_{2}, p_{3}\),and so on.

We can then build a Turing machine to compute the value of thefollowing diagonal function, \(D(n) = p_{n}(n) + 1\).

Notice that \(D\) is a total, computable function from\(\mathbf{N}\) to \(\mathbf{N}\), but it is not primitiverecursive. Why? Suppose for the sake of a contradiction that \(D\)were primitive recursive. Then \(D\) would be equal to\(p_{d}\) for some \(d\in \mathbf{N}\). But it would then follow that

which is a contradiction. Therefore, \(D\) is not primitiverecursive.

Alas, the above diagonal argument works on any class of totalfunctions that could be considered a candidate for the class of allcomputable functions. The only way around this, if we want allfunctions computable in principle, not just in practice, is to add somekind of unbounded search operation. This is what Gödel did toextend the primitive recursive functions to the recursivefunctions.

Define the unbounded minimization operator, \(\mu\), as follows. Let\(f\) be a perhaps partial function of arity \(k+1\). Then\(\mu[f\)] is defined as the following function of arity k. Oninput \(x_{1}, \ldots ,x_{k}\) do thefollowing:

Thus if \(f(i,x_{1},\ldots ,x_{k}) = 1\), and for all \(j \lt i,f(j,x_{1},\ldots ,x_{k})\) is defined, but not equal to 1, then \(\mu[f](x_{1}, \ldots ,x_{k}) = i\). Otherwise \(\mu[f](x_{1}, \ldots,x_{k})\) is undefined.

Gödel defined the set ofRecursive functions to be theclosure of the initial primitive recursive functions under composition,primitive recursion, and \(\mu\) . With this definition, the Recursivefunctions are exactly the same as the set of partial functionscomputable by the Lambda calculus, by Kleene Formal systems, by Markovalgorithms, by Post machines, and by Turing machines.

4. Computational Complexity: Functions Computable in Practice

During World War II, Turing helped design and build a specializedcomputing device called the Bombe at Bletchley Park. He used the Bombeto crack the German “Enigma” code, greatly aiding theAllied cause [Hodges, 1992]. By the 1960’s computers were widelyavailable in industry and at universities. As algorithms weredeveloped to solve myriad problems, some mathematicians and scientistsbegan to classify algorithms according to their efficiency and tosearch for best algorithms for certain problems. This was thebeginning of the modern theory of computation.

In this section we are dealing with complexity instead ofcomputability, and all the Turing machines that we consider will halton all their inputs. Rather than accepting by halting, we will assumethat a Turing machine accepts by outputting “1” and rejects byoutputting “0”, thus we redefine the set accepted by a total machine,\(M\),

The time that an algorithm takes depends on the input and themachine on which it is run. The first important insight in complexitytheory is that a good measure of the complexity of an algorithm is itsasymptotic worst-case complexity as a function of the size of theinput, \(n\).

For an input, \(w\), let \(n = \lvert w\rvert\) be the length of\(w\). Following [Hartmanis, 1989] we say that a Turing machine\(M\)runs in time \(T(n)\) if for all \(w\) of length \(n,M(w)\) takes at most \(T(n)\) steps and then halts. This is calledworst-case complexity because \(T(n)\) must be as large as the timetaken by any input of length \(n\).

For any function \(T : \mathbf{N} \rightarrow \mathbf{N}\), let

Alan Cobham and Jack Edmonds identified the complexity class, \(\P\), ofproblems recognizable in some polynomial amount of time, as being anexcellent mathematical wrapper of the class of feasible problems—those problems all of whose moderately-sized instances can befeasibly recognized,

Any problem not in \(\P\) is certainly not feasible. On the other hand,natural problems that have algorithms in \(\P\), tend to eventually havealgorithms discovered for them that are actually feasible.

Many important complexity classes besides P have been defined andstudied; a few of these are \(\NP\), \(\PSPACE\), and \(\EXPTIME\).\(\PSPACE\) consists of those problems solvable using some polynomialamount of memory space. \(\EXPTIME\) is the set of problems solvable intime \(2^{p(n)}\) for some polynomial, \(p\).

Perhaps the most interesting of the above classes is NP:nondeterministic polynomial time. The definition comes not from a realmachine, but rather a mathematical abstraction. A nondeterministicTuring machine, \(N\), makes a choice (guess) of one of twopossible actions at each step. If, on input \(w\), some sequenceof these choices leads to acceptance, then we say that\(\mathbf{N}\) accepts \(w\), and we say thenondeterministic time taken by \(\mathbf{N}\) on input\(w\), is just the number of steps taken in the sequence thatleads to acceptance. A nondeterministic machine is not charged for allthe other possible choices it might have made, just the single sequenceof correct choices.

NP is sometimes described as the set of problems, \(S\), thathave short proofs of membership. For example, suppose we are given alist of \(m\) large natural numbers: \(a_{1},\ldots ,a_{m}\), and a target number,\(t\). This is an instance of the Subset Sum problem: is there asubset of the \(m\) numbers whose sum is exactly \(t\)? Thisproblem is easy to solve in nondeterministic linear time: for each\(i\), we guess whether or not to take \(a_{i}\).Next we add up all the numbers we decided to take and if the sum isequal to \(t\) then accept. Thus the nondeterministic time islinear, i.e., some constant times the length of the input, \(n\).However there is no known (deterministic) way to solve this problem intime less than exponential in \(n\).

4.1 Reductions and Completeness

There has been a large study of algorithms and the complexity ofmany important problems is well understood. In particular reductionsbetween problems have been defined and used to compare the relativedifficulty of two problems. Intuitively, we say that \(A\) isreducible to \(B\) \((A \le B)\) if thereis an easy-to-compute transformation, \(\tau\), that maps instances of \(A\) toinstances of \(B\) in a way that preserves membership, i.e.,\(\tau\)(w) \(\in B \Leftrightarrow\) w \(\in A\).

Remarkably, a high percentage of naturally occurring computationalproblems turn out to be complete for one of the above classes. (Aproblem, \(A\), is complete for a complexity class \(C\) if\(A\) is a member of \(C\) and all other problems \(B\)in \(C\) are no harder than \(A\), i.e., \(B \le A\). Two complete problems for the same class have equivalentcomplexity.)

The reason for this completeness phenomenon has not been adequatelyexplained. One plausible explanation is that natural computationalproblems tend to be universal in the sense of Turing’s universalmachine. A universal problem in a certain complexity class can simulateany other problem in that class.

In 1971, Cook proved SAT is NP complete [Cook, 1971]. Shortly later, Karp showed that many important combinatorial problems were alsoNP complete, thus establishing the importance of the class NP [Karp, 1972].

Our definition of reduction above lacked precision, just saying that the mapping \(\tau\) must byeasy-to-compute. The reductions that Karp used were polynomial-time reductions, i.e., \(\tau\) iscomputable in polynomial time. Since then, many researchers have observed that natural problemsremain complete for natural complexity classes under surprisingly weakreductions including logspace reductions [Jones, 1973], first-order reductions [Immerman, 1999],projections [Valiant, 1982], and first-order projections [Immerman, 1999].

With a very few exceptions, when a natural problem is in NP, it turns out to be either NP complete,or in P. People wondered whether this was always the case. Ladner proved that if P \(\ne\) NP, thenthere is an intermediate problem \(I\) that is in NP but not in P and not NP complete [Ladner, 1975].

Ladner’s proof method is called delayed diagonalization. He generalized his result to show that forany two well-behaved complexity classes, C, E such that C is strictly contained in E, there is anintermediate class, D such that C is strictly contained in D and D is strictly contained in E. Thusthe ordering of complexity classes is dense.

However, these intermediate problems don’t tend to show up. This phenomenon has received a great deal ofattention recently via the dichotomy conjecture of Feder and Vardi [Feder and Vardi, 1999].Schaefer introduced this work with an insightful paper in which he studied allvariants of the boolean satisfiability problem [Schaefer, 1978]. He proved that each such problem was either NP complete or in P, thus Ladner’s intermediate problemscannot occur among such satisfiability problems. Since there were just these two possibilities,Schaefer called this a dichotomy.

In fact, if one looks closer, all of Schaefer’s satisfiability problems are either NP complete, Pcomplete, \(\oplus\)L complete, NL complete, L complete, or trivial [Allender et al., 2009]. That is thenon-trivial problems in P may be P complete, or complete for one of these three complexity classes within P. In otherwords, if we look closer, the NP/P dichotomy phenomenon problem is really a “multi-chotomoy”phenomenon, namely all non-trivial satisfiability problems are complete for one of five well-knowncomplexity classes.

Feder and Vardi studied Schaefer’s dichotomy and conjectured that it holds for all finite-domainConstraint Satisfaction Problems (CSP) [Feder and Vardi, 1999].A finite-domain CSP, C, consists of a finite domain, D, and a finite set of relations \(R_1,\ldots , R_k\) over D. An instance of C consists of a set of variables, \(v_1, \ldots v_n\)and a conjunction of atoms \(\varphi \equiv \bigwedge R_i(v_{j_1}, \ldots)\).The answer to the instance, \(\varphi\), is “yes”, i.e., \(\varphi \in C\) iff there is an assignment of thevariables to elements of the domain, D, so that \(\varphi\) is satisfied.

With domains of size 2, a CSP problem is just a satisfiability problem, so Schaefer’s theoremalready established the Feder and Vardi conjecture for this case.A simple instance of a CSP with domain size 3 is the 3COLOR problem for undirected graphs. Given such agraph, G, can the vertices of G be colored one of three colors so that no two adjacent vertices havethe same color? To write this as a CSP, let \(D = \{R,Y,B\}\) be a set of three distinct colors andlet the relation \(N\) be the not-equal relation on \(D\). Then from \(G=(V,E)\) the instance of 3COLORis\[ \varphi_G \quad = \quad \bigwedge_{(u,v)\in E} N(u,v)\; .\]Note that \(\varphi_G\) says that whenever there is an edge in \(G\) between vertices \(u\) and \(v\), then \(u\)and \(v\) are assigned different colors.

Feder and Vardi’s conjecture led to an extremely productive research program. In particular, a rich algebraic theory of CSPs was developed in a number of papers starting with[Jeavons et al. 1997]; see [Bulatov, 2018] for a survey.Eventually, by applying and advancing this algebraic theory, Bulatov and Zhuk independently provedthe Feder andVardi conjecture [Bulatov, 2017; Zhuk, 2017].

4.2 Significance of Complexity

The reason that the class NP is sowell studied is that a large number of important practical problems areNP complete, including Subset Sum. None of these problems is known tohave an algorithm that is faster than exponential time, although someNP-complete problems admit feasible approximations to theirsolutions.

A great deal remains open about computational complexity. We know thatstrictly more of a particular computational resource lets us solvestrictly harder problems, e.g. \(\TIME[n]\) is strictly contained in\(\TIME[n^{1.01}]\) and similarly for \(\SPACE\) and othermeasures. However, the trade-offs between different computationalresources is still quite poorly understood. It is obvious that \(\P\)is contained in \(\NP\). Furthermore, \(\NP\) is contained in\(\PSPACE\) because in \(\PSPACE\) we can systematically try everysingle branch of an \(\NP\) computation, reusing space for thesuccessive branches, and accepting if any of these branches lead toacceptance. \(\PSPACE\) is contained in \(\EXPTIME\) because if a\(\PSPACE\) machine takes more than exponential time, then it hasexactly repeated some configuration so it must be in an infiniteloop. The following are the known relationships between the aboveclasses:

However, while it seems clear that \(\P\) is strictly contained in\(\NP\), that \(\NP\) is strictly contained in \(\PSPACE\), and that\(\PSPACE\) is strictly contained in \(\EXPTIME\), none of theseinequalities has been proved. In fact, it is not even known that\(\P\) is different from \(\PSPACE\), nor that \(\NP\) is differentfrom \(\EXPTIME\). The only known proper inclusion from the above isthat \(\P\) is strictly contained in \(\EXPTIME\). The remainingquestions concerning the relative power of different computationalresources are fundamental unsolved problems in the theory ofcomputation.

The following diagram maps out all thecomplexity classes we have discussed and a few more as well. The diagram comes from work inDescriptive Complexity [Immerman, 1999] which shows that all important complexity classes have descriptive characterizations. Fagin began this field by proving that NP = SO\(\exists\), i.e., a property is in NP iff it is expressible in second-order existential logic[Fagin, 1974].

Vardi and the author of this entry later independently proved that P =FO(LFP): a property is in P iff it is expressible in first-order logicplus a least fixed-point operator (LFP) which formalizes the power todefine new relations by induction. A captivating corollary of this isthat P = NP iff SO = FO(LFP). That is, P is equal to NP iff everyproperty expressible in second order logic is already expressible infirst-order logic plus inductive definitions. (The languages inquestion are over finite ordered input structures. See [Immerman,1999] for details.)

The World of Computability and Complexity

The top right of the diagram shows the recursively enumerable (r.e.)problems; this includes r.e.-complete problems such as the haltingproblem (Halt). On the left is the set of co-r.e. problems includingthe co-r.e.-complete problem \(\overline{{\rm Halt}}\) -- the set ofTuring Machines that never halt on a given input. We mentioned at theend of Section 2.3 that the intersection of the set of r.e problemsand the set of co-r.e problems is equal to the set of Recursiveproblems. The set of Primitive Recursive problems is a strict subsetof the Recursive problems.

Moving toward the bottom of the diagram, there is a region marked witha green dotted line labelled “truly feasible”. Note thatthis is not a mathematically defined class, but rather an intuitivenotion of those problems that can be solved exactly, for all theinstances of reasonable size, within a reasonable amount of time,using a computer that we can afford. (Interestingly, as the speed ofcomputers has dramatically increased over the years, our expectationof how large an instance we should be able to handle has increasedaccordingly. Thus, the boundary of what is “trulyfeasible” changes more slowly than the increase of computerspeed might suggest.)

As mentioned before, P is a good mathematical wrapper for the set offeasible problems. There are problems in P requiring \(n^{1,000}\)time for problems of size \(n\) and thus not feasible. Nature appearsto be our friend here, which is to say naturally occurring problems inP favor relatively simple algorithms, and “natural”problems tend to be feasible. The number of steps required forproblems of size \(n\) tends to be less than \(c n^k\) with smallmultiplicative constants \(c\), and very small exponents, \(k\), i.e.,\(k\leq 2\).

In practice the asymptotic complexity of naturally occurring problemstends to be the key issue determining whether or not they arefeasible. A problem with complexity \(17n\) can be handled in under aminute on modern computers, forevery instance of size abillion. On the other hand, a problem with worst-case complexity\(2^n\) cannot be handled in our lifetimes forsome instance ofsize a hundred.

As discussed, natural problems tend to be complete for importantcomplexity classes, namely the ones in the diagram and only a very fewothers. This fascinating phenomenon means that algorithms andcomplexity are more than abstract concepts; they are important at apractical level. We have had remarkable success in proving that ourproblem of interest is complete for a well-known complexity class. Ifthe class is contained in P, then we can usually just look up a knownefficient algorithm. Otherwise, we must look at simplifications orapproximations of our problem which may be feasible.

There is a rich theory of the approximability of NP optimizationproblems (See [Arora & Barak, 2009]). For example, the Subset Sumproblem mentioned above is an NP-complete problem. Most likely itrequires exponential time to tell whether a given Subset Sum problemhas an exact solution. However, if we only want to see if we canreach the target up to a fixed number of digits of accuracy, then theproblem is quite easy, i.e., Subset Sum is hard, but very easy toapproximate.

Even the r.e.-complete Halting problem has many important feasiblesubproblems. Given a program, it is in general not possible to figureout what it does and whether or not it eventually halts. However,most programs written by programmers or students can be automaticallyanalyzed, optimized and even corrected by modern compilers and modelcheckers.

The class NP is very important practically and philosophically. It isthe class of problems, \(S\), such that any input \(w\) is in \(S\)iff there is a proof, \(p(w)\), that \(w\in S\) and \(p(w)\) is notmuch larger than \(w\). Thus, very informally, we can think of NP hasthe set of intellectual endeavors that may be in reach: if we find theanswer to whether \(w \in S\), we can convince others that we havedone so.

The boolean satisfiability problem, SAT, was the first problem provedNP complete [Cook, 1971], i.e., it is a hardest NP problem. The factthat SAT is NP complete means that all problems in NP are reducible toSAT. Over the years, researchers have built very efficient SATsolvers which can quickly solve many SAT instances – i.e., find asatisfying assignment or prove that there is none-- even for instances with millions of variables. Thus, SAT solvers are being used as general purposeproblem solvers. On the other hand, there are known classes of small instances for which currentSAT solvers fail. Thus part of the P versus NP question concerns the practical and theoreticalcomplexity of SAT [Nordström, 2015].

There is an extensive theory of computational complexity. This entrybriefly describes the area, putting it into the context of thequestion of what is computable in principle versus in practice. Forreaders interested in learning more about complexity, there areexcellent books, for example, [Papadimitriou, 1994] and [Arora andBarak, 2009]. There is also the entry onComputational Complexity Theory.

Bibliography

• Allender, E., M. Bauland, N. Immerman, H. Schnoor and H. Vollmer, 2009, “The Complexity of Satisfiability Problems: Refining Schaefer’sTheorem”,Journal of Computer and System Science 75(4): 245–254.
• Arora, Sanjeev and Boaz Barak, 2009,Computational Complexity:A Modern Approach, New York: Cambridge University Press.
• Böerger, Egon, Erich Grädel, and Yuri Gurevich, 1997,The Classical Decision Problem, Heidelberg: Springer.
• Bulatov, Andrei, 2017, “A Dichotomy Theorem for NonuniformCSPs”,IEEE 58th Annual Symposium onFoundations of Computer Science, 319–330.
• –––, 2018, “Constraint SatisfactionProblems: Complexity and Algorithms”,SIGLOG News 4(5):3–24.
• Church, Alonzo, 1933, “A Set of Postulates for theFoundation of Logic (Second Paper)”,Annals ofMathematics (Second Series), 33: 839–864.
• –––, 1936a, “An Unsolvable Problem ofElementary Number Theory,”American Journal ofMathematics, 58: 345–363.
• –––, 1936b, “A Note on theEntscheidungsproblem,”Journal of Symbolic Logic, 1:40–41; correction 1, 101–102.
• Cobham, Alan, 1964, “The Intrinsic Computational Difficulty ofFunctions,”Proceedings of the 1964 Congress for Logic,Mathematics, and Philosophy of Science, Amsterdam: North-Holland, pp. 24–30.
• Cook, Stephen, 1971, “The Complexity of Theorem ProvingProcedures,”Proceedings of the Third Annual ACM STOCSymposium, Shaker Heights, Ohio, pp. 151–158.
• Davis, Martin, 2000,The Universal Computer: the Road fromLeibniz to Turing, New York: W. W. Norton & Company.
• Edmonds, Jack, 1965, “Paths, Trees and Flowers,”CanadianJournal of Mathematics, 17: 449–467.
• Enderton, Herbert B., 1972,A Mathematical Introduction toLogic, New York: Academic Press.
• Fagin, Ronald, 1974, “Generalized First-Order Spectra andPolynomial-Time Recognizable Sets,” inComplexity ofComputation, R. Karp (ed.),SIAM-AMS Proc, 7:27–41.
• Feder, Tomas and Moshe Vardi, 1999, “The ComputationalStructure of Monotone Monadic SNP and Constraint Satisfaction: A StudyThrough Datalog and Group Theory”,SIAM Journal ofComputing 28: 57–104.
• Garey, Michael and David S. Johnson, 1979,Computers andIntractability, New York: Freeman.
• Gödel, Kurt, 1930, “The Completeness of the Axioms of theFunctional Calculus,” in van Heijenoort 1967: 582–591.
• –––, 1931, “On Formally Undecidable Propositionsof Principia Mathematica and Related Systems I,” in van Heijenoort,1967: 592–617.
• Hartmanis, Juris, 1989, “Overview of computational ComplexityTheory” in J. Hartmanis (ed.),Computational Complexity Theory,Providence: American Mathematical Society, pp. 1–17.
• Hilbert and Ackermann, 1928/1938,Grundzüge dertheoretischen Logik, Springer. English translation of the 2ndedition:Principles of Mathematical Logic, New York: ChelseaPublishing Company, 1950.
• Hodges, Andrew, 1992,Alan Turing: the Enigma, London: RandomHouse.
• Hofstadter, Douglas, 1979,Gödel, Escher, Bach: an EternalGolden Braid, New York: Basic Books.
• Hopcroft, John E., 1984, “Turing Machines”,ScientificAmerican, 250(5): 70–80.
• Immerman, Neil, 1999,Descriptive Complexity, New York: Springer.
• Jeavons, P.G., D.A. Cohen and M. Gyssens, 1997, “Closure Properties ofConstraints”,Journal of the ACM, 44: 527–548.
• Jones, Neil, 1973, “Reducibility Among Combinatorial Problems in Logn Space”,Proc. Seventh Annual Princeton Conf. Info. Sci. and Systems, 547–551.
• Karp, Richard, 1972, “Reducibility Among CombinatorialProblems,”, inComplexity of Computations, R.E. Millerand J.W. Thatcher (eds.), New York: Plenum Press, pp. 85–104.
• Kleene, Stephen C., 1935, “A Theory of Positive Integers inFormal Logic,”American Journal of Mathematics, 57:153–173, 219–244.
• –––, 1950,Introduction to Metamathematics,Princeton: Van Nostrand.
• Ladner, Richard, 1975, “On the structure of polynomial time reducibility”,Journal of the ACM, 155–171.
• Levin, Leonid, 1973, “Universal searchproblems,”Problemy Peredachi Informatsii, 9(3):265–266; partial English translation in B.A.Trakhtenbrot, 1984,“A Survey of Russian Approaches to Perebor (Brute-force Search)Algorithms,”IEEE Annals of the History of Computing,6(4): 384–400.
• Markov, A.A., 1960, “The Theory ofAlgorithms,”American Mathematical Society Translations(Series 2), 15: 1–14.
• Meyer, Albert and Dennis Ritchie, 1967, “The Complexity ofLoop Programs,”Proceedings of the 22nd National ACMConference, Washington, D.C., 465–470.
• Nordström, Jakob, 2015, “On the Interplay Between ProofComplexity and SAT Solving,” SIGLOG News, 2(3): 18–44.
• Papadimitriou, Christos H., 1994,ComputationalComplexity, Reading, MA: Addison-Wesley.
• Péter, Rózsa. 1967,Recursive Functions,translated by István Földes, New York: AcademicPress.
• Post, Emil, 1936, “Finite Combinatory Processes –Formulation I,”Journal of Symbolic Logic, 1: 103–105.
• Rogers, Hartley Jr., 1967,Theory of Recursive Functions andEffective Computability, New York: McGraw-Hill.
• Schaefer, Thomas, 1978, “The Complexity of SatisfiabilityProblems”,Proceedings of the Tenth Annual ACM STOCSymposium, 216–226.
• Skolem, Thoralf, 1923, “The foundations of elementaryarithmetic established by means of the recursive mode ofthought,” in van Heijenoort 1967: 302–33.
• Turing, A. M., 1936–7, “On Computable Numbers, with anApplication to the Entscheidungsproblem”,Proceedings of theLondon Mathematical Society, 2(42): 230–265[Preprint available online].
• Valiant, Leslie, 1982, “Reducibility By Algebraic Projections”,L’Enseignement mathematique, 28(3–4): 253–268.
• van Heijenoort, Jean, (ed.), 1967,From Frege To Gödel: ASource Book in Mathematical Logic, 1879–1931, Cambridge, Massachusetts:Harvard University Press.
• Whitehead, Alfred North and Bertrand Russell, 1910–1913,Principia Mathematica, first edition, Cambridge: CambridgeUniversity Press.
• Zhuk, Dmitriy, 2020, “A Proof of CSP Dichotomy Conjecture”, Journal of the ASM, 30: 1–78.

Academic Tools

	How to cite this entry.
	Preview the PDF version of this entry at theFriends of the SEP Society.
	Look up topics and thinkers related to this entry at the Internet Philosophy Ontology Project (InPhO).
	Enhanced bibliography for this entryatPhilPapers, with links to its database.

Other Internet Resources

• Descriptive Complexity: a webpage describing research in Descriptive Complexity which isComputational Complexity from a Logical Point of View (with a diagramshowing the World of Computability and Complexity). Maintained by NeilImmerman, University of Massachusetts, Amherst.
• Mass, Size, and Density of the Universe, from the National Solar Observatory/Sacramento Peak.

Related Entries

Church, Alonzo: logic, contributions to |Church-Turing Thesis |computational complexity theory |Gödel, Kurt |quantum theory: quantum computing |recursive functions |set theory |Turing, Alan |Turing machines