Questions tagged [unique-solution]
The unique-solution tag has no usage guidance.
4 questions with no upvoted or accepted answers
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
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
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