- 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.
