- Authors: H. Buhrman, S. Fenner, L. Fortnow and D. van
Melkebeek.

- Reference: In
*Proceedings of the 17th International Symposium
on Theoretical Aspects of Computer Science*, pages 407-418, 2000.

- Earlier version:
- H. Buhrman, S. Fenner, L. Fortnow and D. van Melkebeek.
Optimal Proof Systems and
Sparse Sets. In
* Proceedings of 17th International Symposium on Theoretical
Aspects of Computer Science*, 2000.

#### Abstract

We exhibit a relativized world where the class of sparse NP sets has no
complete sets. This gives a relativized world where no optimal
proof systems exist.
We also examine under what reductions the class of sparse NP sets can
have complete sets. We show a close connection between these issues and
reductions from sparse to tally sets.
We also consider the question as to whether the sparse NP sets have a
computable enumeration.