THE UNIVERSITY OF MICHIGAN COMPUTING RESEARCH LABORATORY1 Equivalence Relations, Invariants. and Normal Forms Andreas Blass and Yuri Gurevich CRL-TR-9-82 DECEMBER 1982 Computing Research Laboratory Room 1079, East Engineering Building Ann Arbor, Michigan 48109 USA Tel: (313) 763-8000 IAll correspondence should be sent to Professor Yuri Gurevich. Any opinions, findings, and conclusions or recommendations expressed in this publication are those of the authors and do not necessarily reflect the views of the funding agencies.

' hit s t t -.,,~

Equivalence Relations, Invariants, and Normal Forms by Andreas Blass Department of Mathematics and Yuri Gurevich Department of Computer and Communication Sciences The University of Michigan Ann Arbor, MI 48109 December 1982

- 1 - Abstract For an equivalence relation E on the words in some finite alphabet, we consider the recognition problem (decide whether two words are equivalent), the invariant problem (calculate a function constant on precisely the equivalence classes), the normal form problem (calculate a particular member of an equivalence class, given an arbitrary member), and the first member problem (calculate the first member of an equivalence class, given an arbitrary member). A solution for any of these problems yields solutions for all earlier ones in the list. We show that, for polynomial time recognizable E, the first member problem is always in P the class A2 (solvable in polynomial time with an oracle for an NP set) and can be complete for this class even when the normal form problem is solvable in polynomial time. To distinguish between the other problems in the list, we construct an E whose invariant problem is not solvable in polynomial time with an oracle for E (although the first member problem is in NPE co-NPE) and we construct an E whose normal form problem is not solvable in polynomial time with an oracle for a certain solution of its invariant problem.

Introduction This paper was stimulated by [3] where finite structures (e.g. graphs) were considered as inputs for algorithms. Since one is usually interested only in the isomorphism types of structures, it is natural to ask whether these types can be represented in a form suitable for use as inputs in place of the structures themselves. To avoid trivial "solutions", we insist that the isomorphism type of a structure be (rapidly) computable when the structure itself is given. For this to be possible, it is necessary that the isomorphism problem, for the structures considered, be (rapidly) solvable; indeed, to tell whether two structures are isomorphic, one just computes their isomorphism types and checks whether they are equal. Is this necessary condition sufficient as well? That is, does a solution of the isomorphism problem yield a presentation of the isomorphism classes as well? In many cases it does, because the solution of the isomorphism problem proceeds by calculating an invariant (or a system of invariants) such that two structures of the sort considered are isomorphic exactly when their invariants agree. In such a case, the invariants themselves can be used as a presentation of the isomorphism classes. It is not at all obvious, however, that every solution of an isomorphism problem must yield such invariants. For example, the solution in [2] for trivalent graphs does not appear to yield invariants. We shall show, in the more general setting of arbitrary equivalence relations rather than isomorphism, that one cannot, in general, calculate invariants even if one can tell when two objects are equivalent. We shall also consider two problems more difficult than the invariant problem. One is obtained by insisting that the invariant be a member of the equivalence class it represents. In the isomorphism-type situation discussed above, this amounts to insisting that one can (rapidly) compute, from an isomorphism type, some structure

- 3 - in it. An even more difficult problem arises if one insists that the invariant be the first (in some suitable ordering) member of the equivalence class. We shall prove that each of these problems is strictly more difficult than its predecessor. To make these ideas precise, we consider an equivalence relation E over Z*, where Z is a finite alphabet, and we consider the following four problems. Recognition problem: Given x and y in Z*, determine whether xEy. * * Invariant problem: Calculate, for x in Z, an invariant F(x) (in 1 for some finite alphabet E1) such that, for all x and y in E, xEy if and only if F(x)=F(y). * Normal form problem: Calculate, for x in Z, a "normal form" F(x) (in Z*) such that, for all x and y in Z, xEF(x) and if xEy then F(x)=F(y). First member problem: Calculate, for x in E*, the first y such that xEy. In the first member problem, "first" refers to the following standard ordering of E: y precedes z if either y is shorter than z or they have the same length and y lexicographically precedes z. For many of the equivalence relations we consider, equivalent words have the same length, so "first" can be understood as "lexicographically first". It is clear that any solution of the first member problem solves the normal form problem and that any solution to the normal form problem solves the invariant problem. Furthermore, given a solution of the invariant problem, we can solve the recognition problem by computing and comparing F(x) and F(y). In the context of ordinary recursion theory, all four problems are equivalent, for, if we know how to solve the recognition problem, then we can solve the first member problem by testing each y in E in turn (in standard order) until we find one equivalent to x. Since the search is bounded by x, the problems remain

- 4 - equivalent if we consider only primitive recursive computations. Our objective is to prove that all four problems are inequivalent in the context of polynomial time computability. (They are also inequivalent in higher-type recursion theory, but that does not concern us here.) Unfortunately, this objective cannot be achieved without proving P#NP. Indeed, the search procedure indicated above implies that, when the recognition problem is in P, the first member problem is in the polynomial hierarchy of Stockmeyer [4] and is therefore in P if P=NP. More precisely, the first member problem is in Stockmeyer's class Ap, that is, it is computable in polynomial time 2' with an oracle for an NP set, if E is in P. The computation proceeds as follows, using an oracle for the NP set {(x,y) Some member of the equivalence class of x precedes y}. Given x, we begin by querying the oracle about (x,l ), for various values of ~<length(x), to determine by binary search the length m of the first y in the equivalence class of x; this takes approximately log(length(x)) steps. Then we m-1 query the oracle about (x,lO1 ) to determine the first digit yl of the desired y. Then we query about (x,y1lO10 ) to determine the next digit y2, etc. In m such steps we determine all of y. We shall, in Section 1, show that the complexity estimate just obtained is P optimal by constructing an E whose first member problem is A2-complete while the normal form problem has a solution in P (and therefore so do the invariant and recognition problems). This result implies that, if P~NP, the first member problem is strictly harder than the normal form problem. In Section 2, we shall show that the invariant problem is strictly harder than the recognition problem by constructing an equivalence relation E whose invariant problem has no solution computable in polynomial time with an oracle for E. We improve this result by showing that we can simultaneously arrange for the

- 5 - E [' first member problem to be in NP r co-NP. Then we show that the normal form problem is strictly harder than the invariant problem by constructing an equivalence relation E and a solution F of its invariant problem such that no solution of the normal form problem is computable in polynomial time with an oracle for F. The corresponding result for the normal form and first member problems, namely the existence of an equivalence relation E and a solution F of its normal form problem such that the first member problem is not solvable in polynomial time with an oracle for F, follows immediately from the result of Section 1, relativized to an oracle A such that P ANP [1]. Nevertheless, we present a direct and somewhat simpler construction of such E and F using some of the same methods as the other constructions in Section 2. Finally, in Section 3, we formulate some open problems.

- 6 - 1. The first member problem P We show, in this section, that the upper bound of A for the complexity of 2' the first member problem associated to a polynomial time computable equivalence relation, is optimal, even if we require a polynomial time solution for the normal form problem rather than just the recognition problem. Theorem 1. There is an equivalence relation E on {0,1} for which the normal form problem is solvable in polynomial time but the first member problem is P A2-complete. Remarks.l. When we say that the problem of computing a certain function F from E to r.1 is complete for (or hard for, or in) a certain complexity class, we mean that the following decision problem is complete for (or hard for, or in) * that class: Given a word x in E, a letter a in E1, and a positive integer n th (in binary notation), decide whether the n letter in F(x) is a. 2. In the statement and proof of Theorem 1, completeness refers to log-space reductions. (The proof of the weaker result, where completeness refers to polynomial time reduction, would be no easier, although the words w in the proof could then be assumed to be empty by coding them into m.) Proof. We shall work with the alphabet {0,1,2}; the reduction to {0,1} is routine. Let A be a fixed NP-complete set in {0,1},and consider the following k auxiliary problem. An instance of the problem is m2w2, where m is a word in {0,1}* coding, in some standard way, a query machine M (a deterministic Turing machine with alphabet {0,1} that is to interact with an as yet unspecified oracle), w is a word in {0,1}, and k is a positive integer. The question in the instance k m2w2 of the auxiliary problem is whether machine M with oracle A, henceforth written MA, with input w, halts in fewer than k steps. It is routine to check P that this problem is A2 *:~~~~~~2

- 7 To prove the theorem, we shall define an equivalence relation E on {0,1,2}, give a polynomial time computable solution for its normal form problem, and give a log-space computable reduction of the auxiliary problem to the first member problem for E. To define E, we fix a particular nondeterministic Turning machine N that accepts our NP-complete set A in time bounded by a polynomial. Let p be a monotone increasing polynomial (essentially the square of the time bound) such that every computation of N with an input of length t can be coded (in a standard way) by some c in {0,1}* of length p(1). Henceforth we shall not distinguish between c and the computation it codes. For each instance of the auxiliary problem, we define its plausible computations to be the words in {0,1,2}* that consist of k (i) m2w2k, followed by (ii) a string al,...,ak of length k, followed by (iii) a single digit h, followed by (iv) a string of length k, which we think of as consisting of k blocks ql,.'qk each having length k, followed by (v) a string of length k.p(k), which we think of as consisting of k blocks cl,...,ck each having length p(k), subject to the requirements that: (a) When the query machine M coded by m is started with input w and allowed to run for k-l steps (or until it halts if this occurs earlier), its first query (if any) to the oracle concerns the unique string q1 such that ql=q'10r for some r. (Note that, by the time bound, length (ql)<k=length(ql), so this makes sense.) If the answer to this first query is al, under the convention that 0 means "Yes" and 1 means "No", then the next query, if any, concerns the q such that q2=q10' for some r. If the answer to the second query is a2,

the next query (if any) concerns the q1 such that q3=q10r for some r. Etc. (Note that, by the time bound, there will be fewer than k queries altogether.) (0) If there are exactly j queries in the computation described in (a), k p(k) then a.=l and qi=0 and c.=0 for j<i<k. 11 1 -(y) If the computation in (a) reaches a halting state, then h=0; otherwise h=l. (6) For each i such that a.=0, c. has the form cl10r where c! is a computation showing that N acepts q!. If a.=l then c. is a string of O's. Observe that the property of being a plausible computation is decidable in polynomial time. k For orientation and future reference, we construct, for each m2w2k, a particular A plausible computation, called the correct computation. Let the machine M with input w run for k-l steps. Let q,...,q! be its queries to the oracle, and let al,...,aj be the oracle's answers, with 0 representing "Yes". By the time bound, j and each length(q!) must be smaller than k. For each i<j, define qi to be q!lO1 where r is chosen (depending on i) so that length(q.)=k. For k p(k) j<i<k, let a.=l,q.=O,c. =O as required by (B). Note that, with our choices of a's and q's, the computation of M with oracle A is exactly the computation described in (a) above. Let h be 0 if this computation enters a halting state, and 1 otherwise. Finally, define c. to be 0p) if a.=l and to be c!10 if 1 1 1 a.=O, where c! is a computation of N accepting q!, where r is chosen to make length(ci)=p(k), and where c! is chosen, among all computations accepting q!, so that c. is lexicographically as early as possible. It is immediate that k k s=m2w2 a.. a hq...qc.t..ck is a plausible computation for m2w2. We call it s kh1.k l K k the correct computation for m2w2. The important fact about this correct computation is that it lexicographically k precedes all other plausible computations for m2w2. Indeed, suppose

- 9 - s*=m2w2 a *...ak*h*ql*...qk*c*...c* were a lexicographically earlier plausible k computation for the same m2w2. If the first difference between these two plausible computations occurs at ai, then we would have a.=O and a.=l. The computations described in (a) for s and s* are identical up to, but not including, the th oracle's response to the i query. In particular, that query itself is the same: qi=q*. Since a*=O, condition (6) for s* quarantees that c* contains a 1i 1 computation c*' of N accepting q*. So qi.A. But this contradicts the fact, expressed by a="1. that the A oracle responded negatively to query qi. Therefore, the first difference between s and s* must come later than all the a.'s. The 1 computations described in (a) for s and s* are therefore the same. Thus h=h* (by (y)) and q.=q* for all i (by (a) and (s)). The first difference between s 1 1 and s* must therefore be at some ci, and, by (6), we must have a.=0 for this i. But then we cannot have c* lexicographically preceding ci, because of the way we close c. for the correct computation. We are, at last, ready to define E. For each m2w2, we put into one equivak t lence class all its plausible computations together with the extra word m2w2 1, where ~=k(p(k)+k+l)+l. This value of t was chosen so that the extra word has k the same length as the plausible computations for m2w2. Note that the extra word is always the (lexicographically) last member of its equivalence class. To complete the definition of E, we declare that any word that is neither a plausible computation nor an extra word shall be equivalent only to itself. The normal form problem for E is solved by the following polynomial time algorithm. Given x, check whether it is a plausible computation for its maximal initial segment ending with a 2. If not, give x as output. If so, give the extra word for that initial segment as output. This algorithm always produces the last member of the equivalence class of x.

- 1U - The auxiliary problem is reduced to the first member problem for E by the k following algorithm. Given an instance m2w2 of the auxiliary problem, calculate k t l=k(p(k)+k+l)+l, and then find the first member of the equivalence class of m2w2 1 If the digit h in position length(m2w)+2k+l is 0 then give "Yes" as output; otherwise give "No". This algorithm works because the equivalence class of the k Z k extra word m2w2 k contains all the plausible computations for m2w2 and its first k member is, as we saw above, the correct computation for m2w2; the h digit in this k correct computation encodes the answer to the auxiliary problem for m2w2.c

- 11 - 2. Oracles The main result of this section is that, in the context of polynomial time computability, the recognition problem, the invariant problem, the normal form problem, and the first member problem are of strictly increasing complexity. None of these problems can be reduced in general to the previous problem on the list. Theorem 2. (a) There is an equivalence relation E on {0,1}* such that the invariant problem for E cannot be solved by a polynomial time algorithm with an oracle for E. (b) There are an equivalence relation E on {0,1}* and a polynomially bounded solution F:{O,1}*-{O,1} of its invariant problem, such that the normal form problem for E cannot be solved by a polynomial time algorithm with an oracle for F. (c) There are an equivalence relation E on {0,1} and a polynomially bounded solution F of its normal form problem, such that the first member problem for E cannot be solved by a polynomial time algorithm with an oracle for F. Remarks 1. We think of computation with an oracle for a function F (rather than a predicate) as follows. The machine can write a word x on its query tape and receive from the oracle, in a single computation step, the value of F(x), printed on a special tape. A query of this sort can be simulated by a sequence of queries concerning the predicate "The nth letter in F(x) is a". 2. Theorem 1 is relativizable to any oracle. By taking an oracle relative to which P#NP, as in [1], we immediately obtain part (c) of Theorem 2. Nevertheless we shall give another, more direct proof of (c).

- 12 - Proof. Fix an enumeration M0,M1,... of all polynomial time bounded query machines with alphabet {0,1}, and let pn be the polynomial clock bound of M. We construct the desired equivalence relation E in stages. Initially E is the equality relation on {0,1}. At each stage n we may update E by putting into it two pairs (x,y) and (y,x) for some binary stings x,y of the same length d. Here d <dl<... Thus the resulting equivalence relation has the special properties that each equivalence class has at most two members, the two members of any nontrivial equivalence class are words of the same length, and there is at most one nontrivial equivalence class for each length. In part (b) we construct the desired invariant function F simultaneously with E. Initially F(x)=xl for every binary word x. At a stage n we may update F by stipulating that F(x)= n+l for one or two words x of length d n In part (c) we construct the desired normal form function F simultaneously with E. Initially F is the identity function F(x)=x. At each stage n we may update F by stipulating that F(x)=ldn for one word of length dn. The sequence d <dl<d2<... is chosen in such a way that for each n, dn-0 p (dn)<dn+l and pn(d )<2 1. Thus, computing on an input of length dn, M asks fewer than 2dn-1 queries and each query is shorter than dn+ In the rest of the proof we consider a stage n of the construction. Let x and y range over the binary words of length d=d. Let M=M and p=p. n n n (a) For each x let x' be the result produced by M on the input x when it uses the current E as an oracle. If there are distinct x,y with x'=y' go to the next stage. ME fails to solve the invariant problem for E because ME (x)=x'=y'=M (y) whereas (x,y)~E. (Note that later stages of the construction will not affect the values of M (x) and M (y), because they alter E only on words longer than any query involved in the computation of these values.)

13 Suppose, on the other hand, that x'$y' for all x#y. We say that x affects y if M queries E about (x,y) or (y,x) in the computation of y'. Each y is affected by at most p(d)<2d elements x. Lemma. Let R be a binary relation on a nonempty set S of cardinality 2k. Suppose that for each ueS there are fewer than k elements vcS with (u,v)cR. Then there exist distinct u,vES such that neither (u,v) nor (v,u) is in R. Proof of Lemma. Otherwise, the set of all k(2k-l) two-element subsets of S would be the union of the 2k sets R ={{u,v}:(u,v) R} u each of which has cardniality <k-l. This is a contradiction. The lemma is proved. By the lemma (with S={O,1} and R being the relation "is affected by") there are distinct x,y such that neither of x and y affects the other. Put (x,y) and (y,x) into E. This does not alter the computations of x' and y'. E Go to the next stage. M fails to solve the invariant problem for E because (x,y)eE, whereas ME x)=x' y'=ME(y). (b) For each x let F by the current F with the following change: x d+l F (x)=O1. Let x' be the result computed by M with input x and the oracle x F x If there is an x with x'$x then choose one such x, and update F by making it equal to F. This does not affect the computation of x'. Go to the d next stage. Note that the updated F is one-to-one on {0,1} so that there is no need to update E. Since (x,x')xE, M fails to solve the normal problem for E. Suppose, on the other hand, that x'=x for all x. Choose distinct x and y such that M does not query F about y in the computation of x', and M does not query F about x in the computation of y'. This choice is possible, Y

- 14 -d-l by the lemma, because each computation involves at most p(d)<2 queries. d+i Update F by stipulating F(x)=F(y)=O, put pairs (x,y) and (y,x) into E, and go to the next stage. M fails to solve the normal form problem for F F E because M (x)=xsy=M (y) whereas (x,y)EE. (c) For each x let F be the current F with the following change: x d F (x)=ld. Let x' be the result computed by M with oracle F on input x. x x If there is an x with x'ix, then choose one such x, update F by making it equal to F, put (x,l ) and (1,x) into E, and go to the next stage. M F fails to solve the first member problem for E because M (x)=x'#x whereas x is the first member in its equivalence class. Suppose, on the other hand, that x'=x for every x. In particular d d d (1 )=l1. Choose x<l such that M does not query the oracle about x in the d computation of (1 )'. This choice is possible because the computation involves d-1 at most p(d)<2 queries. Update F by making it equal to F. This does x not change the computations of x' and (1d)' Put (x,ld) and (dx) into F E, and go to the next stage. M fails to solve the first member problem for E F d 1d because M (1 )=l whereas 1d is not the first member in its equivalence class.D Our last result is an improvement of part (a) in Theorem 2. It asserts that the invariant problem can be intractable even when the recognition problem is tractable and the first member problem is nearly tractable. Theorem 3. There is an equivalence relation E an {O,1}* such that (i) the invariant problem for E is not solvable by a polynomial time algorithm with an oracle for E, and (ii) the first member problem for E is in NP and co-NP relative to E. Proof. In the proof of part (a) of Theorem 2 we constructed an equivalence relation E such that every equivalence class has at most two elements, the two

- 15 - members of any nontrivial equivalence class are words of the same length, and there is at most one nontrivial equivalence class for each length. We shall modify the construction so that for each length &>0 there is exactly one nontrivial equivalence class. First make sure that 4p (d )<2 n-3. Then turn to a stage n of the n n construction. Here we first update E by adding to it all pairs (O,1 ) and (1,0 ) such that O<l<d0 if n=O, and d <L<d otherwise. We use the notation 0 n-1 n of the proof of Theorem 2. Let x' be the result produced by M on input xe{0,l} with an oracle for the current E. If there is a pair xfy with x'=y' pick one such pair x,y. Computing x' and y', M queried E about <2p(d) pairs (u,v) altogether. Hence at most 4p(d)<2 -3 words were involved in all those queries. Choose u,ve{0,l} such that u,v,x,y are different and u,v were not involved in the queries of the computations of x',y'. Update E by adding (u,v) and (v,u) to E. This does not alter the computations of x',y'. Go to the next stage. If, on the other hand, x'ly' for all x=y proceed as in the proof of part (a) of Theorem 2. The predicate "y is the first member in the E-class of X" is NP in E by the following procedure. If y<x and (x,y)eE, then accept; if y=x, then guess two distinct but E-related words of the same length as x, and accept if x is not the later of these two words. The complementary predicate is also NP in E by the following procedure. If (x,y)tE then accept; otherwise guess a word z such that (y,z)eE, and accept if z<y.

- 16 - 3. Problems The results in this paper suggest several natural problems. Two that strike us as particularly interesting are the following. 1. Can results similar to ours be obtained if, instead of considering arbitrary equivalence relations, one restricts attention to the relation of isomorphism between (standard representations of) structures? 2. Are there analogs of Theorem 1 for the invariant and normal form problems? That is, is there a polynomial time computable E such that every polynomially bounded solution of its invariant problem is A -hard? And is there an E such 2 that the invariant problem is solvable in polynomial time but every polynomially P bounded solution of the normal form problem is A -hard? 2

17 References 1. T. Baker, J. Gill and R. Solovay, Relativizations of the P=?NP questions, SIAM J. Computing 4(1975), 431-442. 2. Z. Galil, C.M. Hoffmann, E.M. Luks, C.P. Schnorr, and A. Weber, An O(n31og n) deterministic and an O(n ) probabilistic isomorphism test for trivalent graphs, 23rd Annual Symposium on Foundations of Computer Science, IEEE (1982), 118-125. 3. Y. Gurevich, Why first-order logic?, in preparation. 4. L.J. Stockmeyer, The polynomial-time hierarchy, Theoret. Comp. Sci. 3(1977), 1-22.

EQUIVALENCE RELATIONS, INVARIANTS, AND NORMAL FORMS ERRATA page 6 6 9 14 15 15 line 13 -1 14 -6 15 17 reads binary P A2 close E an x = y X should read unary P-complete chose E on x # y x Also replace the last two the first-member function 6." sentences on page 15 with "It follows immediately that for E is in NP EFco-NP in sense of Remark 1 on page Remark: 1. When we say that a function F 2), we mean that the length of length of x. is polynomially bounded (as in Theorem F(x) is bounded by a polynomial in the 2. The first of these corrections has no real effect when, as in the present paper, the functions in question are polynomially bounded, but in the general situation "unary" is correct.

UNIVERSITY OF MICHIGAN rl r111111111111 f II I 3 9015 02527 8329 THE UNIVERSITY OF MICHIGAN DATE DUE rI / -, (