Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR98-027 | 15th April 1998 00:00

Sparse sets, approximable sets, and parallel queries to NP

RSS-Feed




TR98-027
Authors: Vikraman Arvind, Jacobo Toran
Publication: 26th May 1998 20:06
Downloads: 3241
Keywords: 


Abstract:

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 if SAT is
$O(\log n)$-approximable
then FP$^{\rm NP}_{||}$ = FP$^{\rm NP[log]}$.
Since FP$^{\rm NP}_{||}$ = FP$^{\rm NP[log]}$.
implies that SAT is $O(\logn)$-approximable,
these two hypotheses are
shown to be equivalent, thus solving an open question from
Buhrman Fortnow and Torenvliet. We show as a consequence of our first result
that if an NP-complete set or a coNP-complete set is
disjunctively reducible to a sparse set of polylogarithmic
density then P=NP.



ISSN 1433-8092 | Imprint