# Unambiguous SAT and sparse languages

What is the consequence if there are only polynomially many 'yes' classes of instances of a language that is polynomial time reducible from a problem equivalent to UnambiguousSAT (such as possibly unique subset sum)?

• UnambiguousSAT is a promise problem. When you say it reduces to a sparse language S, do you have in mind the usual thing of allowing the reduction to give arbitrary answers on instances that don't satisfy the promise (ie, which have more than one satisfying assignment)? Apr 28 '17 at 15:36
• @JoshuaGrochow yes I think allowing arbitrary answers for instances not satisfying promise is the right thing to do (is there another alternative?). But it seems to me that then it might trivialize the query. Apr 28 '17 at 17:00

By basically the same as the usual proof that BPP is in P/poly, there is polynomial advice that provides good random bits for the randomized reduction of Valiant-Vazirani. Use that advice to produce the queries to UnambiguousSAT. Apply the reduction from UnambiguousSAT to the sparse language $S$ - which is in P/poly - and use the additional advice to decide $S$.
• Yes. You are essentially asking for consequences of $\mathsf{PromiseUP } \subseteq \mathsf{coNP}$ or $\mathsf{PromiseUP} \subseteq \mathsf{coAM}$ (or coMA, depending on what you meant by "randomized certificate"). Valiant-Vazirani says $\mathsf{NP} \subseteq \mathsf{R \cdot PromiseUP}$. So these would have the consequence that $\mathsf{NP} \subseteq \mathsf{R \cdot coNP} \subseteq \mathsf{coAM}$, resp., $\mathsf{NP} \subseteq \mathsf{R \cdot coAM} \subseteq \mathsf{coAM}$. In either case, you still get $\mathsf{NP} \subseteq \mathsf{coAM}$ and thus PH collapses. May 1 '17 at 17:21