in theory

"Marge, I agree with you – in theory. In theory, communism works. In theory." — Homer Simpson

CS254 Lecture 8 – Approximate Counting

Posted on May 6, 2010 by luca

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.

Continue reading →