Valiant defined #P and showed that permanent and other functions are hard for this class.