DIMACS TR: 99-48

Optimal Proof Systems and Sparse Sets

Authors: Harry Buhrman, Steve Fenner, Lance Fortnow and Dieter van Melkebeek


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.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1999/99-48.ps.gz
DIMACS Home Page