Algebraic combinatorics studies objects and structures arising from algebra, representation theory, algebraic geometry via discrete methods. Many of the quantities relevant for these areas are nonneg- ative integers (dimensions, multiplicities, point counts etc), and the natural question arises, what the best formulas to compute them are, and if they also count some nice set of objects. I will intro- duce some of the main such quantities, like dimension of Specht modules, Littlewood-Richardson and Kronecker coefficients, and explain what is known or could be theoretically achieved using the formalism of computational complexity.