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$
$\endgroup$
2
-
$\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 GrochowCommented Apr 28, 2017 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$– TurboCommented Apr 28, 2017 at 17:00
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
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$.
answered Apr 28, 2017 at 19:01
-
$\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$– TurboCommented May 1, 2017 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$ Commented May 1, 2017 at 17:21