Questions: Counting Complexity and the Sharp-P Class

Question 1

Given a bipartite graph, you need to determine (a) whether a perfect matching exists, and (b) how many perfect matchings exist. What is the computational complexity of each task?

• A. Both tasks are in P — matching algorithms solve both efficiently
• B. Task (a) is in P; task (b) is #P-complete — deciding is easy but counting is hard
• C. Both tasks are NP-complete — matchings are hard to find and count
• D. Task (a) is NP-complete; task (b) is in P — counting is easier than deciding for matchings

Answer: (B)

This is the canonical example illustrating that counting can be dramatically harder than deciding. Deciding whether a perfect matching exists is in P — polynomial-time algorithms (e.g., Hopcroft-Karp) solve it efficiently. But counting the number of perfect matchings is equivalent to computing the permanent of the bipartite adjacency matrix, which Valiant proved is #P-complete in 1979. No polynomial-time algorithm is known for the permanent, and #P-completeness shows this is likely not an accident. The decision problem being easy does not help you count solutions.

Question 2

Why is computing the permanent of a matrix computationally harder than computing the determinant, even though their formulas differ only in that the permanent uses all-positive signs while the determinant uses alternating signs?

• A. The permanent formula has more terms and therefore takes longer to evaluate directly
• B. The alternating signs in the determinant allow Gaussian elimination to exploit massive algebraic cancellations, while the all-positive permanent eliminates this structure
• C. Matrices with all-positive permanents are rarer than those with non-zero determinants, making them harder to find
• D. The permanent is not actually harder — it just lacks efficient built-in software support

Answer: (B)

The determinant can be computed in polynomial time via Gaussian elimination because the alternating signs enable enormous algebraic cancellation — rows can be added and subtracted to create zeros, reducing the matrix to triangular form. The permanent has no minus signs, so no such cancellations occur: every term in the expansion is positive and no row operations can simplify the computation. Valiant showed this structural difference makes the permanent #P-hard. Two nearly identical formulas have exponentially different computational complexity due to the presence or absence of cancellation structure.

Question 3

#P is a subset of NP because most #P counting problem has a corresponding NP decision problem.

• T. True
• F. False

Answer: False

NP and #P are incomparable as classes: NP contains decision problems (yes/no answers), while #P contains function problems (counting answers). They cannot be directly compared by subset inclusion. More importantly, #P is believed to be strictly harder than NP: Toda's theorem shows that the entire polynomial hierarchy PH reduces to P^#P, meaning a single #P oracle call can simulate any number of alternations between existential and universal quantifiers. Informally, #P is far above NP in computational power — not a subset of it.

Question 4

A problem that is easy to decide (solvable in polynomial time, i.e., in P) can seldom be #P-hard to count.

• T. True
• F. False

Answer: False

This is precisely the surprising insight from #P theory. Perfect matching decision is in P, yet counting perfect matchings is #P-complete (Valiant, 1979). Similarly, 2-coloring a graph is in P, but counting the number of valid 2-colorings is #P-complete. Easy decidability provides no guarantee of easy countability. The counting version asks for a complete tally of all witnesses — which can be vastly harder than merely certifying that one exists.

Question 5

Explain why Toda's theorem implies that counting solutions is 'more powerful' than deciding membership, even with the full computational power of the polynomial hierarchy.

Model answer: Toda's theorem states that every problem in the polynomial hierarchy PH can be solved by a polynomial-time machine with a single oracle call to a #P function. This means #P subsumes the entire PH: anything decidable using any finite alternation of ∃ and ∀ quantifiers (any problem in Σₖ or Πₖ for any k) can also be solved with one counting query. The polynomial hierarchy represents the power of alternating between guessing and verifying-all-cases, yet a single counting query is sufficient to simulate all of this. Knowing exactly how many witnesses exist is more informative than knowing whether any exist.

This theorem is why #P is considered to sit 'above' the polynomial hierarchy in computational power. In practice, this explains why exact probabilistic inference and exact counting are computationally expensive even when corresponding decision problems are easy, and why approximation algorithms and sampling methods (Monte Carlo, FPRAS) dominate practical applications where #P-complete counting problems arise.