Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR98-027 | 15th April 1998 00:00

#### Sparse sets, approximable sets, and parallel queries to NP

TR98-027
Authors: Vikraman Arvind, Jacobo Toran
Publication: 26th May 1998 20:06
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