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?

$\endgroup$

1 Answer 1

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

$\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
    Apr 30, 2015 at 0:06
  • $\begingroup$ @Naman See the edit. $\endgroup$
    – Igor Rivin
    Apr 30, 2015 at 0:17

Not the answer you're looking for? Browse other questions tagged or ask your own question.