Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > APPROXIMABLE SETS:
Reports tagged with approximable sets:
TR98-027 | 15th April 1998
Vikraman Arvind, Jacobo Toran

Sparse sets, approximable sets, and parallel queries to NP

We relate the existence of disjunctive hard sets for NP to
other well studied hypotheses in complexity theory showing
that if an NP-complete set or a coNP-complete set is
polynomial-time disjunctively reducible
to a sparse set then FP$^{\rm NP}_{||}$ = FP$^{\rm NP[log]}$. Using
a similar argument we obtain also that ... more >>>




ISSN 1433-8092 | Imprint