On Certain Polynomial-Time Truth-Table Reducibilities of Complete Sets to Sparse Sets
- 1 August 1983
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 12 (3) , 411-425
- https://doi.org/10.1137/0212027
Abstract
No abstract availableKeywords
This publication has 9 references indexed in Scilit:
- Sparse complete sets for NP: Solution of a conjecture of Berman and HartmanisPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1980
- A Note on Sparse Complete SetsSIAM Journal on Computing, 1979
- 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 Sets Cook-Reducible to Sparse SetsSIAM Journal on Computing, 1976
- A comparison of polynomial time reducibilitiesTheoretical Computer Science, 1975
- On Reducibility to Complex or Sparse SetsJournal of the ACM, 1975
- Tally languages and complexity classesInformation and Control, 1974
- Reducibility among Combinatorial ProblemsPublished by Springer Nature ,1972