Valiant–Vazirani theorem
E345812
The Valiant–Vazirani theorem is a fundamental result in computational complexity theory showing that solving unique solutions of NP problems is, under randomized reductions, as hard as solving general NP problems, with major implications for the study of randomness and hardness of approximation.
All labels observed (2)
| Label | Occurrences |
|---|---|
| Valiant-Vazirani theorem | 1 |
| Valiant–Vazirani theorem canonical | 1 |
Statements (46)
| Predicate | Object |
|---|---|
| instanceOf |
computational complexity theorem
ⓘ
result in theoretical computer science ⓘ |
| assumes | standard Turing machine model of computation ⓘ |
| canonicalReferenceTitle | NP is as easy as detecting unique solutions ⓘ |
| complexityAssumptionContext | P versus NP ⓘ |
| concernsProblem |
Unique-SAT
ⓘ
satisfiability problem ⓘ |
| field | computational complexity theory ⓘ |
| formalizes | randomized reduction from SAT to Unique-SAT ⓘ |
| hasImplicationFor |
derandomization
ⓘ
hardness of approximation ⓘ isolation lemma techniques ⓘ structure of NP ⓘ |
| implies | NP is contained in RP with an oracle for Unique-SAT ⓘ |
| influenced | isolation lemma in combinatorics and complexity ⓘ |
| isCentralTo |
study of promise problems in complexity theory
ⓘ
study of randomness in computation ⓘ |
| mainTopic |
NP complexity class
ⓘ
promise problems ⓘ randomized reductions ⓘ unique solutions of NP problems ⓘ |
| namedAfter |
Leslie Valiant
ⓘ
Vijay Vazirani ⓘ |
| originalAuthors |
Leslie Valiant
ⓘ
Vijay Vazirani ⓘ |
| originalPublicationType | journal article ⓘ |
| originalPublicationVenue | Theoretical Computer Science ⓘ |
| problemType | decision problem ⓘ |
| proofMethod | probabilistic method ⓘ |
| reductionType | randomized polynomial-time reduction ⓘ |
| relatesClass |
NP
ⓘ
PH ⓘ UP ⓘ ⊕P ⓘ |
| resultType | randomized reduction theorem ⓘ |
| shows |
If there is a polynomial-time algorithm for Unique-SAT then there is a randomized polynomial-time algorithm for SAT
ⓘ
Random hashing can isolate a unique satisfying assignment with non-negligible probability ⓘ Under randomized reductions, NP is no harder than detecting unique solutions in NP ⓘ |
| showsHardnessOf | Unique-SAT ⓘ |
| showsRelationshipBetween | search problems with many solutions and problems with a unique solution ⓘ |
| statesRoughly | Solving SAT instances with a unique satisfying assignment is as hard as solving general SAT under randomized polynomial-time reductions ⓘ |
| usedIn |
hardness results for unique games and related problems
ⓘ
reductions for approximate counting ⓘ |
| usesTechnique |
pairwise independent hash functions
ⓘ
random hashing ⓘ |
| yearProved | 1986 ⓘ |
Referenced by (2)
Full triples — surface form annotated when it differs from this entity's canonical label.
subject surface form:
Leslie Valiant
this entity surface form:
Valiant-Vazirani theorem