SETS by GERD WECHSUNG in Jena (G.D.R.)') 0. Iritroduet,ion and Resnlt,s The consequences of the existence of Theorem 1 ([3]). P = KP o There exists a &-complete sparse set d 7 ~ coNP. Theorem 2 ( [ 7 ] ) . P = N P e There exists a SL-complete sparse set in NP. B precursor of Theorem 2 is contained in [5], and in [2] Theorem 2 has been provcd for single latter alphabet languages instead of sparse sets. These results show to what extent it is unlikely that N P or coNP have SL-cornplet'e sparse sets. It, could possibly be the case that P = N P but N P or coNP contains sparse -I ,-complete sets, where ~ is the nondeterministic polynomial t,ime reducibility introduced in [l]: since 5 is a restriction of s , and therefore s ,,-complete set.s could exist which are not 5;-complete. The next two theorems give evidence for spmw &-complete sets not to exist in NP and coNP. :,-complete sparse sets in KP and coNP have been investigated in [ 2 ] . [3], [ S ] , [7] and [ %I . The results can be formulated as follows: Theorem 3. ([lo]). XP = coNP o Thwe exists a &-complete sparse set in CONY. Theorem 4. NP = coNP o There ezists a SY-complete sparse set i 7 b NP. A necessary and sufficient condition for 5 ; tjo be equal to 5 ; , is givcw in [6]. From Corollary 5 . 5; = s y (KP = COKP * P = NP). Replacing 5 ; by the random polynomial time reducibility 5 , iiltroduced in [l] Theorem 6. SP u CONP = .4, o There exists a S,-coaiplete sparse set in CONY. Theorem 7 . SP u coNP = A , o There exists a S,-complete sparse set in NP. From a comparison of Theorems 2 and 7 and of Theorems 4 and 7 we get two further corollaries concerning the relationships between the reducibility notions considered in this paper. a comparison of Theorem 2 and 4 we get we prove the following modifications of Theorems 1 and 2 : Corollary 8. sE= sR -+ ( N P u coN1' = R n coR --t P = NP). Corollary 9. SR = S y 4 (NP = COW -+ Nl'w CONY = R n coR).
l ) A d d e d i n t h e p r o o f : Since the end of 1983 many further results 011 sparfie coniplete sets have been reached which are surveyed in [9].