COOKIES: By using this website you agree that we can place Google Analytics Cookies on your device for performance monitoring. |

University of Cambridge > Talks.cam > Logic and Semantics Seminar (Computer Laboratory) > The complexity of counting problems

## The complexity of counting problemsAdd to your list(s) Download to your calendar using vCal - David Richerby, University of Essex
- Friday 29 April 2022, 14:00-15:00
- SS03.
If you have a question about this talk, please contact Jamie Vicary. Every computational decision problem (“Is there an X?”) has a natural counting variant (“How many X’s are there?”). More generally, computing weighted sums such as integrals, expectations and partition functions in statistical physics can also be seen as counting problems. I will give an introduction to the complexity of solving counting problems. I will focus on variants of constraint satisfaction problems (CSPs) and exactly counting the solutions, though I’ll also touch on approximate counting. CSPs are powerful enough to naturally express many important problems, but also being restricted enough to allow their computational complexity to be classified completely and elegantly. This talk is part of the Logic and Semantics Seminar (Computer Laboratory) series. ## This talk is included in these lists:- All Talks (aka the CURE list)
- Cambridge talks
- Computer Laboratory talks
- Computing and Mathematics
- Interested Talks
- Logic and Semantics Seminar (Computer Laboratory)
- SS03
- School of Technology
- Trust & Technology Initiative - interesting events
- bld31
- yk373's list
Note that ex-directory lists are not shown. |
## Other listsRoyal Society Rosalind Franklin Seminar Series MRC Chaucer Club Computer Laboratory talks## Other talksPredicting Transitions far from Equilibrium Magma as Soft Matter On the quenching of star formation in observed and simulated central galaxies: Evidence for the role of integrated AGN feedback Talk 4 â€“Protocols to Control Transmission Within Schools Jo Evans title and abstract tba Gateway CCIMI |