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)?

  • $\begingroup$ 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)? $\endgroup$ – Joshua Grochow Apr 28 '17 at 15:36
  • $\begingroup$ @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. $\endgroup$ – Turbo Apr 28 '17 at 17:00

It puts NP into P/poly, and therefore collapses PH to its second level.

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$.

  • $\begingroup$ thank you also would a deterministic or a randomized short certificate for no instances of unambiguous SAT problem or its equivalent have any consequences? $\endgroup$ – Turbo May 1 '17 at 8:10
  • 1
    $\begingroup$ 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. $\endgroup$ – Joshua Grochow May 1 '17 at 17:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.