Lecture Notes in Mathematics Edited by A. Dold, B. Eckmann and E Takens Subseries: Fondazione C. I. M. E., Firenze Adviser: Roberto Conti 1429 S. Homer A.Nerode R.A. Platek G.E. Sacks A. Scedrov Logic and Computer Science Lectures given at the 1st Session of the Centro Internazionale Matematico Estivo (C.I.M.E.) held at Montecatini Terme, Italy, June 20-28, 1988 Editor: P. Odifreddi I I I Springer-Verlag Berlin Heidelberg New York London Paris Tokyo Hong Kong Barcelona Authors Steven Homer Department of Computer Science and Mathematics Boston University, Boston, MA 02215, USA Anil Nerode Mathematical Sciences Institute Cornell University, Ithaca, NY 14853, USA Richard A. Platek Odyssey Research Associates 301A Harris B. Dates Drive, Ithaca, NY 14850-1313, USA Gerald E. Sacks Department of Mathematics Harvard University, Cambridge, MA 02138, USA Andre Scedrov Department of Mathematics University of Pennsylvania, Philadelphia, PA 19104, USA Editor Piergiorgio Odifreddi Dipartimento di Informatica, Universit& Corso Svizzera 185, 10149 Torino, Italy Mathematics Subject Classification (1980): 03B40, 03B20, 03B70, 03D15 ISBN 3-540-52?34-6 Springer-Verlag Berlin Heidelberg New York ISBN 0-38?-52?34-6 Springer-Verlag NewYork Berlin Heidelberg This work is subject to copyright.A ll rights are reserved,w hethert he whole or part of the material is concerned, specificallyt he rights of translation,r eprinting, re-use of illustrations,r ecitation, broadcasting,r eproductiono n microfilmso r in otherw ays, and storagei n data banks. Duplication of this publicationo r parts thereofi s only permittedu ndert he provisionso f the GermanC opyright Law of September9 , 1965, in its versiono f June 24, 1985, and a copyright fee must always be paid. Violationsf all under the prosecutiona ct of the German Copyright Law. © Springer-VerlagB erlin Heidelberg 1990 Printed in Germany Printing and binding: Druckhaus Beltz, Hemsbach/Bergstr. 2146/3140-543210- Printedo n acid-freep aper P r e f a c e The C.I.M.E. Meeting on Logic and Computer Science was held in June 1988 in Montecatini, Italy. It was attended by some one hundred people from all over Europe, and it consisted of five short courses on mainstream aspects of Applied Logic. In particular, the following fields were touched: foundational aspects of both logical (Sacks) and functional (Scedrov) program- ming languages; constructive logic (Nerode); complexity theory (Hartmanis and Homer); and program verification (Platek). The present volume collects the lecture notes for those classes (with only one exception). We hope that they will turn out to be useful both to the people who attended the meeting, and to those who did not, but share with all of us an interest in the foundational aspects of Computer Science and the applications of Logic. On behalf of the organization, I would like to thank the speak- ers and the participants for making the meeting a successful one. Piergiorgio Odifreddi TABLE OF CONTENTS S. HOMER, The Isomorphism Conjecture and its Generalization ............... A. NERODE, Some Lectures on Intuitionistic Logic .......................... 12 R.A. PLATEK, Making Computers Safe for the World. An Introduction to Proofs of Programs. Part I .......................................... 60 G.E. SACKS, Prolog Progra-~ing ............................................ 90 A. SCEDROV, A Guide to Polymorphic Types .................................. i i i List of Participants ...................................................... 151 The Isomorphism Conjecture and Its Generalizations Steven Homer* Departments of Computer Science and Mathematics Boston University Boston, MA 02215 USA This paper focuses on a particular problem in complexity theory, the isomorphism con- jecture, which has been central to a large body of recent research. The problem was origi- nally posed by Len Berman and Juris Hartmanis in [3]. Part of their the motivation for this problem is a theorem of John Myhill's from classical recursion theory and much of the work on the conjecture involves the interplay between recursion theory and complexity theory. Mathematical logic plays a major role in the definitions of the concepts and in indicating pos- sible methods of solution. This paper will first present some background, including the origi- nal conjecture and first results concerning it. Then several generalizations of the conjecture and recent work concerning these generalizations will be discussed. Finally relativizations of the conjecture will be briefly explored. Throughout the paper the interaction with recursion theory and the many open problems which arise will be stressed. 1. The Isomorphism Conjecture We begin with the work of Berman and Hartmanis [3]. They undertook the study of the structure of the NP-complete sets. There are literally thousands of such sets and, due to their practical importance, their study is one of the central topics of complexity theory. In [3] the question asked was, how similar are all of these NP-complete problems and what structure do they have in common ? Given that these many problems come from extremely disparate and unrelated areas of computer science they reached the surprising conclusion that all of the known (at that time) NP-complete sets are very similar, in fact essentially the same. More precisely they proved that they are all isomorphic via polynomial-time isomorphisms (p- isomorphic). They conjectured that all NP-complete problems are p-isomorphic. *This work was supported in part by NSA grant #MDA904-87-H-2003 and by NSF grant #MIP-8608137. Given the background provided by classical recursion theory this conjecture seems per- fectly reasonable. The well known isomorphism theorem of John Myhill [18] states that all many-one complete recursively enumerable are isomorphic via a recursive isomorphism. If Myhill's proof workect in this subrecursive setting the conjecture would fol- low. However, as we will see, the subrecursive case does not follow from the recursive but rather presents subtleties and complications which are unique to complexity theory. Research on the isomorphism conjecture provides a good illustration of the difficulties present in the subrecursive setting which simply never arise in recursion theory. Surprisingly this research has some similarity to research in set recursion in generalized recursion theory (see Slaman [ 19]). A precise study of the parallels between these two areas might be worth pursuing. Now to some definitions and terminology. All sets (problems) will be subsets of {0,1}*. This papers deals exclusively with polynomial-time reducibilities. However, we will be careful to distinguish which type of polynomial reducibility we are using at any time. Four types of reducibilities will be used. They are Turing, -<!?, truth-table, <ft, many-one, <_g, and one-one, <f-l, polynomial reducibility. Even among these four we will have occasion to distinguish several different restrictions and extensions. For any of these reducibilities, _<, and any set S, the <-degree of S = {A I A < S and S _< A}. A set C is <-hard for a complexity class Q if, B e Q implies B < C. C is <-complete for Q if C e Q and it is <-hard for Q. Readers unfamiliar with these reducibilities and their elementary properties might consult the paper of Ladner, Lynch and Selman [14]. NP-complete sets are sets which are _<g-complete for NP. A polynomial-time isomor- phism (p-isomorphism) between two problems A and B is a one-one, surjective polynomial- time computable and invertible function from {0,1}* to {0,1}* which reduces A to B. Using these definitions, the conjecture that all NP-complete sets are p-isomorphic can now be pre- cisely understood. Note that the isomorphism conjecture implies that P ~ NP. The first results in support of the conjecture are contained in the Berman, Hartmanis paper. There they show that many of the well-known NP-complete sets are p-isomorphic. Their method is to give conditions which imply p-isomorphism. They then show that many common NP-complete problems satisfy these conditions. The formulation of the result given here is due to Mahaney and Young [17]. It is essentially equivalent to the original one. Proofs of these results are omitted here, but can be found in [17]. SAT is, as usual, the collec- tion of satisfiable Boolean formulas. Definition: A polynomial padding function for a set S is is a one-one, polynomial time com- putable and invertibte function p such that for all x and y, x ES if and only if p(x,y)v_.S. Theorem 1: Two sets which are in the same polynomial many-one degree both of which have padding functions are p-isomorphic. Corollary 1: An NP-complete set A is p-isomorphic to SAT if and only if A has a padding function. Proof of corollary (sketch): The corollary follows from Theorem 1 once a padding function for SAT is constructed. To pad a formula x with a binary padding string y, allocate a new literal for each 0 bit of y and the negation of a new literal for each 1 bit of y. Now form p(x,y) by conjoining x with the new literals and negations of literals. The above Theorem gives a condition for p-isomorphism in terms of the sets structural properties. Often, as in the Corollary, we are given a particular "canonical" complete set (like SAT) and want to determine if another complete set is p-isomorphic to it. A second, related and often useful condition implying isomorphism can be given in terms of the reducibility properties of the sets. Let <--f-l,invertible denote a reduction witnessed by a 1-1 polynomial- time computable and polynomial-time invertible function. Theorem 2: Let C be a set with a polynomial padding function and B be such that B <--~-l,invertible C and C <--~-l,invertible B. Then B and C are p-isomorphic. Proof: Let p be a polynomial padding function for C, f witness the invertible reduction from C to B and g witness the invertible reduction from B to C. We define a padding function q for B by, q(z,y) = f(p(g(z),y)). Then z e B iff g(z) e C iff p(g(z),y) E C iff f(p(g(z),y))=q(z,y) e B. It is straightforward to check that q is polynomial-time invertible, so it is a padding function for B. The p-isomorphism follows by Theorem 1. Using Theorem 2 we can prove that or NP-complete sets, 1-1, invertible completeness is enough to ensure p-isomorphism with SAT. A similar result holds for any other <g-degree which contains a complete set (like SAT) which is <f_l,invaibte-complete and has a polyno- mial padding function. Corollary 2: Let B be NP-complete. Then SAT is p-isomorphic to B iff SAT <f-l,invertibIe B. Using Corollary 1, most known NP-complete sets can be shown to be p-isomorphic. One possibly exceptional class of NP-complete sets, not all known to have padding functions, are the p-creative sets defined by Joseph and Young in [8]. These sets are the polynomial- time analogs of the recursively creative sets. They have a number of interesting properties. Past this, little is known concerning the original conjecture. 2. The Conjecture for Other Subrecursive Classes To better focus on the difficulties concerning a solution to the isomorphism conjecture and to examine the efficacy of the recursion-theoretic methods which are so successful in the r.e. case, we next consider two other well-studied complexity classes, deterministic exponential time (E = DTIME (2 linear)) and nondeterministic exponential time (NE = NTIME (2 linear )). What form does the isomorphism conjecture take here ? We consider sets in (deterministic or nondeterministic) exponential time which are complete for many-one polynomial-time reduc- tions. Such sets form a polynomial many-one degree. The isomorphism question is then, as before, whether that degree collapses. That is, whether all sets in the degree are p-isomorphic. Another way to view this degree is that it is the polynomial many-one degree of the canonical complete set, which for E is K = {( e,x,k) I the e th exponential time set accepts x in < k steps, k a binary integer}. It is straightforward to show that K is actually <Ei.,i,~ertibte-complete for E. The isomorphism question for these and other subrecursive classes has in recent years come under study and some interesting results have been achieved. In many ways the non- deterministic classes are the more interesting as they intuitively seem more similar to NP, not being closed under complement. We begin, however, with deterministic exponential time as here the results are the cleanest. In order to motivate our approach let us first briefly review the progenitor of all of these ideas, the result of John Myhill [18]. Myhill proved that all r.e. many-one complete sets are recursively isomorphic. This can be viewed as an effective version of the Cantor-Schroder- Bernstein Theorem from set theory. Its proof has two parts. First it is shown that all many-one complete r.e. sets are one-one complete. This follows from the fact that all many-one complete r.e. sets have padding functions. Next it is proved that any two one-one complete r.e. sets are recursively isomorphic. The proof here is a "back and forth" argument where the recursive isomorphism is constructed value by value using the one-one reductions between the two sets. However, the search required to find the next value of the isomorphism may be very (more than polynomially) long. The analogous proof for subrecursive complete sets fails in several places. While, as we will see, polynomial many-one completeness does imply polynomial one-one complete- ness, the proofs of these facts are quite different in this setting. Furthermore, the results here are not as strong as in the recursion-theoretic case. The one-one reductions are not known to be polynomially invertible, or even length increasing in general. If invertibility of the reduc- tions (or equivalently the existence of invertible padding functions) were shown then p- isomorphism would follow from the results in Section 1. One very nice result for deterministic exponential time is due to Len Berman [2]. He proved, Theorem 3: A set A which is many-one polynomial-time complete for deterministic exponential time is one-one polynomial time complete as well. Furthermore, the one-one reductions to A can be made to be length increasing. Proof (from Ganesan and Homer [5]): Let A be any arbitrary <g-complete set in E and let K be the complete set for E defined above. Since K is 1-1, length-increasing complete, it is enough to show that K <~-l,tiA. (<-~-l,ti denotes a one-one, length-increasing polynomial-time reduction.) Let f 1,f2 .... be an ennumeration of all polynomial time computable functions, such that ~.i,x. f i ( x ) can be computed in time 20(lil+lxl). We construct a set M in E such that the reduction, say, f j from M to A is 1-1-1i on {j} × N. In addition, the set M is constructed so that the function, g(x) = (j,x) will be a reduction from K to M. The required 1-1-1i reduction from K to A is then f (x)=f) (g (x)). The following program describes the set M. 1. input (i,x) 2. if I f i ( i , x ) l<l ( i , x ) l 3. then accept (i,x) i f f f i (i,x) 4 A. 4. else if there exists y < x such that f i (i,x) = f i (i,y) 5. then accept (i,x) iff y d K 6. else accept (i,x) i f fxeK. Lemma : M is in E. Proof: Let us compute the time required for M on input (i,x). Note that computing f i (i ,x ) takes time 2°(I i I+lx I). Since, there are only 2°(l(i.x)l) strings of the form (i,y) less than (i,x) all of them can be computed in time 2 ° ( I( i,x)l). Hence the condition on line 5 of the algorithm can be performed in 21(i,x)l steps. There are only three cases where the decision to accept (i,x) is made. Case 1: If i (i ,x)[_<[ (i ~c)[. In this we accept (i,x) iff f i (i ,x) is not in A. This can obviously be done in time 21(i,x)l as A is in E. Case 2: The condition on line 4 holds. Since ]y[ < [(i,x)l membership of y in K can be decided in time 21(i,x)l. Case 3: M accepts (i,x) i f fxeK. This can be done in time 21(i,x)l. It is clear from the above cases that M is in E. Lemma: I f f j is a reduction from M to A, then f j is 1-1-5 on {j } x N. Moreover, g(x) = (j,x) is a reduction from K to M. Proof: If f j is not length increasing, it is not a reduction from M to A because of line 3 of the construction. So, f j has to be length increasing. Suppose, f j is not 1-1. Let x2 be the least element such that for some x l <x 2, f j (j ,x 2)=f j (j ,x l). By definition of M, ( j ,xl)eM iff x laK ,O',x2)f-M i f f x l d K . So, f j can not be a reduction from M to A, a contradiction. Hence f ) is 1-1-1i on {j} x N. Note that ( j , x ) ~ / i f f x e K from the way M is defined. The elements of the form (j,x) will always fall in Case 3 of the algorithm. Hence, g(x) = (j,x) is a reduction from K to M. Lemma: K <f-l.liA. Proof: Define f (x)=fj (g (x)). Clearly g is 1-1-1i. Since f j is 1-1-1i on the range of g, f is 1-1 and length increasing as well. f is also computable in polynomial time. It is easy to check that f is a reduction from K to A. The next (and final) step toward showing that all exponential time complete sets are p- isomorphic would be to show that the reductions can be made to be polynomial-time inverti- b!e. That is, many-one completeness implies one-one invertible completeness. In fact, if this were the case, Theorem 2 would yield a solution to the isomorphism problem in this setting. Unfortunately, whether the reductions can be strengthened to be invertible remains an open problem. Next, a related and somewhat more tractable problem is considered. We are unable to determine the structure of the many-one polynomial degree of the complete set for E. Is there a polynomial <g-degree of a set in E whose p-isomorphism class we can determine ? In par- ticular, can we find such a degree that collapses or doesn't collapse? It is not difficult to construct an infinite exponential time set A which is polynomially immune (that is, contains no infinite polynomial subset). Clearly such an A is not p- isomorphic to A x N. However, A _<g A x N via f(x)=(x,1) and A x N <g A via f(x,y)=x. So A x N and A are in the same _<g-degree and we have an example of a polynomial many-one degree which does not collapse. The construction of such a set A is given in Kurtz, Mahaney and Royer [11]. In fact, they construct such a set which is complete with respect to polyno- mial 2-truth-table reducibility, a slightly weaker reducibility than _<g. Intuitively A is 2- truth-table reducible to B (A <--~-tt B) if and only if there is a polynomial time computable function f such that for each x, f(x) is a list of at most two string w and z, and whether x is in A can be determined as a boolean functions of the answers to whether w and z are in B. Kurtz, Mahaney and Royer [1 I] show, Theorem 4: There is a p-immune set in E which is 2-tt complete for E. Until quite recently it was not known if any polynomial many-one degree (complete or not) was collapsing. The first such example is found in [11] where it is shown, Theorem 5: There is a set A in E which is 2-tt complete for exponential time and whose poly- nomial many-one degree collapses. The proof is not given here. It is a finite injury priority argument from recursion theory. Both of the above theorems hold for any deterministic subrecursive complexity classes con- taining E as well. There seems to be no way to strengthen the argument and make A many- one complete, hence settling the conjecture for exponential time. For nondeterministic exponential time (NE) the situation is somewhat more difficult. This is due to the nondeterminism and in particular the fact that the class is probably not closed under complement. Nonetheless, this and other nondeterministic classes are in some respects the more interesting as it is, after all, a nondeterministic classes in which we are the most interested. Only one part of the above theorems holds for nondeterministic classes as well. The next two results can be found in Ganesan and Homer [5]. Theorem 6: A set A which is many-one polynomial-time complete for nondeterministic