IMMUNITY OF COMPLETE PROBLEMS

Authors
HOMER S WANG J
Citation
S. Homer et J. Wang, IMMUNITY OF COMPLETE PROBLEMS, Information and computation, 110(1), 1994, pp. 119-129
Citations number
17
Categorie Soggetti
Information Science & Library Science",Mathematics,"Computer Science Information Systems
Journal title
Information and computation → ACNP
ISSN journal
08905401
Volume
110
Issue
1
Year of publication
1994
Pages
119 - 129
Database
ISI
SICI code
0890-5401(1994)110:1<119:IOCP>2.0.ZU;2-X
Abstract
Two necessary and sufficient conditions for all E-complete sets to con tain dense P subsets are shown. We then prove that every less-than-or- equal-to m(p)-hard for E set and its complement contain dense E and UP subsets. As a corollary, every NE-complete set and its complement con tain dense E and UP subsets. (C) 1994 Academic Press, Inc.