Optimal Proof Systems and Sparse Sets Download as PS


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.