ECCC-Report TR98-027https://eccc.weizmann.ac.il/report/1998/027Comments and Revisions published for TR98-027en-usTue, 26 May 1998 20:06:10 +0300
Paper TR98-027
| Sparse sets, approximable sets, and parallel queries to NP |
Vikraman Arvind,
Jacobo Toran
https://eccc.weizmann.ac.il/report/1998/027We 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.
Tue, 26 May 1998 20:06:10 +0300https://eccc.weizmann.ac.il/report/1998/027