On Sparse Complete Sets
β
Gerd Wechsung
π
Article
π
1985
π
John Wiley and Sons
π
English
β 402 KB
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 i