Skip to main content

All Questions

Filter by
Sorted by
Tagged with
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 ...
Henry Yuen's user avatar
  • 3,888