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?
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)&lt;2n.  Let

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

I leave the rest of the proof as exercise.


Show that function f is in #P.
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].
(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.