# 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 number of a graph through the permanent?

• Since you can reduce #3SAt to the permanent, you can solve the permanent to find the number of solutions to the 3SAt instance. if it's more than zero, the problem is satisfiable. – Suresh Venkat Mar 11 '12 at 10:25
• @SureshVenkat that is true. I was thinking of something else.. along the lines of given a graph using a single calculation of permanent to find the max indep number. Was curious if such a trick existed! – v s Mar 11 '12 at 19:28
• If you want a really transparent example, the permanent of the biadjacency matrix of a bipartite graph counts the number of perfect matchings in this graph. For a non-bipartite graph, the permanent of its adjacency matrix counts the number of cycle covers. – Bruno Mar 12 '12 at 7:57

## 1 Answer

Here is a hint for your question in the comment to the question. The independence number of a graph can be computed by a polynomial-time oracle Turing machine which calls the #P oracle just once. That is, the independence number is in class FP#P[1].

For a graph G on n vertices, let gk(G) be the number of independent sets of size k in G. Note that 0≤gk(G)<2n. Let

$$f(G)=\sum_{k=0}^n 2^{nk}g_k(G).$$

I leave the rest of the proof as exercise.

1. Show that function f is in #P.
2. Show that the independence number of G can be computed from two integers n and f(G) in time polynomial in n, and conclude that the independence number can be computed in FP#P[1].
3. (If this is not clear from item 2,) conclude that the independence number can be computed by a polynomial-time oracle Turing machine which calls the oracle for the permanent just once.

The same idea works also for the chromatic number.

• I think this is what I may be looking for. I am unfamiliar with #P proofs. There has to be a way to show $1$ can be found through permanent of an appropriately constructed matrix. That matrix and its construction is probably what I am seeking? – v s Mar 12 '12 at 0:39
• @vs: As I suggested in this answer, you should forget about the permanent and just use the definition of #P until step 3. Once you have a proof, you can rewrite the whole proof to use the permanent throughout the proof, but that is not intuitive because the proof of the #P-completeness of the permanent is unintuitive. – Tsuyoshi Ito Mar 12 '12 at 11:22