TR98-027 Authors: Vikraman Arvind, Jacobo Toran

Publication: 26th May 1998 20:06

Downloads: 2674

Keywords:

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.