The structure of polynomial complexity cores
- 1 January 1984
- book chapter
- Published by Springer Nature
- p. 452-458
- https://doi.org/10.1007/bfb0030328
Abstract
No abstract availableKeywords
This publication has 8 references indexed in Scilit:
- Bi-immune sets for complexity classesTheory of Computing Systems, 1985
- Some structural properties of polynomial reducibilities and sets in NPPublished by Association for Computing Machinery (ACM) ,1983
- Sparse complete sets for NP: Solution of a conjecture of Berman and HartmanisJournal of Computer and System Sciences, 1982
- Completeness, Approximation and DensitySIAM Journal on Computing, 1981
- Relationship between density and deterministic complexity of MP-complete languagesPublished by Springer Nature ,1978
- On Isomorphisms and Density of $NP$ and Other Complete SetsSIAM Journal on Computing, 1977
- On the structure of complete sets: Almost everywhere complexity and infinitely often speedupPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1976
- On Reducibility to Complex or Sparse SetsJournal of the ACM, 1975