<p>The <a href="http://en.wikipedia.org/wiki/Permanent" rel="nofollow">permanent</a> of a <a href="http://en.wikipedia.org/wiki/%280,1%29-matrix" rel="nofollow">01-matrix</a> is equal to the number of <a href="http://en.wikipedia.org/wiki/Vertex_cycle_cover" rel="nofollow">vertex cycle covers</a> of an unweighted directed graph. Its computation is <a href="http://en.wikipedia.org/wiki/Sharp-P-complete" rel="nofollow">#P-complete</a>.</p>

CC BY-SA 3.0
2013-04-05T18:05:55.147Z
2013-04-05T18:05:55.147Z
Khaled.K
<p>There is a polynomial-time reduction from one problem to the other, as explained on <a href="http://en.wikipedia.org/wiki/Permanent_is_sharp-P-complete#01-Matrix">Wikipedia</a> among other places.</p>

CC BY-SA 3.0
2013-04-05T18:45:46.283Z
Very nice. I never saw that before.
Craig Feinstein
CC BY-SA 3.0
2013-04-05T17:38:24.930Z
2013-04-05T17:38:24.930Z
Timothy Chow
<p>How much easier is computing the permanent of a matrix with only zeroes and ones than a matrix of only integers?</p>

<cc.complexity-theory><matrices><permanent>
The complexity of computing the permanent of a matrix of zeroes and ones versus a matrix of integers
Craig Feinstein
# The complexity of computing the permanent of a matrix of zeroes and ones versus a matrix of integers

(Asked by: username_0 on 2013-04-05)

How much easier is computing the permanent of a matrix with only zeroes and ones than a matrix of only integers?

**Tags:** cc.complexity-theory, matrices, permanent

---

## 2 answers

### Answer by username_2 on 2013-04-05. Score: 15 | Accepted answer

There is a polynomial-time reduction from one problem to the other, as explained on [Wikipedia](http://en.wikipedia.org/wiki/Permanent_is_sharp-P-complete#01-Matrix) among other places.

> **Comments:**
> **username_0**: Very nice. I never saw that before.  

---

### Answer by username_1 on 2013-04-05. Score: 2

The [permanent](http://en.wikipedia.org/wiki/Permanent) of a [01-matrix](http://en.wikipedia.org/wiki/%280,1%29-matrix) is equal to the number of [vertex cycle covers](http://en.wikipedia.org/wiki/Vertex_cycle_cover) of an unweighted directed graph. Its computation is [#P-complete](http://en.wikipedia.org/wiki/Sharp-P-complete).


---

