We consider the computation of n-variate polynomials over a field F via a sequence of arithmetic operations such as additions, subtractions, multiplications, divisions, etc. It has been known for at five decades now that a random n-variate polynomial of degree n is hard to compute. Yet not a single explicit polynomial is provably known to be hard to compute (although we have a lot of good candidates). In this talk we will first describe this problem and its relationship to the P vs NP problem. We will then describe several partial results on this problem, both old and new, along with a more general approach/framework that ties together most of these partial results.