6.5440 Algorithmic Lower Bounds: Fun with Hardness Proofs (Fall 2023)

This lecture is about counting solutions, instead of just finding one. Given an NP problem and a notion of certificates for that problem, the counting version of the problem is to determine the number of valid certificates for a given instance. Analogous to NP, we get a class #P.

In the world of Karp-style reductions, we get the notion of parsimonious (and “c-monious”, a term I made up) reductions that preserve the number of solutions (possibly with a uniform scale factor c). Many #P-hardness reductions are obtained this way. More generally, though, #P-hardness is defined relative to Cook-style multicall reductions.

After reviewing some old proofs and whether they are parsimonious, we'll prove a bunch of problems #P-complete:

• Permanent of a matrix
• 0/1 permanent = counting perfect matchings in planar graphs
• #2SAT
• Hamiltonicity
• Nikoli puzzles Shakashaka and Slitherlink

We'll also discuss the related notion of ASP (Another Solution Problem) and ASP-completeness. This area is motivated by many puzzles (such as Nikoli puzzles) which are supposed to be designed to have unique solutions. How can we tell whether the solution is unique, or equivalently, whether the puzzle has a second solution? Here we need our reductions to preserve solution uniqueness, a weaker condition than parsimony (but not c-mony).