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

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

CC BY-SA 3.0
2017-05-01T08:10:08.560Z
thank you also would a deterministic or a randomized short certificate for no instances of unambiguous SAT problem or its equivalent have any consequences?
Turbo
CC BY-SA 3.0
2017-05-01T17:21:50.920Z
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.
Joshua Grochow
CC BY-SA 3.0
2017-04-28T19:01:28.823Z
2017-04-28T19:01:28.823Z
Joshua Grochow
<p>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)?</p>

CC BY-SA 3.0
2017-04-28T15:36:52.373Z
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)?
Joshua Grochow
CC BY-SA 3.0
2017-04-28T17:00:35.140Z
@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.
Turbo
<big-picture><np-complete><derandomization><p-vs-np><unique-solution>
Unambiguous SAT and sparse languages
Turbo
# Unambiguous SAT and sparse languages

(Asked by: username_0 on 2017-04-27)

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

**Tags:** big-picture, np-complete, derandomization, p-vs-np, unique-solution

> **Comments:**
> **username_1**: 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)?  
> **username_0**: @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.  

---

## 1 answers

### Answer by username_1 on 2017-04-28. Score: 2 | Accepted answer

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

> **Comments:**
> **username_0**: thank you also would a deterministic or a randomized short certificate for no instances of unambiguous SAT problem or its equivalent have any consequences?  
> **username_1**: 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.  

---

