# Questions tagged [permanent]

The tag has no usage guidance.

49 questions
Filter by
Sorted by
Tagged with
2answers
832 views

### Is there a direct/natural reduction to count non-bipartite perfect matchings using the permanent?

Counting the number of perfect matchings in a bipartite graph is immediately reducible to computing the permanent. Since finding a perfect matching in a non-bipartite graph is in NP, there exists ...
2answers
1k views

### Lower bound for determinant and permanent

In light of the recent chasm at depth-3 result (which among other things yields a $2^{\sqrt{n}\log{n}}$ depth-3 arithmetic circuit for the $n \times n$ determinant over $\mathbb{C}$), I have the ...
5answers
3k views

### About properties of adjacency matrix when a graph is planar

1- Is there any specific properties for adjacency matrix when a graph is planar? 2- Is there any thing special for computing the permanent of adjacency matrix when a graph is planar?
5answers
713 views

### Easy problems with hard counting versions

Wikipedia provides examples of problems where the counting version is hard, whereas the decision version is easy. Some of these are counting perfect matchings, counting the number of solutions to $2$-...
2answers
790 views

1answer
581 views

### Permanent of a $3 \times 3$ and $4 \times 4$ matrix from determinants

Let $A$ be a $3 \times 3$ or a $4 \times 4$ matrix with entries $a_{ij}$. Can someone provide me a matrix $B$ so that $\operatorname{per}(A) = \det(B)$? What is the smallest explicit $B$ that is known ...
2answers
639 views

### Cancellation and determinant

Berkowitz algorithm provides a polynomial size circuit with logarithmic depth for determinant of a square matrix using matrix powers. The algorithm implicitly uses cancellation. Is cancellation ...
1answer
501 views

### Conditional results implying difficulty of improving upper/lower bounds for permanent

Let $A$ be a given square matrix. Is there any evidence that beating quadratic lower bounds for $B$ such that $\text{det}(B) = \text{per}(A)$ could be hard? Is there any plausible conjecture which ...
1answer
195 views

0answers
81 views

### Is $MSB$ of permanent and certifying half number of witnesses easy?

Can there be a $P$ algorithm to decide if number of perfect matchings is at least $(n!/2)+1$ for a bipartite graph on $n+n$ vertices? Can there be a $P$ algorithm to decide if number of witnesses ...
2answers
343 views

### The complexity of computing the permanent of a matrix of zeroes and ones versus a matrix of integers

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