# CS254 Lecture 8 – Approximate Counting

Counting Problems

Today we describe counting problems and the class ${{\bf \#P}}$ that they define, and we show that every counting problem ${{\bf \#P}}$ can be approximately solved in randomized polynomial given access to an ${{\bf NP}}$ oracle.