We exhibit a relativized world where the class of sparse NP sets has no complete sets. This gives the first 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.
DIMACS Home Page