Distinguishing conjunctive and disjunctive reducibilities by sparse sets
- 1 April 1989
- journal article
- Published by Elsevier in Information and Computation
- Vol. 81 (1) , 62-87
- https://doi.org/10.1016/0890-5401(89)90029-1
Abstract
No abstract availableKeywords
This publication has 6 references indexed in Scilit:
- On Sets Truth-Table Reducible to Sparse SetsSIAM Journal on Computing, 1988
- A comparison of polynomial time completeness notionsTheoretical Computer Science, 1987
- Sets with small generalized Kolmogorov complexityActa Informatica, 1986
- Relativizing complexity classes with sparse oraclesJournal of the ACM, 1986
- On Isomorphisms and Density of $NP$ and Other Complete SetsSIAM Journal on Computing, 1977
- A comparison of polynomial time reducibilitiesTheoretical Computer Science, 1975