2
$\begingroup$

I am relatively new to complexity and computability theory. I just came across the concept of 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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
7
$\begingroup$

Les Valiant's original paper is beautifully written.

EDIT A simpler proof, with a nice explanation (see Section 3) is given by Ben-Dor and Halevy

Improve this answer
$\endgroup$
2
  • $\begingroup$ Actually I am fairly new to this field. I tried to go through the paper but couldn't absorb much. I wanted to start by knowing the reduction steps or something if possible. Maybe I can try that myself if you just give a hint like which problem can be reduced into it. $\endgroup$
    – Naman
    Commented Apr 30, 2015 at 0:06
  • $\begingroup$ @Naman See the edit. $\endgroup$
    – Igor Rivin
    Commented Apr 30, 2015 at 0:17

Not the answer you're looking for? Browse other questions tagged .