4
$\begingroup$

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?

Improve this question
$\endgroup$
11
  • 3
    $\begingroup$ 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 $\endgroup$
    – Tayfun Pay
    Commented Mar 5, 2017 at 14:58
  • $\begingroup$ 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... $\endgroup$
    – Joshua Grochow
    Commented Mar 6, 2017 at 23:17
  • 1
    $\begingroup$ @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.) $\endgroup$
    – Joshua Grochow
    Commented Mar 7, 2017 at 1:45
  • 1
    $\begingroup$ 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. $\endgroup$
    – Sasho Nikolov
    Commented Mar 9, 2017 at 5:07
  • 1
    $\begingroup$ 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$. $\endgroup$
    – Lance Fortnow
    Commented Mar 10, 2017 at 12:38

1 Answer 1

Reset to default
3
$\begingroup$

"Is it reasonable to expect reduction from ..."


unambiguous$\Pi$ to unambiguousSAT ​ ?
Yes, since SAT is NP-hard under reductions that preserve the number of solutions.

"and vice versa" ?
$\Pi$ is NP-complete and you've assumed that U$\Pi$ "has a randomized reduction from $\Pi$", so there is
a randomized reduction from USAT to U$\Pi$, since there's one from SAT to U$\Pi$. ​ For most natural problems, if U$\Pi$ is non-trivial then one can find a simple reduction from SAT to $\Pi$ that preserves number of solutions. ​ In particular, it's reasonable to expect a reduction from USAT to U$\Pi$. ​ However, I have no clue regarding whether-or-not there's necessarily
a better reduction from USAT to U$\Pi$ (than the one from $\Pi$ to U$\Pi$).



"Would that mean promiseNP has a complete problem?" ​ Yes, since it follows
from NP having complete languages that promiseNP unconditionally does too.



"In general if" unambiguousSAT "is in RP then NP=RP."
"Can we get something similar for" unambiguous$\Pi$?


Yes, as follows:

By NP-hardness of U$\Pi$ under randomized reductions, ​ NP $\subseteq$ BPP . ​ ​ ​ By search-to-decision, probabilistic polynomial-time algorithms can solve all of FNP. ​ By the definition of FNP,
one can efficiently deterministically check whether-or-not an alleged witness is valid.
Finally, if there are no valid witnesses, then one cannot incorrectly find such a witness.

Improve this answer
$\endgroup$
8
  • $\begingroup$ You seem to be confused between UniqueSAT and UnambiguousSAT as well. $\endgroup$
    – Tayfun Pay
    Commented Mar 5, 2017 at 15:02
  • $\begingroup$ I'm just using the OP's term. ​ promiseNP is the set of promise problems that can be solved by NP machines. ​ ​ ​ ​ $\endgroup$
    – user6973
    Commented Mar 5, 2017 at 15:05
  • $\begingroup$ @RickyDemer can you provide reference for 'since SAT is NP-hard under reductions that preserve the number of solutions'? $\endgroup$
    – Turbo
    Commented Mar 8, 2017 at 13:11
  • $\begingroup$ @Turbo Page 67 theoryofcomputing.org/articles/v003a004/v003a004.pdf $\endgroup$
    – Tayfun Pay
    Commented Mar 10, 2017 at 4:01
  • 1
    $\begingroup$ @Turbo look at parsimonious reductions. Those are the reductions that preserve the number of solutions when reducing from A to B. If there is a reduction that preserves the number of solutions then there ought to be a reduction that preserves uniqueness. $\endgroup$
    – Tayfun Pay
    Commented Mar 10, 2017 at 4:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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