One of the seven Millennium Prize Problems is called the P versus NP problem. Every ambitious mathematics student should probably know what it is. At the bottom of this problem lie the most profound questions about the nature of mathematical thought: what is truth, what is proof, what is a creative leap, what is trust, what is verification. Briefly, the "P not equal to NP" conjecture postulates that it is inherently more difficult to come up with proofs than to verify a given purported proof is correct. Of course you may all feel this is intuitively true, but can you prove it?

The P versus NP problem is presented in the wider context of Computational Complexity Theory. This theory is the quantitative study of efficient computation. It turns out that the computation and its complexity form the key link of truth, proof and verification. The central theme of Computational Complexity Theory is to give classification theorems, not unlike the classification theorem for all finite simple groups.  In this talk I will discuss some progress in this classification program for the class of counting problems.