Tagged Questions
3
votes
1answer
198 views
examples of use of permanents
It is known that if calculating permanent is easy, then solving hard problems in NP is easy. Is there a transparent example regarding application of say finding independent set or find chromatic ...
12
votes
2answers
281 views
A question to the #P-complete proof of the permanent from Ben-Dor/Halevi
In the paper of Ben-Dor/Halevi [1] it is given another proof that the permanent is
$\#P$-complete. In the later part of the paper, they show the reduction chain
\begin{equation}
\text{IntPerm} \propto ...
-2
votes
1answer
203 views
Complexity of counting the number of Good-perfect matching in the bipartite graph
Let's $G=(U, V, E)$ be a balanced bipartite graph which $|U|=|V|=n$ and $|E|=n*(n-1)$; All nodes in $U$ are connected to all nodes in $V$ except $u_i$ to $v_i$ for $1\leq i \leq n$.
Definition1: ...
1
vote
1answer
301 views
The Relationship between P^NP and the Permanent
In the lecture notes Introduction to Complexity Theory by Goldreich, there is a section called "How close is $\#P$ is to $NP$". It is stated there that a $P^{NP}$ machine would approximate $\#P$ in ...
21
votes
2answers
614 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 ...
