468 CHAPTER 10. INTRACTABLE PROBLEMS

1. I. Borosh and L. B. Treybig, Bounds on positive integral solutions of linear Diophantine equations, Proceedings of the A MS 55 (1976), pp. 299-304.

2. A. Cobhara, The intrinsic computational difficulty of functions, Proc. 1964 Congress for Logic, Mathematics, and the Philosophy of Science, North Holland, Amsterdam, pp. 24-30.

3. S. C. Cook, The complexity of theorem-proving procedures, Third ACM Symposium on Theory of Computing (1971), ACM, New York, pp. 151-158.

4. M. R. Carey and D. S. Johnson, Computers and Intractability: a Guide to the Theory of NP-Completeness, H. Freeman, New York, 1979.

5. D. S. Hochbaum (ed.), Approximation Algorithms for NP-Hard Problems, PWS Publishing Co., 1996.

6. R. M. Karp, Reducibility among combinatorial problems, in Complexity of Computer Computations (R. E. Miller, ed.). Plenum Press, New York, pp. 85-104,1972.

7. L. A. Levin, Universal sorting problems, Problemi Peredachi Informatsii 9:3 (1973), pp. 265-266.

8. J. Hartmanis and R. E. Stearns, On the computational complexity of algorithms, Transactions of the AMS 117 (1965), pp. 285-306.

9. J. D. UUman, NP-complete scheduling problems, J. Computer and System Sciences 10:3 (1975), pp. 384-393.

Chapter 11

Additional Classes of Problems

The story of intractable problems does not begin and end with MV. There are many other classes of problems that appear to be intractable, or are interesting for some other reason. Several questions involving these classes, like the V - question, remain unresolved.

We shall begin by looking at a class that is closely related to V and Л/Р: the class of complements oiMV languages, often called со-ЛР. liV = MV, then co-MV is equal to both, since V is closed under complementation. However, it is likely that co-MV is different from both these classes, and in fact likely that no NP-complete problem is in co-AfV.

Then, we consider the class TS, which is all the problems that can be solved by a Turing machine using an amount of tape that is polynomial in the length of its input. These TMs are allowed to use an exponential amount of time, as long as they stay within a limited region of the tape. In contrast to the situation for polynomial time, we can prove that nondeterminism doesnt increase the power of the TM when the limitation is polynomial space. However, even though VS clearly includes all oiMV, we do not know whether VS is equal to AfV, or even whether it is equal to V. We expect that neither equality is true, however, and we give a problem that is complete for VS and appears not to be in MV.

Then, we turn to randomized algorithms, and two classes of languages that lie between V and AfV. One is the class TIV of random polynomial languages. These languages have an algorithm that runs in polynomial time, using some coin flipping or (in practice) a random-number generator. The algorithm either confirms membership of the input in the language, or says I dont know. Moreover, if the input is in the language, then there is some probabifity greater than 0 that the algorithm will report success, so repeated application of the algorithm will, with probability approaching 1, confirm membership.

The second class, called ZW (zero-error, probabilistic polynomial), also involves randomization. However, algorithms for languages in this class either

say yes the input is in the language, or no it is not. The expected running time of the algorithm is polynomial. However, there might be runs of the algorithm that take more time than would be allowed by any polynomial bound.

To tie these concepts together, we consider the important issue of primality testing. Many cryptographic systems today rely on both:

1. The ability to discover large primes quickly (in order to allow communication between machines in a way that is not subject to interception by an outsider) and

2. The assumption that it takes exponential time to factor integers, if time is measured as a function of the length n of the integer written in binary.

We shall see that testing primes is both in MP and co-MP, and therefore it is unlikely that we can prove primality testing to be NP-complete. That is unfortunate, because proofs of NP-completeness are the most common arguments that a problem most likely requires exponential time. We shall also see that primality testing is in the class TIP. This situation is both good news and bad news. It is good, because in practice, cryptographic systems that require primes really do use an algorithm in the TZP class to find them. It is bad because it provides further weight to the assumption that we shall not be able to prove primality testing to be NP-complete.

H.l Complements of Languages in AfV

The class of languages P is closed under complementation (see Exercise 10.1.6). For a simple argument why, let L be in P and let M be a TM for L. Modify M as follows, to accept L. Introduce a new accepting state q and have the new TM transition to q whenever M halts in a state that is not accepting. Make the former accepting states of M be nonaccepting. Then the modified TM accepts L, and runs in the same amount of time that M does, with the possible jiddition of one move. Thus, L is in ;P if L is.

It is not known whether MP is closed under complementation. It appears not, however, and in particular we expect that whenever a language L is NP-complete, then its complement is not in MP.

11.1.1 The Class of Languages Co~NV

Co-MP is the set of languages whose complements are in MP. We observed at the beginning of Section 11.1 that every language in P has its complement also in P, and therefore in MP. On the other hand, we believe that none of the NP-complete problems have their complements in MP, and therefore no NP-complete problem is in co-MP. Likewise, we believe the complements of NP-complete problems, which are by definition in co-MP, вхе not in MP. Figure 11.1 shows the way we believe the classes P, MP, and co-MP relate,