INTRODUCTION We begin with an overview of those areas in the theory of computation that ‘we present in this course. Following that, you'll have a chance to learn and/or review some mathematical concepts that you will need later. 0.1 AUTOMATA, COMPUTABILITY, AND COMPLEXITY This book focuses on three traditionally central areas of the theory of computa~ tion: automata, computability, and complexity. They are linked by the question: What are the findamental capabilities an limitations of computers? ‘This question goes back to the 1930s when mathematical logicians first began to explore the meaning of computation. ‘Technological advances since that time have greatly increased our ability to compute and have brought this question out of the realm of theory into the world of praetical concern. In each of the three areas—automata, computability, and complexity—this question is interpreted differently, and the answers vary according to the inter pretation. Following this introductory chapter, we explore each area in a sepa rate part of this book. Here, we introduce these parts in reverse order because starting from the end you can better understand the reason for the beginning, 12 CHAPTER O/ INTRODUCTION COMPLEXITY THEORY Computer problems come in different varieties; some are easy, and some are hard. For example, the sorting problem is an easy one. Say that you need to arrange a list of numbers in ascending order. Even a small computer can sort 2 million numbers rather quickly. Compare that to a scheduling problem. Say that you must find a schedule of classes for the entire university to satisfy some reasonable constraints, such as chat no two classes take place in the same room, at the same time. ‘The scheduling problem seems to be much harder than the sorting problem. If you have just a thousand classes, finding the best schedule may require centuries, even with a supercomputer. What makes some problems computationally hard and atbers easy? ‘This is the central question of complexity theory. Remarkably, we don't know the answer to it, though it has been intensively researched for the past 35 years. Later, we explore this fascinating question and some of its ramifications In one of the important achievements of complexity theory thus far, re- searchers have discovered an elegant scheme for classifying problems according to their computational difficulty. It is analogous to the periodic table for clas sifying elements according to their chemical properties. Using this scheme, we can demonstrate a method for giving evidence that certain problems are compu- tationally hard, even if we are unable to prove that they are. ‘You have several options when you confront a problem that appears to be ‘computationally hard. First, by understanding which aspect of the problem is at the root of the difficulty, you may be able to alter it so that the problem is more casily solvable. Second, you may be able to settle for less than a perfect solution to the problem, In certain cases finding sofutions that only approximate the perfect one is relatively easy. Third, some problems are hard only in the worst case situation, but easy most ofthe time. Depending on the application, you may be satisfied with a procedure that occasionally is stow but usually runs quickly. Finally, you may consider alternative types of computation, such as randomized computation, that can speed up certain tasks. ‘One applied area that has been affected directly by complexity theory is the ancient field of cryptography. In most fields, an easy computational problem is preferable to a hard one because easy ones are cheaper to solve. Cryptogra- phy is unusual because it specifically requires computational problems that are hard, rather than easy, because secret codes should be hard to break without the secret key or password, Complexity theory has pointed cryptographers in the direction of computationally hard problems around which they have designed revolutionary new codes. COMPUTABILITY THEORY During the first half of the twentieth century, mathematicians such as Kurt Gadel, Alan Turing, and Alonzo Church discovered that certain basie problems cannot be solved by computers, One example of this phenomenon is the prob-0.2 MATHEMATICAL NOTIONS ANO TERMINOLOGY 3 lem of determining whether a mathematical statement is true or false. ‘This task is the bread and butter of mathematicians. Tt seems like a natural for solution by computer because it lies strictly within the realm of mathematics. But no computer algorithm can perform this task Among the consequences of this profound result was the development of ideas concerning theoretical models of computers that eventually would help lead to the construction of actual computers. The theories of computability and complexity are closely related. In com- plexity theory, the objective is to classify problems as easy ones and hard ones, whereas in computability theory the classification of problems is by those that are solvable and those that are not. Computability theory introduces several of the concepts used in complexity theory AUTOMATA THEORY Automata theory deals with the definitions and properties of mathematical mod- els of computation, ‘These models play a role in several applied areas of computer science. One model, called the finite automaton, is used in text processing, com- pilers, and hardware design. Another model, called the context-free grammar, is used in programming languages and artificial intelligence. Automata theory is an excellent place to begin the study of the theory of computation. The theories of computability and complexity require a precise definition ofa computer. Automata theory allows practice with formal definitions of computation as it introduces concepts relevant to other nontheoretical areas of computer science. 0.2 MATHEMATICAL NOTIONS AND TERMINOLOGY [As in any mathematical subject, we begin with a discussion of the basic mathe- matical objects, tools, and notation that we expect to use. SETS A.set is a group of objects represented as a unit. Sets may contain any type of object, including numbers, symbols, and even other sets. The objects in a set are called its elements or members. Sets may be described formally in several ways. ‘One way is by listing a sets elements inside braces. Thus the set {7,21, 57) contains the elements 7, 21, and 7. ‘The symbols € and ¢ denote set member ship and nonmembership. We write 7 € (7,21, 57) and 8 ¢ {7,21,57}. For two sets A and B, we say that A is a subset of B, written A < B, if every member of4 ciapTer o/ INTRODUCTION Aalso isa member of B. We say that A isa proper subset of B, written AC B, if Ais a subset of B and not equal to B. ‘The order of describing a set doesn't matter, nor does repetition of its mem bers. We get the same set by writing {57,7,7.7,21}. If we do want to take the number of occurrences of members into account we call the group 2 meutset in- stead of a set. Thus {7} and {7,7} are different as multisets but identical as sets. An infinite set contains infinitely many elements, We cannot write a list ofall the elements of an infinite set, so we sometimes use the “...” notation to mean, “continue the sequence forever.” Thus we write the set of natural numbers N’ {1.2.3.0 ‘The set of integers 2 is written fo QMO Z “The set with 0 members is called the empty set and is written 0. When we wane co describe a set containing elements according to some rule, we write {n] rule about 1}. ‘Thus {nn =m? for some m €.N’} means the set of perfect squares. Ifwe have two sets A and B, the union of Aand B, written AUB, isthe set we get by combining all the elements in A and B into single set. The intersection of 4and Bi, written AM B, is the set of elements that are in both A and B. The complement of A, written A, is the set of all elements under consideration that are not in A. ‘As is often the case in mathematics, a picture helps clarify a concept. For sets, we use a type of picture called a Venn diagram. It represents sets as regions ‘enclosed by circular lines. Let the set START-t be the set of all English words that start with the letter “t.” For example, in the following figure the circle represents the set START-t. Several members of this set are represented as points inside the circle, smagrt Dy— ernife oo tundra . theory FicuRe 0.1 Venn diagram for the set of English words starting with “t” ‘Similarly, we represent the set END-z of English words that end with “2” in the following figure.0.2 MATHEMATICAL NOTIONS AND TERMINOLOGY 5 END? yo gure, jaw °7—~ rarematare FIGURE 0.2 ‘Venn diagram for the set of English words ending with “2” “To represent both sets in the same Venn diagram we must draw them so that they overlap, indicating that they share some clements, as shawn in the following figure. For example, the word fpves is in both sets, The figure also contains a circle for the ser START). It doesn't overlap the circle for START-t because no ‘word lies in both sets. SPAR ENDS. STARTS) U topaz jazz FIGURE 0.3 ‘Overlapping circles indicate common elements ‘The next two Venn diagrams depict the union and intersection of sets A and B, @ ricure 0.4 ygrams for (a) AU B and (b) ANB6 — cHaPTER O/ INTRODUCTION SEQUENCES AND TUPLES A sequence of objectsisa list of these objects in some order. We usually designate 1 sequence by writing the list within parentheses. For example, the sequence 7, 21, 57 would be written (7.21, 57). Ina set the order doesn’t matter, but in a sequence it does, Hence (7.21.57) is not the same as (57, 7,21). Similarly, repetition does matter in a sequence, but it doesn't matter in a set. ‘Thus (7.7. 21.57) is different from both of the other sequences, whereas the set (7. 21,57} is identical to the set {7,7,21, 57}. ‘As with sets, sequences may be finite or infinite. Finite sequences often are called tuples. A sequence with k elements is a k-tuple. ‘Thus (7.21,57) is a 3-tuple. A 2-tuple is also called a pair. Sets and sequences may appear as elements of other sets and sequences. For ‘example, the power set of A is the set of all subsets of A. If 4 is the set {0,1}, the power set of A is the set {0, {0}, (1), {0,1} }. The set of all pairs whose elements are Os and Is is { (0,0), (0, 1}. (1,0), (1.1) }. If A and Bare two sets, the Cartesian product or eross product of A and B, written A x B, is the set ofall pairs wherein the first element is a member of A and the second element is a member of B. EXAMPLE 0.5 IA = {1,2} and B= (x,y. Ax B= {(L2), (Ley), (1e2)s 2.2), 2), (2.2)} We can also take the Cartesian product of k sets, Ai, zy... Ay written A x Ap x +++ Ag, Tis the set consisting of al F-tuples (ai,a2, ax) where ae Ay EXAMPLE 0,60 =~ IFA and B are as in Example 0.5, Ax Bx A= {(12,1s (12,2), Ut Us (1u2) e21), (12.2), (2.01), (22052), (Zeus 1s (2ss2)s (2.201), (2,252) fe If we have the Cartesian product ofa set with itself, we use the shorthand & —— Dx Ax a= At0.2 MATHEMATICAL NOTIONS AND TERMINOLOGY 7 EXAMPLE O.7 eo ‘The set N equals \’ x NV. Ic consists of all pairs of natural numbers. We also may write itas ((i,)] tJ 2 1). FUNCTIONS AND RELATIONS Funetions are central to mathematics. A function is an object that sets up an input-output relationship. A function takes an input and produces an output. In every function, the same input always produces the same output. If f isa funetion whose output value is 6 when the input value is a, we write fla) =b, A function also is called a mapping, and, if f(a) = b, we say that f maps a to b. For example, the absolute value function abs takes a number x as input and returns x if x is positive and —z if x is negative. Thus abs(2) = abs(—2) = 2. Addition is another example of a function, written add. ‘The input to the addi- tion function isa pair of numbers, and the output is the sum of those numbers. The set of possible inputs to the function is called its domain. ‘The outputs ‘ofa function come from a set called its range. The notation for saying that f is a function with domain D and range It is F: DOR. In the case of the function ats, if we are working with integers, the domain and the range are Z, so we write abs: Z—> Z. In the case of the addition function for integers, the domain isthe set of pairs of integers 2 x Z and the range is Z, so we write add: Z x Z—+Z, Note thata function may not necessarily use all the elements of the specified range. The function abs never takes on the value = even though ~1 € Z. A function that does use all the elements of the range is said to be onto the range. We may describe a specific function in several ways. One way is with a pro- cedure for computing an output from a specified input. Another way is with a table thar lists all possible inputs and gives the output for each input. EXAMPLE, Consider the funetion J: {0,1,2,3,4}—{0, n | f(r) a 1 T 2 (3 4 0 2 3 4B CHAPTER O/ INTRODUCTION This funetion adds I to its input and then outputsthe result modulo 5. A number modulo m is the remainder after division by m. For example, the minute hand ona clock face counts modulo 60. When we do modular arithmetic we define Zp = (0.1.2, ...,m— 1}. With this notation, the aforementioned function f has the form 7 EXAMPLE Q,Q) meeonwnnn Sometimes a two-dimensional table is used if the domain of the function is the Cartesian product of two sets. Here is another funetion, g: Z1 x Z;—+ Zs. The entry at the row labeled ¢ and the column labeled j in the table is the value of atid). ‘The function g is the addition function modulo 4. When the domain of a function f is Ay x ++ x Ay for some sets Ay, +5 Aky the input to f isa -tople (a;.a2, ....e) and we eal the a; the arguments tof A function with & arguments is called a k-ary function, and kis called the arity oftthe function. IF is 1, f has single argument and f is called a unary function. If kis 2, fis a binary function. Certain familiar binary functions are written in a special infix notation, with the symbol for the funetion placed between its two arguments, rather than in prefix notation, with the symbol preceding. For example, the addition funetion add usually is written in infix notation with the + symbol between its two arguments as in a +5 instead of in prefix notation add (a,b). A predicate or property is a function whose range is {TRUE, FALSE}. For example, let even bea property that is ‘TRUE if its input is an even number and FALSE if its input is an odd number. Thus even(4) = TRUE and even(5) = FALSE. A property whose domain isa set of k-tuples 4 x --- x Ais called a relation, a k-ary relation, or a k-ary relation on A. \ common ease is a 2-ary relation, called a binary relation, When writing an expression involving a binary rela- tion, we customarily use infix notation. For example, “less than” is a relation usually written with the infix operation symbol <. “Equality,” written with the = symbol is another familiar relation. TF R is a binary relation, the statement ‘aRb means that afb = TRUE. Similarly if R is a k-ary relation, the statement Ray, ....a4) means that R(ay, ....a4) = TRUF0.2 MATHEMATICAL NOTIONS AND TERMINOLOGY 9 EXAMPLE 0.10 Ina children’s game called Scissors-Paper-Stone, the two players simultaneously selecta member of the set (SCISSORS, PAPER, STONE} and indicate their selec~ tions with hand signals, Ifthe two selections are the same, the game starts over. If che selections differ, one player wins, according to the relation beats beats | 8 PAPER STONE Scissors [FALSE TRUE FALSE PAPER | FALSE FALSE TRUE STONE TRUE FALSE FALSE From this table we determine that SCISSORS beats PAPER is TRUE and that PAPER beats SCISSORS is FALSE, Sometimes describing predicates with sets instead of functions is more con- venient. ‘The predicate P: D—>{‘TRUF, FALSE} may be written (D. $), where S= (a € D| Pla) = TRUF}, or simply 5 if the domain D is obvious from the context. Hence the relation beats may be written {(SCISSORS, PAPER), (PAPER, STONE), (STONE, SCISSORS)} A special type of binary relation, called an equivalence relation, captures the notion of two objects being equal in some feature. A binary relation Ris an equivalence relation if R satisfies three conditions: 1. Ris reflexive if for every 2, Rts 2. Ris symmetric if for every x and y, Ry implies yltx; and 3. Ris transitive if for every «, y,and 2, Ry and yRz implies 2. EXAMPLE O.1T =~ Define an equivalence relation on the natural numbers, written =; say that i =r j, if¢—j isa multiple of 7. This is an equivalence rela satisfies the three conditions. First, itis reflexive, as i—i = 0, which isa multiple of 7. Second, itis symmetric, asi — j isa multiple of 7 if j — fis a multiple of 7. ‘Third, iis transitive, as whenever {— j isa multiple of 7 and j — kris a multiple of 7, then i = k= (ij) + (j — b) is the sum of two multiples of 7 and hence a multiple of 7, too.