<p>Let $\Pi$ be an $\mathsf{NP}$-complete problem. It is standard that $3SAT$ and $\Pi$ are reducible from each other.</p>

<p>Let UnambiguousSAT, or USAT for short, denote the promise problem which is 3SAT but with the promise that there is $\leq 1$ solution (that is, it is in $\mathsf{PromiseUP}$). Valiant-Vazirani gives a randomized reduction from SAT to USAT.</p>

<p>For some natural problem $\Pi$, let U$\Pi$ is the corresponding promise problem in $\mathsf{PromiseUP}$, and suppose that $\Pi$ randomly reduces to U$\Pi$.</p>

<p>Is it reasonable to expect reduction from U$\Pi$ to USAT and vice versa? Would that mean $\mathsf{PromiseUP}$ has complete problem?</p>

<p>In general if USAT is in $\mathsf{RP}$ then $\mathsf{NP}=\mathsf{RP}$. Can we get something similar for U$\Pi$ as above?</p>

CC BY-SA 3.0
2017-03-05T14:58:05.113Z
UniqueSAT is not a promise problem. UniqueSAT is a complete problem for complexity US. On the other hand, UnambiguousSAT is a promise problem which is associated with complexity class UP
Tayfun Pay
CC BY-SA 3.0
2017-03-06T23:17:07.653Z
Aside from the incorrect terminology in the original question (which I think I've now corrected), I don't understand the downvotes. In light of Ricky Demer's answer, this question turned out to have an easy answer, but that doesn't necessarily deserve a downvote...
Joshua Grochow
CC BY-SA 3.0
2017-03-07T00:10:18.817Z
@JoshuaGrochow Is it okay to answer questions that are posed with wrong terminology without correcting it? No Is it okay to use that wrong terminology within the answer? No.
Tayfun Pay
CC BY-SA 3.0
2017-03-07T01:45:06.120Z
@TayfunPay: I agree with you. But is it okay to downvote questions or answers simply because they are posed with wrong terminology? No. You should correct the terminology either by pointing it out in the comments or by editing it yourself, especially when it is fairly clear what the writer was trying to get at. (When the latter is unclear and cannot be clarified by comments/discussion, then perhaps something deserves a downvote.)
Joshua Grochow
CC BY-SA 3.0
2017-03-07T02:29:14.913Z
@JoshuaGrochow We began to be "this" sensitive? I actually pointed out the misconception in the comments. However, if I had asked this question, especially in this form, several years ago or so, then someone, whose name shall not be mentioned, and his minions, would have down voted it, asked it to be closed for it not being research level and possibly called me a "crank" along the way...
Tayfun Pay
CC BY-SA 3.0
2017-03-07T14:00:08.030Z
@TayfunPay: I am sorry that you experienced such behavior in the past. I think it is important that we maintain a welcoming and encouraging atmosphere, in the spirit of teaching and learning from one another. I think that whether a question is research-level or not should be about the content of the question, not about whether or not the questioner knows the right terminology with which to ask it (again, modulo issues of clarity, as in my previous comment).
Joshua Grochow
CC BY-SA 3.0
2017-03-07T22:50:26.243Z
Incidentally, this sort of promise problem is important as the type that typically comes up in solving logic puzzles. Usually the puzzle itself promises exactly one solution rather than at most one solution, but the decision problem "if I make this single additional step in my partial solution, is there still a solution?" is what you need in solving these puzzles and is of this type.
David Eppstein
CC BY-SA 3.0
2017-03-09T05:07:09.200Z
I think the question, or at least most of it, is on the level of a graduate / advanced undergrad exercise, and is not really research level.
Sasho Nikolov
CC BY-SA 3.0
2017-03-10T12:38:01.027Z
How is the "the corresponding promise problem" defined? In particular the UP promise is a restriction on NTMs, I don't see how you will apply it to a the language $\Pi$.
Lance Fortnow
CC BY-SA 3.0
2017-03-11T22:13:59.183Z
@LanceFortnow naively cant you take a parsimonious reduction to 3SAT as Ricky Demer says (is it possible) and apply a similar restriction there?
Turbo
CC BY-SA 3.0
2017-03-12T15:34:25.503Z
True, if you consider $\Pi$ not as a language but as a polynomial-time computable relation where $(x,w)$ is in $\Pi$ if $w$ is a witness for $x$.
Lance Fortnow
<reductions><randomness><np-complete><unique-solution><promise-problems>
UnambiguousSAT reductions
Turbo
# UnambiguousSAT reductions

(Asked by: username_0 on 2017-03-05)

Let $\Pi$ be an $\mathsf{NP}$-complete problem. It is standard that $3SAT$ and $\Pi$ are reducible from each other.

Let UnambiguousSAT, or USAT for short, denote the promise problem which is 3SAT but with the promise that there is $\leq 1$ solution (that is, it is in $\mathsf{PromiseUP}$). Valiant-Vazirani gives a randomized reduction from SAT to USAT.

For some natural problem $\Pi$, let U$\Pi$ is the corresponding promise problem in $\mathsf{PromiseUP}$, and suppose that $\Pi$ randomly reduces to U$\Pi$.

Is it reasonable to expect reduction from U$\Pi$ to USAT and vice versa? Would that mean $\mathsf{PromiseUP}$ has complete problem?

In general if USAT is in $\mathsf{RP}$ then $\mathsf{NP}=\mathsf{RP}$. Can we get something similar for U$\Pi$ as above?

**Tags:** reductions, randomness, np-complete, unique-solution, promise-problems
> **Comments:**
> **username_1**: UniqueSAT is not a promise problem. UniqueSAT is a complete problem for complexity US. On the other hand, UnambiguousSAT is a promise problem which is associated with complexity class UP  
> **username_2**: Aside from the incorrect terminology in the original question (which I think I've now corrected), I don't understand the downvotes. In light of Ricky Demer's answer, this question turned out to have an easy answer, but that doesn't necessarily deserve a downvote...  
> **username_1**: @JoshuaGrochow Is it okay to answer questions that are posed with wrong terminology without correcting it? No Is it okay to use that wrong terminology within the answer? No.  
> **username_2**: @TayfunPay: I agree with you. But is it okay to downvote questions or answers simply because they are posed with wrong terminology? No. You should correct the terminology either by pointing it out in the comments or by editing it yourself, especially when it is fairly clear what the writer was trying to get at. (When the latter is unclear and cannot be clarified by comments/discussion, then perhaps something deserves a downvote.)  
> **username_1**: @JoshuaGrochow We began to be "this" sensitive? I actually pointed out the misconception in the comments. However, if I had asked this question, especially in this form, several years ago or so, then someone, whose name shall not be mentioned, and his minions, would have down voted it, asked it to be closed for it not being research level and possibly called me a "crank" along the way...  
> **username_2**: @TayfunPay: I am sorry that you experienced such behavior in the past. I think it is important that we maintain a welcoming and encouraging atmosphere, in the spirit of teaching and learning from one another. I think that whether a question is research-level or not should be about the content of the question, not about whether or not the questioner knows the right terminology with which to ask it (again, modulo issues of clarity, as in my previous comment).  
> **username_3**: Incidentally, this sort of promise problem is important as the type that typically comes up in solving logic puzzles. Usually the puzzle itself promises exactly one solution rather than at most one solution, but the decision problem "if I make this single additional step in my partial solution, is there still a solution?" is what you need in solving these puzzles and is of this type.  
> **username_4**: I think the question, or at least most of it, is on the level of a graduate / advanced undergrad exercise, and is not really research level.  
> **username_5**: How is the "the corresponding promise problem" defined? In particular the UP promise is a restriction on NTMs, I don't see how you will apply it to a the language $\Pi$.  
> **username_0**: @LanceFortnow naively cant you take a parsimonious reduction to 3SAT as Ricky Demer says (is it possible) and apply a similar restriction there?  
> **username_5**: True, if you consider $\Pi$ not as a language but as a polynomial-time computable relation where $(x,w)$ is in $\Pi$ if $w$ is a witness for $x$.  

---

## 0 answers

