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?
3
$\begingroup$
$\endgroup$
-
5$\begingroup$ 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. $\endgroup$ – Suresh Venkat Mar 11 '12 at 10:25
-
$\begingroup$ @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! $\endgroup$ – v s Mar 11 '12 at 19:28
-
2$\begingroup$ 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. $\endgroup$ – Bruno Mar 12 '12 at 7:57
3
$\begingroup$
$\endgroup$
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.
- 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.
answered Mar 11 '12 at 22:53
-
$\begingroup$ 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? $\endgroup$ – v s Mar 12 '12 at 0:39
-
1$\begingroup$ @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. $\endgroup$ – Tsuyoshi Ito Mar 12 '12 at 11:22
