On the structure of complete sets: Almost everywhere complexity and infinitely often speedup
- 1 October 1976
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 76-80
- https://doi.org/10.1109/sfcs.1976.22
Abstract
In this paper we investigate the structure of sets which are complete for various classes. We show, for example, that sets complete for deterministic time classes contain infinite polynomial time recognizable subsets, thus showing that they are not complex almost everywhere. We show by a related technique that any set complete for NEXP_TIME contains an infinite subset in DEXP_TIME, thereby showing that these sets do not require the use of non-determinism almost everywhere. Furthermore, we show that complete sets for deterministic time classes have effective I.O. speed-up to a polynomial; this strengthens a result of Stockmeyer.Keywords
This publication has 4 references indexed in Scilit:
- On isomorphisms and density of NP and other complete setsPublished by Association for Computing Machinery (ACM) ,1976
- On time versus space and related problemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1975
- On Reducibility to Complex or Sparse SetsJournal of the ACM, 1975
- A Machine-Independent Theory of the Complexity of Recursive FunctionsJournal of the ACM, 1967