Ilya Posov

Valiant-Vazirani Theorem

Abstract

Leslie G. Valiant and Vijay V. Vazirani in 1986 wrote a paper with the name `NP is as Easy as Detecting Unique Solutions'. The theorem they proved became the classical theorem in the complexity theory, so sometimes it's even called a lemma instead of a theorem. In this text it will be presented the statement of the theorem, two different proofs, and also it would be some discussion. Both L.G. Valiant and V.V. Vazirani are professors of computer science, L.G. Valiant works at the Harvard University, V.V. Vazirani works at the Georgia Tech and at the University of California, Berkley. They have their homepages and more information about them can be found there: http://people.deas.harvard.edu/~valiant/, http://www-static.cc.gatech.edu/~vazirani/.