410 CHAPTER 9. UNDECWABILITY

9.6 Summary of Chapter 9

♦ Recursive and Recursively Enumerable Languages: The languages accepted by Turing machines are called recursively enumerable (RE), and the subset of RE languages that are accepted by a TM that always halts are called recursive.

f Complements of Recursive and RE Languages: The recursive languages are closed under complementation, and if a language and its complement are both RE. then both languages are actually recursive. Thus, the complement of an RE-but-not-recursive language can never be RE.

♦ Decidability and Undecidabiiity: Decidable is a synonym for recvir-sive, although we tend to refer to languages as recursive and problems (which are languages interpreted as a question) as decidable. If a language is not recursive, then we call the problem expressed by that language undecidable.

-f The Language Ld: This language is the set of strings of Os and Is that, when interpreted as a TM, are not in the language of that TM. The language L is a good example of a language that is not RE; i.e., no Turing machine accepts it.

The Universal Language: The language L consists of strings that are interpreted as a TM followed by an input for that TM, The string is in L if the TM accepts that input. L is a good example of a language that is RE but not recursive.

f Rices Theorem: Any nontrivial property of the languages accepted by Turing machines is undecidable. For instance, the set of codes for Turing machines whose language is empty is undecidable by Rices theorem. In fact, this language is not RE, although its complement - the set of codes for TMs that accept at least one string - is RE but not recursive.

¥ Posts Correspondence Problem: This question asks, given two lists of the same number of strings, whether we can pick a sequence of corresponding strings from the two lists and form the same string by concatenation. PCP is an important example of an undecidable problem, PCP is a good choice for reducing to other problems and thereby proving them undecidable.

♦ Undecidable Context-Pree-Language Problems: By reduction from PCP, we can show a number of questions about CFLs or their grammars to be undecidable. For instance, it is undecidable whether a CFG is ambiguous, whether one CFL is contained in another, or whether the intersection of two CFLs is empty.

9.7. REFERENCES FOR CHAPTER 9 411

9.7 References for Chapter 9

The undecidabihty of the universal language is essentially the result of Turing [9], although there it was expressed in terms of computation of arithmetic functions and halting, rather than languages and acceptance by final state. Rices theorem is from [8].

The undecidability of Posts Correspondence problem was shown in [7], although the proof used here was devised by R. W. Floyd, in unpublished notes. The undecidabihty of Post tag systems (defined in Exercise 9.4.4) is from [6].

The fundamental papers on undecidability of questions about context-free languages are [1] and [5]. However, the fact that it is undecidable whether a CFG is ambiguous was discovered independently by Cantor [2], Floyd [4], aud Chomsky and Schutzenberger [3].

1. Y. Bar-Hillel, M. Perles, and E. Shairdr, On formal properties of simple phrase-structure grammars, Z. Phonetik. Sprachwiss. Komniunikations-forsch. 14 (1961), pp. 143-172.

2. D. C. Cantor, On the ambiguity problem in Backus systems, J. ACM 9:4 (1962), pp. 477-479.

3. N. Chomsky and M. P. Schutzenberger, The algebraic theory of con-text-fi:ee languages, Computer Programming and Formal Systems (1963), North Holland, Amsterdam, pp. 118-161.

4. R. W. Floyd, On ambiguity in phrase structure languages, Communications of the ACM 5:10 (1962), pp. 526-534.

5. S. Ginsburg and G. F. Rose, Some recursively unsolvable problems in ALGOL-hke languages, J. ACM 10:1 (1963), pp. 29-47.

6. M. L. Minsky, Recursive unsolvabihty of Posts problem of tag and other topics in the theory of Turing machine.s, Annals of Mathematics 74:3 (1961), pp. 437-455.

7. E. Post, A variant of a recursively unsolvable problem, Bulletin of the AMS52 (1946), pp. 264-268.

8. H. G. Rice, Classes of recursively enumerable sets and their decision problems, Transacttons of the A MS 89 (1953), pp. 25-59.

9. A. M. Turing, On computable numbers with an application to the Ent-scheidungsproblem, Proc. London Math. Society 2:42 (1936), pp. 230-265.

Chapter 10

Intractable Problems

We now bring our discussion of what can or cannot be computed down to the level of efficient versus inefficient computation. We focus on problems that are decidable, and ask which of them can be computed by Turing machines that run in an amount of time that is polynomial in the size of the input. You should review in Section 8.6.3 two important points:

The problems solvable in polynomial time on a typical computer are exactly the same as the problems solvable in polynomial time on a Turing machine.

Experience has shown that the dividing line between problems that can be solved in polynomial time and those that require exponential time or more is quite fundamental. Practical problems requiring polynomial time are almost always solvable in an amount of time that we can tolerate, while those that require exponential time generally cannot be solved except for small instances.

In this chapter we introduce the theory of intractability, that is, techniques for showing problems not to be solvable in polynomial time. We start with a particular problem - the question of whether a boolean expression can be satisfied, that is, made true for some assignment of the truth values TRUE and FALSE to its variables. This problem plays the role for intractable problems that L or PCP played for undecidable problems. That is, we beghi with Cooks Theorem, which implies that the satisfiabUity of boolean formulas cannot be decided in polynomial time. We then show how to reduce this problem to many other problems, which are therefore shown intractable as well.

Since we are dealing with whether problems can be solved in polynomial time, our notion of a reduction must change. It is no longer sufficient that there be an algorithm to transform Instances of one problem to instances of another. The algorithm itself must take at most polynomial time, or the reduction does not let us conclude that the target problem is intractable, even if the source