There are two main areas of interest in the field of theory of computation. The first area is computability theory, which provides the tools to classify problems in those that are solvable and those that are not. The second area is complexity theory, which deals with the classification of problems according to their computational complexity. In other words, it categorizes problems as easy ones or hard ones. The scopes of computability and complexity theory seem to be delimited by their definition, but these two areas are clearly related. For example, let's imagine that we have determined that a problem is solvable and an algorithm that solves it is given. The algorithm may be so expensive (in terms of computational resources) that in practice the problem remains unsolvable. Hence, we come down to the question: given a certain input to a problem for which is known to be solvable, and an algorithm for it, how much resources will it take to solve it?
Languages and decidability
In theoretical computer science, a problem is formally represented as a language, which is a set of strings defined over some alphabet. Thus, in this context, the terms problem and language are often interchangeable. Formal languages allow us for a rigorous and precise analysis of the computational complexity of the problems they represent.
Now, let's say we take a particular string from the set of all possible strings defined over the alphabet, a language is decidable if we can answer "yes" or "no" to the question: Is the string in the language? More formally, given a particular string over all possible strings, and a Turing machine that decides a language over the same input alphabet –a Turing machine that answers “yes” or “no” for the given decision problem–, a precise analysis can be made over the input and the description of the Turing machine in order to determine the amount of time or space required to arrive to the two possible outcomes: the answer is “no” or the answer is “yes”. One can ask: what if the string is not in the language? In this case, because the problem is decidable, the Turing machine will reject the input and answer “no”, otherwise it may loop indefinitely (which is equivalent to not having an algorithm for the problem). This fact highlights the restriction in the analysis of computational complexity only to those problems that are decidable.
Figure 1 shows the relationship between some of the relevant concepts in the area of computational complexity. Essentially, complexity classes are used to categorize set of solvable (decidable) problems according to their computational difficulty. A complexity class is defined by several parameters [3]: the model of computation (i.e. a Turing machine), the mode of computation (deterministic and nondeterministic), and a bound (which usually is a function of the length of the input) on the amount of a particular resource (such as time or space) that an algorithm may use [4]. Time and space are then defined as the number of steps and the number of tape cells used in a computation by a Turing machine, respectively.
Figure 1. What is Computability Complexity Theory? (click to enlarge)
Time complexity
Decision problems can be classified by the time required to solve them. The definition of time complexity is the following:
"The time complexity of a deterministic Turing machine M is the function ƒ: N → N, where ƒ(n) is the maximum number of steps that M uses on any input of length n. If ƒ(n) is the running time of M, we say that M runs in time ƒ(n) and that M is an ƒ(n) time Turing machine" [5].
The running time of an algorithm is estimated on a reasonable large input by using asymptotic analysis and it is expressed using asymptotic notation or big-O notation. This form of analysis represents a convenient way of estimation because it only considers the highest term of the expression for the running time of the algorithm, which dominates the other terms on large inputs.
The class P
The class P is the set of languages that are decided in polynomial time by a single-tape deterministic Turing machine. This class of problems are important in the theory of computational complexity because [5]:
- P is invariant for all models of computation that are polynomially equivalent to the deterministic single-tape Turing machine.
- P roughly corresponds to the class of problems that are realistically solvable on a computer.
In other words, P does not depend on the model of computation and all problems in P are not only theoretically, but also practically solvable. Whether or not the running time is practical depends on the degree of the polynomial, however, “once a polynomial time algorithm has been found for a problem that formerly appeared to require exponential time, some key insight into it has been gained, and further reductions in its complexity usually follow, often to the point of actual practical utility” [5].
One example of a problem that is in P is PATH. Given a directed graph G, the PATH problem is to determine whether a directed path exists from any given two vertices that are in G. The proof that PATH is in P is by construction. The Turing machine M that computes PATH works as follows:
M = “On input ‹G, s, t› where G is a directed graph with nodes s and t:
- Place a mark on node s.
- Repeat the following until no additional nodes are marked:
- Scan all the edges of G. If an edge (a, b) is found going from a marked node a to an unmarked node b, mark node b.
- If t is marked, accept. Otherwise, reject.”
Now, by analyzing each of the stages (1-4) of M, it can be verified that M runs in polynomial time. Stage 1 and 4 runs in O(1), while stage 3 runs at most n times, where n is the number of nodes in G. Thus, the machine runs in O(1) + O(1) + O(n) = O(n), a polynomial time in the size of G.
The class NP
The class NP is the set of languages that are decided in polynomial time by a nondeterministic Turing machine, or more formally, the set of all problems that have polynomial time verifiers, which means that, for a given particular instance of a problem for which the answer is known to be “yes”, there is a computation that runs in polynomial time that verifies it [5]. Having this notion of “polynomial time verifiers”, there can be a nondeterministic Turing machine that nondeterministically runs the verifier on all possible strings. If any branch in the computation is valid, the machine accepts, otherwise, if no branch is valid, the machine rejects. One can say that this is, in general, a brute-force search algorithm that runs in parallel.
Every decision problem solvable by a polynomial time deterministic algorithm is also solvable by a polynomial time nondeterministic algorithm. To prove this, one can construct a nondeterministic machine that uses the polynomial time deterministic algorithm as a polynomial time verifier [1].
The Hamiltonian Path (HAMPATH) problem is an example of a problem in NP. For a given graph G = (V, E), a Hamiltonian path in G is a simple path that includes all the vertices of G. The HAMPATH problem consists on determining whether or not G contains a Hamiltonian path. A nondeterministic algorithm for HAMPATH can be easily obtained by giving a nondeterministic Turing machine that guesses all possible paths in G and checks whether each of the potential path is a Hamiltonian path.
The question of whether P = NP
For many years, researchers have dedicated a lot of effort to investigate the question of whether P = NP. This question is one of the greatest unsolved problems in theoretical computer science and contemporary mathematics. In fact, many people work under the assumption that P ≠ NP because, despite the efforts of many persisting researchers, no polynomial time deterministic algorithm has been found for any problem in NP. However, nobody has proved or disproved this conjecture.
An important discovery made independently in the early 70’s by Stephen Cook and Leonid Levin has been fundamental this prominent question. Nonetheless, before going into the details of their work, it is necessary to introduce a couple of important concepts for understanding the relationship between two problems in terms of their computational difficult. They also help to distinguish those problems whose individual complexity is related to that of its entire class.
The first concept is completeness. In complexity theory, completeness is a term used to describe a problem that is “one of the hardest” or “the most representative” problem in its class. In the class NP, an NP-complete problem is a problem that is “just as hard” as any other problem in NP. Formally, a problem A is NP-complete if:
- A is in NP.
- Every problem in NP is reducible to A.
The second condition of the definition of NP-completeness introduces another important concept, reducibility. There are many types of reductions; however, the one that is of interest in the theory of NP-completeness is that of a polynomial time reduction or polynomial transformation. Very informally, a polynomial transformation of two problems (or languages) is a function f that maps an instance of the first problem into an instance of the second in polynomial time.
Polynomial transformations provide the means for converting any algorithm that solves the second problem into a corresponding algorithm that solves the first problem. More importantly, if the solution to the second problem runs in polynomial time, then the solution to the first problem will use polynomial time as well. A problem that satisfies the second condition of NP-completeness, but not necessarily the first one is known as NP-hard. More formally, a problem is NP-hard if all problems in NP are polynomial time reducible to it, even though it may not be in NP itself [5]. This means that a NP-hard problem is “at least as hard as the hardest problems in NP”.
The most important consequence of the definition of NP-completeness is that if a polynomial time algorithm can be found for a NP-complete problem, then every problem in NP can be solved in polynomial time as well, and therefore P = NP. In order to prove that a problem is NP-complete one should show that it is in NP and that some known NP-complete problem is reducible to it. The first condition can be easily met by giving a non-deterministic polynomial time algorithm that solves the problem. The hard part is to satisfy the second condition, which requires writing the polynomial transformation that maps a known NP-complete problem into the problem we are trying to show as NP-complete. As a side note, it is useful to know that the “polynomial transformability” relation is transitive and that a polynomial transformation between two problems may actually consists of several intermediate reductions involving other problems.
It can be easily seen that in order to use this approach, one would need to have at least one known NP-complete problem available. The first NP-complete problem is a decision problem from Boolean logic called the satisfiability problem (SAT). The satisfiability problem consists on finding a truth assignment that satisfies a Boolean formula. A Boolean formula is satisfiable if and only if there is some assignment of true and false values to the variables that make the formula evaluate to true.
The Cook-Levin Theorem states that SAT ∈ P iff P = NP, which proves that SAT is NP-complete and links the complexity of the SAT problem to the complexities of all problems in NP [5]. To show that SAT is NP-complete, one must show that SAT is in NP and that every problem in NP is polynomial time reducible to it. This proof can be summarized as follows. First, SAT is easily shown to be in NP by giving an algorithm that solves it in (nondeterministic) polynomial time. A nondeterministic algorithm just needs to guess a truth assignment for a given Boolean formula and then check to see if the assignment satisfies it.
Secondly, to show that every language in NP is reducible to SAT, the proof gives a description of a generic procedure that, when applied to a polynomial time nondeterministic Turing machine that recognizes A; it gives the polynomial transformation that maps an instance of A into an instance of SAT and, therefore, simultaneously proves that for every language L in NP, L is reducible to SAT. The procedure transforms the input I to a Boolean expression B. If the machine accepts, B has a satisfying assignment that corresponds to the accepting computation. If the machine does not accept, no assignment satisfies B. Finally, the proof analyzes the complexity of the reduction to state that the transformation can be computed in polynomial time, and thus showing that SAT is NP-complete.
There are many decision problems that are NP-complete whose proofs are not as complex as the one given for SAT. Actually, once there is a single problem proven to be NP-complete, the procedure for proving additional NP-complete problems becomes easier. To given an example, consider the Hamiltonian Path (HAMPATH) problem and the Traveling Salesman (TS) decision problem. Both problems are known to be NP-complete.
Knowing that HAMPATH is NP-complete, one can show that TS is also NP-complete. The TS problem is defined as follows: given a number of cities, the distances from any city to any other city, and D ∈ Z+, is there a round-trip route that visits each city exactly once and then returns to the starting city having a total distance no more than D?
A similarity exists between HAMPATH and TS and in fact, HAMPATH is reducible to TS. Because it is known that HAMPATH is NP-complete, the proof to show that TS is NP-complete as well essentially consists on:
- Showing that TS is in NP.
- Constructing a transformation ƒ from HAMPATH to TS.
- Proving that ƒ runs in polynomial time.
The TS decision problem can be easily show to be in NP by giving an nondeterministic Turing machine that just needs to guess a round-trip route and verify that the total distance is less than the given bound. The function ƒ that transforms HAMPATH to TS is defined by [1] as follows: Suppose G = (V, E), with |V| = m, is a given instance of HAMPATH. The corresponding instance of TS has a set C of cities that is identical to V. For any two cities vi, vj ∈ C, the inter-city distance d(vi, vj) is defined to be 1 if {vi, vj} ∈ E and 2 otherwise. The distance D on the desired round-trip length is set equal to m. In [1], the proof continues by showing that ƒ runs in polynomial time and that G contains a Hamiltonian path if and only if there is round-trip of all the cities in ƒ(G) that has a total distance no more than D, concluding that HAMPATH is polynomially reducible to TS and therefore TS is NP-complete.
The previous procedure can be generalized for proving additional NP-complete problems. The only steps that vary are the selection for an NP-complete problem whose characteristics would allow for a relatively easy construction of a polynomial transformation, and of course, the construction of such transformation.
Another related unsolved question whose answer could determine if P = NP is that of whether the class NP is closed under complementation. If NP is not closed under complementation, then clearly P ≠ NP, since P is closed under complementation. There is no NP-complete problem whose complement is known to be in NP. In fact, if any NP-complete problem is discovered to have its complement in NP, then NP would be closed under complementation [2].
Space complexity
Another way of classifying problems according to their computational complexity is by the amount of space that a Turing machine requires to compute a solution. The formal definition of space complexity is the following:
"Let M be a deterministic Turing machine that halts on all inputs. The space complexity of M is the function ƒ: N → N, where ƒ(n) is the maximum number of tape cells that M scans on any input of length n. If the space complexity of M is ƒ(n), we also say that it runs in space ƒ(n). If M is a nondeterministic Turing machine wherein all branches halt on all inputs, ƒ(n) would be the maximum number of tape cells that M scans on any branch of its computation for any input of length n" [5].
Interestingly, a problem that uses more than linear time (or even more than polynomial time) could actually require linear space. For example, the NP-complete problem SAT can be solved with a linear space algorithm. Space complexity shares many of the characteristics of time complexity, but space appears to be more powerful than time because space can be reused, whereas time cannot [5]. In fact, Walter Savitch, in 1970, showed that a nondeterministic Turing machine that runs in space ƒ(n) can be simulated by a deterministic Turing machine that runs in the square of the space or ƒ2(n). As seen in time complexity, the effects in time are significantly greater than the space requirements of equivalent deterministic and nondeterministic Turing machines.
The class PSPACE
The class of languages that are decidable in polynomial space on a deterministic Turing machine is called PSPACE. By following the analogy of the time complexity counterpart, the class of languages that are decidable in polynomial space on a nondeterministic Turing machine is called NSPACE.
Savitch’s Theorem states that any nondeterministic Turing machine that uses f(n) space can be converted to a deterministic Turing machine that uses only f2(n) space [5]. More formally, NPSACE(f(n)) ⊆ SPACE (f2(n)). Thus, PSPACE = NPSPACE, because the square of any polynomial is still a polynomial, which shows how nondeterminism has a more limited effect on space requirements in comparison with time requirements.
Decision problems that are in P are also in PSPACE, more specifically P ⊆ PSPACE. It is clearly that, for t(n) ≥ n, a machine that computes a solution in time t(n) can use at most t(n) space because it can explore at most one new cell at each step of its computation [5]. On the other hand, problems that are in NP are also in NPSPACE, and hence, by Savitch’s Theorem, NP ⊆ PSPACE.
The classes L and NL
The space complexity classes L and NL are very interesting because they consider what is called sublinear space bounds. In sublinear space complexity the machine is able to read the entire input but it does not have enough space to store the input [5], whereas in time complexity, sublinear bounds are not considered because the machine cannot read the entire input.
In order to support sublinear space bounds, the single-tape Turing machine is slightly modified to have two tapes: one read-only input tape and a read-write work tape. The input tape contains the input and cannot be modified. On the other hand, the read-write work tape works as usual and it is the only tape that contributes to the space complexity of this Turing machine.
L and NL are the classes of languages that are decidable in logarithmic space by a deterministic and a nondeterministic Turing machine, respectively. As an example, [5] shows how the language A = { 0k1k | k ≥ 0 } ∈ L. In a single-tape Turing machine, the entire input is read and the machine uses linear space to cross off the 0s and 1s to determine if the number of 0s and 1s matches. However, the algorithm can be modified to use logarithmic space by having a two-tape Turing machine that counts the number of 0s and 1s. The only space required is the one occupied by two binary counters in the work tape, where each of the counters uses only logarithmic space. The Turing machine runs in O(log n) space, which shows that A ∈ L.
Conclusion
There have been many advances in the area of computational complexity that contribute to the understanding of the characteristics and limitations of algorithms, however, there are still many questions that remain unsolved and represent an extremely interesting challenge for mathematicians, computer scientists and researchers alike. The question of whether P = NP is still unsolved. In fact, the equivalence of complexity classes not only remains unsolved for P and NP, but also for other important time and space complexity classes.
The importance of determining whether P = NP comes from the fact that if this conjecture is proven to be true, then many problems that are of great interest in mathematics, computer science, economics and other areas, could be solved in polynomial time. This means that there is an algorithm capable of solving the problem within practical time constraints. However, nobody has yet proved or disproved this conjecture. So far, people have had to either approximate a solution or find a similar problem whose solution can be solved in a relative short period of time and that satisfies to some degree the requirements for information at a relative cost. For many years researchers have tried, without success, to find polynomial time algorithms to solve NP problems. Thus, most of the researchers work under the assumption that such algorithms do not exist, in other words, that P ≠ NP.
References
[1] Garey, Michael R., and Johnson, David S. Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman & Co, 1990.
[2] Hopcroft, John E., and Ullman, Jeffrey D. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, 1979.
[3] Papadimitriou, Christos H. Computational Complexity. San Diego, California: Addison-Wesley, 1994.
[4] Salomaa, Arto. Formal Languages. Orlando, Florida: Academic Press, Inc. 1987.
[5] Sipser, Michael. Introduction to the Theory of Computation. 2nd ed. Boston, Massachusetts: Thomson Course Technology, 2006.
