Claremont Center for the Mathematical Sciences

Much of my research involves approximating the sizes of sets that are described combinatorially. How many perfect matchings are there in a graph? How many linear extensions of a poset are there? [These are needed to find p-values of certain statistical tests.] Typically these problems are thought of as being hard, and in the 1970's this notion of hardness was made precise with the idea of #P complete problems. In this talk, I will define #P completeness, talk about the differences between #P and NP complete problems, give several examples, and present the proof of Brightwell and Winkler that counting the number of linear extensions of a poset is #P complete.