Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Selfreducibility:
TR10-163 | 3rd November 2010
Harry Buhrman, Leen Torenvliet, Falk Unger, Nikolay Vereshchagin

Sparse Selfreducible Sets and Nonuniform Lower Bounds

It is well-known that the class of sets that can be computed by polynomial size circuits is equal to the class of sets that are polynomial time reducible to a sparse set. It is widely believed, but unfortunately up to now unproven, that there are sets in $EXP^{NP}$, or even ... more >>>

ISSN 1433-8092 | Imprint