A hierarchy theorem for almost everywhere complex sets with application to polynomial complexity degrees
- 31 January 2006
- book chapter
- Published by Springer Nature
- p. 125-135
- https://doi.org/10.1007/bfb0039600
Abstract
No abstract availableKeywords
This publication has 19 references indexed in Scilit:
- What is a hard instance of a computational problem?Published by Springer Nature ,1986
- Bi-immune sets for complexity classesTheory of Computing Systems, 1985
- Hard-core theorems for complexity classesJournal of the ACM, 1985
- A note on deterministic and nondeterministic time complexityInformation and Control, 1982
- The tight deterministic time hierarchyPublished by Association for Computing Machinery (ACM) ,1982
- Some connections between nonuniform and uniform complexity classesPublished by Association for Computing Machinery (ACM) ,1980
- Inclusion complete tally languages and the Hartmanis-Berman conjectureTheory of Computing Systems, 1977
- On the structure of complete sets: Almost everywhere complexity and infinitely often speedupPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1976
- On Almost Everywhere Complex Recursive FunctionsJournal of the ACM, 1974
- On sets having only hard subsetsPublished by Springer Nature ,1974