Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [unique-solution]

The tag has no usage guidance.

1
vote
1answer
128 views

Unambiguous SAT and sparse languages

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 ...
6
votes
1answer
177 views

What's the relationship between ASP-complete and #P-complete?

Given that ASP-reductions by definition are parsimonious and parsimonious reductions preserve #P-completeness, one might think that the counting version of all ASP-complete problems are also #P-...
4
votes
1answer
235 views

UnambiguousSAT reductions

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 ...
14
votes
1answer
405 views

NP-Complete problems that admit an efficient algorithm under the promise of a unique solution

I was recently reading a very nice paper by Valiant and Vazirani which shows that if $\mathbf{NP \neq RP}$, then there can not be an efficient algorithm to solve SAT even under the promise that it is ...
4
votes
1answer
231 views

Evidence that UniqueSat is dense

UniqueSAT ={$\phi$| $\phi$ has unique satisfying assignment } represents an important class of computational problems. Unique SAT is CoNP-hard and $US$-complete. What is the density of UniqueSAT? ...
5
votes
1answer
977 views

Reduction from SAT to 0,1 integer linear program with zero or one solutions

Probably this is well known. There is probabilistic reduction from SAT to Unique SAT (0 or 1 solutions). According to answer and comments derandomizing the reduction would imply $PH \subseteq \oplus ...
37
votes
4answers
1k views

Examples where the uniqueness of the solution makes it easier to find

The complexity class $\mathsf{UP}$ consists of those $\mathsf{NP}$-problems that can be decided by a polynomial time nondeterministic Turing machine which has at most one accepting computational path. ...
17
votes
1answer
581 views

What evidence do we have for $\mathsf{UP} \neq \mathsf{NP}$?

Following Josh Grochow's suggestion, I am converting my comment from a previous question into a new question. What evidence do we have for $\mathsf{UP} \neq \mathsf{NP}$? Here $\mathsf{UP}$ is the ...
13
votes
1answer
815 views

Does “Second X is NP-complete” imply “X is NP-complete”?

"Second $X$" problem is the problem of deciding the existence of another solution different from some given solution for problem instance. For some $NP$-complete problems, the second solution ...
-2
votes
1answer
367 views

Can every digital file have a unique fingerprint?

Disclaimer: I am not a CS person but this question is more philosophical in the sense i could not get a good enough answer ANYWHERE ELSE as to how systems such as Youtube content id work. In Youtube ...
14
votes
0answers
208 views

Does requiring uniqueness of valid answers for Merlin limit the power of Arthur-Merlin protocols?

Preamble. The complexity class AM are those problems which can be solved by a two-round interactive proof system between a prover "Merlin" and a verifier "Arthur". A problem — which tests some ...
4
votes
2answers
439 views

Constructing uniquely satisfiable formulas

Unique SAT ={$\phi$| $\phi$ has unique satisfying assignment } represents an important class of computational problems. I recall reading that P=NP iff Unique SAT is in P (I don't remember where I read ...
28
votes
2answers
1k views

Derandomizing Valiant-Vazirani?

The Valiant-Vazirani theorem says that if there is a polynomial time algorithm (deterministic or randomized) for distinguishing between a SAT formula that has exactly one satisfying assignment, and an ...
19
votes
1answer
1k views

Consequences of UP equals NP

EDIT at 2011/02/08: After some references finding and reading, I decided to separate the original question into two separate ones. Here's the part concerning UP vs NP, for the syntactic and semantic ...
16
votes
4answers
882 views

Complexity of finding a second solution given a correct solution to an NP-complete problem

I'm looking to figure out whether there are any general results about or examples concerning the NP-completeness of the problem of finding a second solution to an NP-complete problem. More precisely, ...
25
votes
5answers
2k views

Verifying unique solutions of SAT

Consider the following problem: given a CNF formula and an assignment that satisfies this formula, is there another satisfying assignment for this formula ? What is the complexity of this problem ? (...