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.
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
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.
- (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.