Sparse Sets in : Relativizations
Stuart A. Kurtz · SIAM Journal on Computing · 1985
We construct an oracle relative to which ${\bf P} e \bf {NP}$ and there are no sparse sets in $\bf {NP}$–$\bf {P}$. The well-known construction of Baker, Gill and Solovay [SIAM J. Comput., 4 (1975), pp. 431–442] gives an oracle relative to which there is a sparse set in $\bf {NP}$–${\bf P}$. Together, these results show that simple modifications of conventional proof techniques cannot establish whether or not sparse sets exist in $\bf {NP}$–$\bf {P}$, even if one assumes ${\bf P} e \bf {NP}$.