[+] #P and ASP. NP search problem, # problems, #P, parsimonious and cmonious reductions, SAT problems, Shakashaka, Hamiltonicity, Slitherlink, permanent, counting bipartite (perfect/maximal) matchings, counting minimal vertex covers, positive #2SAT. ASP (Another Solution Problem).  [Scribe Notes] [src]  
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 Karpstyle reductions, we get the notion of parsimonious (and “cmonious”, a term I made up) reductions that preserve the number of solutions (possibly with a uniform scale factor c). Many #Phardness reductions are obtained this way. More generally, though, #Phardness is defined relative to Cookstyle multicall reductions. After reviewing some old proofs and whether they are parsimonious, we'll prove a bunch of problems #Pcomplete:
We'll also discuss the related notion of ASP (Another Solution Problem) and ASPcompleteness. 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 cmony). 
Handwritten notes, page 1/8 •
[previous page] •
[next page] •
[PDF]
Handwritten notes, page 1/8 • [previous page] • [next page] • [PDF] 

Slides, page 1/21 •
[previous page] •
[next page] •
[PDF]
Slide from Lecture 7. Figure drawn by Erik Demaine based on Figure 4 of http://dx.doi.org/10.1137/0211025 Slides, page 1/21 • [previous page] • [next page] • [PDF] 
The video above should play if your web browser supports either modern Flash or HTML5 video with H.264 or WebM codec. The handwritten notes and slides should advance automatically. If you have any trouble with playback, email Erik.