I am relatively new to complexity and computability theory. I just came across the concept of [Permanent](http://en.wikipedia.org/wiki/Permanent) of a matrix and read that it is NP hard problem to compute the permanent of 0-1 matrix. 
Of course it struck me with surprise as it would have to anyone new that it is NP hard where determinent is polynomial. Could any one give an easy proof of this by reducing any other NP complete problem into this?



NP Hardness proof for permanent of 0-1 matrix
[Les Valiant's original paper](http://www.math.washington.edu/~billey/colombia/references/valiant.permanent.1979pdf.pdf) is beautifully written.


**EDIT** A simpler proof, with a nice explanation (see Section 3) is given by [Ben-Dor and Halevy](http://people.csail.mit.edu/shaih/pubs/01perm.pdf)


