Questions tagged [unique-solution]
The unique-solution tag has no usage guidance.
21 questions
11
votes
1
answer
390
views
Theorem 2.4(i) in Valiant-Vazirani paper "NP is as easy as detecting unique solutions"
I have a question about the paper "NP is as easy as detecting unique solutions" by Valiant and Vazirani, specifically the proof of the Theorem 2.4(i).
The proof starts by saying
Clearly, $...
- 113
7
votes
0
answers
185
views
Variation of (derandomized) Valiant-Vazirani
I am interested in the following "improvement" of the Valiant-Vazirani reduction. As pointed out here, under the right derandomization assumptions one can obtain a deterministic polynomial-...
- 1,049
6
votes
0
answers
105
views
Certifying the promise in hard promise problems
Do we happen to know of any promise problems where the problem is both conditionally hard (say, NP-hard) while simultaneously being able to certify that the instance satisfies the given promise?
For ...
- 1,049
1
vote
0
answers
165
views
Algorithms for finding unique solutions of NP-complete problems
The complexity of algorithms that find unique solution for an NP-complete problem (the input is guaranteed to have a unique solution) seems to shed light on the hardness character of different NP ...
- 21.1k
2
votes
0
answers
97
views
A question about UE
Much has been written about the class UP see related (even more in literature)
example question here. Much is understood about the class UP, and its place in collapsing the PH too. UP has a played ...
- 1,261
1
vote
1
answer
237
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 ...
- 13.3k
7
votes
1
answer
649
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-...
- 249
4
votes
1
answer
354
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 ...
- 13.3k
19
votes
3
answers
1k
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 ...
- 419
4
votes
1
answer
301
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?
...
- 21.1k
5
votes
1
answer
1k
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 ...
- 1,955
38
votes
4
answers
2k
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. ...
- 11.4k
19
votes
1
answer
748
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 ...
- 18.3k
11
votes
2
answers
1k
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 ...
- 21.1k
-2
votes
1
answer
450
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 ...
- 5
15
votes
1
answer
304
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 ...
- 8,939
9
votes
2
answers
988
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 ...
- 21.1k
34
votes
2
answers
2k
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 ...
- 3,888
21
votes
1
answer
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 ...
- 7,668
21
votes
4
answers
1k
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, ...
- 311
31
votes
5
answers
3k
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 ? (...
- 411