<p>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<sup>#P[1]</sup>.</p>

<p>For a graph <i>G</i> on <i>n</i> vertices, let <i>g</i><sub><i>k</i></sub>(<i>G</i>) be the number of independent sets of size <i>k</i> in <i>G</i>.  Note that 0≤<i>g</i><sub><i>k</i></sub>(<i>G</i>)&lt;2<sup><i>n</i></sup>.  Let</p>

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

<p>I leave the rest of the proof as exercise.</p>

<ol>
<li>Show that function <i>f</i> is in #P.</li>
<li>Show that the independence number of <i>G</i> can be computed from two integers <i>n</i> and <i>f</i>(<i>G</i>) in time polynomial in <i>n</i>, and conclude that the independence number can be computed in FP<sup>#P[1]</sup>.</li>
<li>(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.</li>
</ol>

<p>The same idea works also for the chromatic number.</p>

CC BY-SA 3.0
2012-03-12T00:39:12.577Z
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
CC BY-SA 3.0
2012-03-12T11:22:57.973Z
@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
CC BY-SA 3.0
2012-03-11T22:53:05.393Z
2012-03-11T22:53:05.393Z
Tsuyoshi Ito
<p>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?</p>

CC BY-SA 3.0
2012-03-11T10:25:13.667Z
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
CC BY-SA 3.0
2012-03-11T19:28:27.693Z
@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
CC BY-SA 3.0
2012-03-12T07:57:44.933Z
If you want a really transparent example, the permanent of the [biadjacency matrix](http://en.wikipedia.org/wiki/Adjacency_matrix#Adjacency_matrix_of_a_bipartite_graph) 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
<cc.complexity-theory><counting-complexity><permanent>
examples of use of permanents
v s
# examples of use of permanents

(Asked by: username_0 on 2012-03-11)

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?

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

> **Comments:**
> **username_1**: 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.  
> **username_0**: @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!  
> **username_2**: If you want a really transparent example, the permanent of the [biadjacency matrix](http://en.wikipedia.org/wiki/Adjacency_matrix#Adjacency_matrix_of_a_bipartite_graph) 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.  

---

## 1 answers

### Answer by username_3 on 2012-03-11. Score: 3 | Accepted 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 *g**k*(*G*) be the number of independent sets of size *k* in *G*. Note that 0≤*g**k*(*G*)<2*n*. 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.

> **Comments:**
> **username_0**: 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?  
> **username_3**: @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.  

---

